Search

As a complement of our recent article [O. Stein and A. Tezel, J. Global Optim., 41 (2008), pp. 245-266], we study convergence of a semismooth Newton method for generalized semi-infinite programming problems with convex lower level problems. The semismooth Newton method is applied to a semismooth reformulation of the upper and lower level Karush-Kuhn-Tucker conditions by nonlinear complementarity problem functions into a semismooth system of equations. In the present paper we assume strict complementary slackness neither in the upper nor in the lower level. The auxiliary functions of the locally reduced problem then are not necessarily twice continuously differentiable. Still, we can show that a standard regularity condition for quadratic convergence of the semismooth Newton method holds under a natural assumption for semi-infinite programs.

This paper extends the regularized smoothing Newton method in vector complementarity problems to symmetric cone complementarity problems (SCCP), which includes the nonlinear complementarity problem, the second-order cone complementarity problem, and the semidefinite complementarity problem as special cases. In particular, we study strong semismoothness and Jacobian nonsingularity of the total natural residual function for SCCP. We also derive the uniform approximation property and the Jacobian consistency of the Chen-Mangasarian smoothing function of the natural residual. Based on these properties, global and quadratical convergence of the proposed algorithm is established.

In this paper we establish the existence of a discrete zero point of a function from the $n$-dimensional integer lattice $\mathbb{Z}^n$ to the $n$-dimensional Euclidean space $\mathbb{R}^n$ under very general conditions with respect to the behavior of the function. The proof is constructive and uses a combinatorial argument based on a simplicial algorithm with vector labeling and lexicographic linear programming pivot steps. The algorithm provides an efficient method to find an exact solution. We also discuss how to adapt the algorithm for two related problems, namely, to find a discrete zero point of a function under a general antipodal condition and to find a solution to a discrete nonlinear complementarity problem. In both cases the modified algorithm provides a constructive existence proof, too. We further show that the algorithm for the discrete nonlinear complementarity problem generalizes the well-known Lemke’s method to nonlinear environments. An economic application is also presented.

The second-order cone complementarity problem (SOCCP) is a wide class of problems containing the nonlinear complementarity problem (NCP) and the second-order cone programming problem (SOCP). Recently, Fukushima, Luo, and Tseng [SIAM J. Optim., 12 (2001), pp. 436--460] extended some merit functions and their smoothing functions for NCP to SOCCP. Moreover, they derived computable formulas for the Jacobians of the smoothing functions and gave conditions for the Jacobians to be invertible. In this paper, we propose a globally and quadratically convergent algorithm, which is based on smoothing and regularization methods, for solving monotone SOCCP. In particular, we study strong semismoothness and Jacobian consistency, which play an important role in establishing quadratic convergence of the algorithm. Furthermore, we examine the effectiveness of the algorithm by means of numerical experiments.

We develop a semismoothness concept for nonsmooth superposition operators in function spaces. The considered class of operators includes nonlinear complementarity problem (NCP)-function-based reformulations of infinite-dimensional nonlinear complementarity problems and thus covers a very comprehensive class of applications. Our results generalize semismoothness and $\alpha$-order semismoothness from finite-dimensional spaces to a Banach space setting. For this purpose, a new infinite-dimensional generalized differential is used that is motivated by Qi's finite-dimensional C-subdifferential [Research Report AMR96/5, School of Mathematics, University of New South Wales, Australia, 1996]. We apply these semismoothness results to develop a Newton-like method for nonsmooth operator equations and prove its local q-superlinear convergence to regular solutions. If the underlying operator is $\alpha$-order semismooth, convergence of q-order $1+\alpha$ is proved. We also establish the semismoothness of composite operators and develop corresponding chain rules. The developed theory is accompanied by illustrative examples and by applications to NCPs and a constrained optimal control problem.

Minimization of a differentiable function subject to box constraints is proposed as a strategy to solve the generalized nonlinear complementarity problem (GNCP) defined on a polyhedral cone. It is not necessary to calculate projections that complicate and sometimes even disable the implementation of algorithms for solving these kinds of problems. Theoretical results that relate stationary points of the function that is minimized to the solutions of the GNCP are presented. Perturbations of the GNCP are also considered, and results are obtained related to the resolution of GNCPs with very general assumptions on the data. These theoretical results show that local methods for box-constrained optimization applied to the associated problem are efficient tools for solving the GNCP. Numerical experiments are presented that encourage the use of this approach.

Two recent papers [F. Facchinei, Math. Oper. Res., 23 (1998), pp. 735--745 and F. Facchinei and C. Kanzow, SIAM J. Control Optim., 37 (1999), pp. 1150--1161] have shown that for a continuously differentiable P0-function f, the nonlinear complementarity problem NCP$(f_\varepsilon)$ corresponding to the regularization $f_\varepsilon(x):=f(x)+\varepsilon x$ has a unique solution for every $\varepsilon>0$, that dist ($x(\varepsilon), \,{\mathop{\rm SOL}}(f))\rightarrow 0$ as $\varepsilon \rightarrow 0$ when the solution set SOL(f) of NCP(f) is nonempty and bounded, and NCP(f) is stable if and only if the solution set is nonempty and bounded. These results are proved via the Fischer function and the mountain pass theorem. In this paper, we generalize these nonlinear complementarity results to a box variational inequality problem corresponding to a continuous P0-function where the regularization is described by an integral. We also describe an upper semicontinuity property of the inverse of a weakly univalent function and study its consequences.

In this paper, we consider a proximal point algorithm (PPA) for solving monotone nonlinear complementarity problems (NCP). PPA generates a sequence by solving subproblems that are regularizations of the original problem. It is known that PPA has global and superlinear convergence properties under appropriate criteria for approximate solutions of subproblems. However, it is not always easy to solve subproblems or to check those criteria. In this paper, we adopt the generalized Newton method proposed by De Luca, Facchinei, and Kanzow to solve subproblems and adopt some NCP functions to check the criteria. Then we show that the PPA converges globally provided that the solution set of the problem is nonempty. Moreover, without assuming the local uniqueness of the solution, we show that the rate of convergence is superlinear in a genuine sense, provided that the limit point satisfies the strict complementarity condition.

The Josephy--Newton method for solving a nonlinear complementarity problem consists of solving, possibly inexactly, a sequence of linear complementarity problems. Under appropriate regularity assumptions, this method is known to be locally (superlinearly) convergent. To enlarge the domain of convergence of the Newton method, some globalization strategy based on a chosen merit function is typically used. However, to ensure global convergence to a solution, some additional restrictive assumptions are needed. These assumptions imply boundedness of level sets of the merit function and often even (global) uniqueness of the solution. We present a new globalization strategy for monotone problems which is not based on any merit function. Our linesearch procedure utilizes the regularized Newton direction and the monotonicity structure of the problem to force global convergence by means of a (computationally explicit) projection step which reduces the distance to the solution set of the problem. The resulting algorithm is truly globally convergent in the sense that the subproblems are always solvable, and the whole sequence of iterates converges to a solution of the problem without any regularity assumptions. In fact, the solution set can even be unbounded. Each iteration of the new method has the same order of computational cost as an iteration of the damped Newton method. Under natural assumptions, the local superlinear rate of convergence is also achieved.

In this paper, we propose a new QP-free method, which ensures the feasibility of all iterates, for inequality constrained optimization. The method is based on a nonsmooth equation reformulation of the KKT optimality condition, by using the Fischer--Burmeister nonlinear complementarity problem function. The study is strongly motivated by recent successful applications of this function to the complementarity problem and the variational inequality problem. The method we propose here enjoys some advantages over similar methods based on the equality part of the KKT optimality condition. For example, without assuming isolatedness of the accumulation point or boundedness of the Lagrangian multiplier approximation sequence, we show that every accumulation point of the iterative sequence generated by this method is a KKT point if the linear independence condition holds. And if the second-order sufficient condition and the strict complementarity condition hold, the method is superlinearly convergent. Some preliminary numerical results indicate that this new QP-free method is quite promising.

We present a new algorithm for the solution of general (not necessarily monotone) complementarity problems. The algorithm is based on a reformulation of the complementarity problem as a nonsmooth system of equations by using the Fischer--Burmeister function. We use an idea by Chen, Qi, and Sun and apply a Jacobian smoothing method (which combines nonsmooth Newton and smoothing methods) to solve this system. In contrast to that of Chen, Qi, and Sun, however, our method is at least well defined for general complementarity problems. Extensive numerical results indicate that the new algorithm works very well. In particular, it can solve all nonlinear complementarity problems from the MCPLIB and GAMSLIB libraries.

A noninterior continuation method is proposed for nonlinear complementarity problems. It improves the noninterior continuation methods recently studied by Burke and Xu [Math. Oper. Res., 23 (1998), pp. 719--734] and Xu [The Global Linear Convergence of an Infeasible Non-Interior Path-following Algorithm for Complementarity Problems with Uniform P-functions, Preprint, Department of Mathematics, University of Washington, Seattle, 1996]; the interior point neighborhood technique is extended to a broader class of smoothing functions introduced by Chen and Mangasarian [Comput. Optim. Appl., 5 (1996), pp. 97--138]. The method is shown to be globally linearly convergent following the methodology established by Burke and Xu. In addition, a local acceleration step is added to the method so that it is also locally quadratically convergent under suitable assumptions.

It is well known that a nonlinear complementarity problem (NCP) can be formulated as a system of nonsmooth equations. Chen and Mangasarian [Comput. Optim. Appl., 5 (1996), pp. 97--138] proposed a class of parametric smooth functions by twice integrating a probability density function. As a result, the nonsmooth equations can be approximated by smooth equations. This paper refines the smooth functions proposed by Chen and Mangasarian and investigates their structural properties. The refinement allows us to establish the existence, uniqueness, and limiting properties of the trajectory defined by the solutions of these smooth equation approximations. In addition, global error bounds for the NCP with a uniform P-function are obtained.

We investigate the properties of a new merit function which allows us to reduce a nonlinear complementarity problem to an unconstrained global minimization one. Assuming that the complementarity problem is defined by a $P_0$-function, we prove that every stationary point of the unconstrained problem is a global solution; furthermore, if the complementarity problem is defined by a uniform $P$-function, the level sets of the merit function are bounded. The properties of the new merit function are compared with those of Mangasarian--Solodov's implicit Lagrangian and Fukushima's regularized gap function. We also introduce a new simple active-set local method for the solution of complementarity problems and show how this local algorithm can be made globally convergent by using the new merit function.

We consider two merit functions for a generalized nonlinear complementarity problem (GNCP) based on quadratic regularization of the standard linearized gap function. The first extends Fukushima’s merit function for variational inequality problems [Fukushima, Math. Programming, 53 (1992), pp. 99–110] and the second extends Mangasarian and Solodov’s implicit Lagrangian for complementarity problems [Mangasarian and Solodov, Math. Programming, 62 (1993), pp. 277–297]. We show, among other things, that the second merit function is in the order of the natural residual squared and we give conditions under which the stationary points of this function are the solutions to GNCP. These results extend those of Luo et al. [Math. Oper. Res., 19 (1994), pp. 880–892] and of Yamashita and Fukushima [J. Optim. Theory Appl., 84 (1995), pp. 653–663] on the properties of the implicit Lagrangian.

In this paper, the authors describe and establish the convergence of a new iterative method for solving the (nonmonotone) nonlinear complementarily problem (NCP). The method utilizes ideas from two distinct pproaches for solving this problem and combines them into one unified framework. One of these is the infeasible-interior-point approach that computes an approximate solution to the NCP by staying in the interior of the nonnegative orthant; the other approach is typified by the NE/SQP method which is based on a generalized Gauss–Newton scheme applied to a constrained nonsmooth-equations formulation of the complementarily problem. The new method, called a positive algorithm for the NCP, generates a sequence of positive vectors by solving a sequence of linear equations (as in a typical interior-point method) whose solutions (if nonzero) provide descent directions for a certain merit function that is derived from the NE/SQP iteration function modified for use in an interior-point context.