Interior-point methods for nonlinear complementarity problems

We present a potential reduction interior-point algorithm for monotone nonlinear complementarity problems. At each iteration, one has to compute an approximate solution of a nonlinear system such that a certain accuracy requirement is satisfied. For problems satisfying a scaled Lipschitz condition, this requirement is satisfied by the approximate solution obtained by applying one Newton step to that nonlinear system. We discuss the global and local convergence rates of the algorithm, convergence toward a maximal complementarity solution, a criterion for switching from the interior-point algorithm to a pure Newton method, and the complexity of the resulting hybrid algorithm.This research was supported in part by NSF Grant DDM-89-22636.The authors would like to thank Rongqin Sheng and three anonymous referees for their comments leading to a better presentation of the results.     

Regular exceptional family of elements with respect to isotone projection cones in Hilbert spaces and complementarity problems

Conditions for the non-existence of a regular exceptional family of elements with respect to an isotone projection cone in a Hilbert space will be presented. The obtained results will be used for generating existence theorems for a complementarity problem with respect to an isotone projection cone in a Hilbert space.     

An unconstrained smooth minimization reformulation of the second-order cone complementarity problem

A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over ℝⁿ. A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over ℝⁿ and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiability, not continuous differentiability, was established. In this paper, we extend this merit function and its analysis, including continuous differentiability, to the second-order cone complementarity problem (SOCCP). Although SOCCP is reducible to a SDCP, the reduction does not allow for easy translation of the analysis from SDCP to SOCCP. Instead, our analysis exploits properties of the Jordan product and spectral factorization associated with the second-order cone. We also report preliminary numerical experience with solving DIMACS second-order cone programs using a limited-memory BFGS method to minimize the merit function. In honor of Terry Rockafellar on his 70th birthday     

On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm

This paper is devoted to the eigenvalue complementarity problem (EiCP) with symmetric real matrices. This problem is equivalent to finding a stationary point of a differentiable optimization program involving the Rayleigh quotient on a simplex (Queiroz et al., Math. Comput. 73, 1849–1863, 2004). We discuss a logarithmic function and a quadratic programming formulation to find a complementarity eigenvalue by computing a stationary point of an appropriate merit function on a special convex set. A variant of the spectral projected gradient algorithm with a specially designed line search is introduced to solve the EiCP. Computational experience shows that the application of this algorithm to the logarithmic function formulation is a quite efficient way to find a solution to the symmetric EiCP.     

Nonlinear relaxation methods for solving symmetric linear complementarity problems

A family of iterative algorithms is presented for the solution of the symmetric linear complementarity problem,

Solving stochastic complementarity problems in energy market modeling using scenario reduction

In this paper, we analyze market equilibrium models with random aspects that lead to stochastic complementarity problems. While the models presented depict energy markets, the results are believed to be applicable to more general stochastic complementarity problems. The contribution is the development of new heuristic, scenario reduction approaches that iteratively work towards solving the full, extensive form, stochastic market model. The methods are tested on three representative models and supporting numerical results are provided as well as derived mathematical bounds.     

On the coerciveness of some merit functions for complementarity problems over symmetric cones

One of the popular solution methods for the complementarity problem over symmetric cones is to reformulate it as the global minimization of a certain merit function. An important question to be answered for this class of methods is under what conditions the level sets of the merit function are bounded (the coerciveness of the merit function). In this paper, we introduce the generalized weak-coerciveness of a continuous transformation. Under this condition, we prove the coerciveness of some merit functions, such as the natural residual function, the normal map, and the Fukushima-Yamashita function for complementarity problems over symmetric cones. We note that this is a much milder condition than strong monotonicity, used in the current literature.     

Implicit complementarity problems on isotone projection cones

Isac and Németh [G. Isac and A. B. Németh, Projection methods, isotone projection cones and the complementarity problem, J. Math. Anal. Appl. 153 (1990), pp. 258–275] proved that solving a coincidence point equation (fixed point problem) in turn solves the corresponding implicit complementarity problem (nonlinear complementarity problem) and they exploited the isotonicity of the metric projection onto isotone projection cones to solve implicit complementarity problems (nonlinear complementarity problems) defined by these cones. In this article an iterative algorithm is studied in connection with an implicit complementarity problem. It is proved that if the sequence generated through the defined algorithm is convergent, then its limit is a solution of the coincidence point equation and thus solves the implicit complementarity problem. Sufficient conditions are given for this sequence to be convergent for implicit complementarity problems defined by isotone projection cones, extending the results of Németh [S.Z. Németh, Iterative methods for nonlinear complementarity problems on isotone projection cones, J. Math. Anal. Appl. 350 (2009), pp. 340–370]. Some existing concepts from the latter paper are extended to solve the problem of finding nonzero solutions of the implicit complementarity problem.     

An LP-based successive overrelaxation method for linear complementarity problems

A sparsity preserving LP-based SOR method for solving classes of linear complementarity problems including the case where the given matrix is positive-semidefinite is proposed. The LP subproblems need be solved only approximately by a SOR method. Heuristic enhancement is discussed. Numerical results for a special class of problems are presented, which show that the heuristic enhancement is very effective and the resulting program can solve problems of more than 100 variables in a few seconds even on a personal computer.This research was sponsored by the Air Force Office of Scientific Research, Grant No. AFOSR-86-0124. Part of this material is based on work supported by the National Science Foundation under Grant No. MCS-82-00632.The author is grateful to Dr. R. De Leone for his helpful and constructive comments on this paper.     

A class of nonlinear complementarity problems for multifunctions

Given a continuous mapF:R ⁿ R ⁿ and a lower semicontinuous positively homogeneous convex functionh:R ⁿ R, the nonlinear complementarity problem considered here is to findxR ₊ ⁿ andyh(x), the subdifferential ofh atx, such thatF(x)+y0 andx ^T (F(x)+y)=0. Some existence theorems for the above problem are given under certain conditions on the mapF. An application to quasidifferentiable convex programming is also shown.The authors are grateful to Professor O. L. Mangasarian and the referee for their substantive suggestions.     

The eigenvalue complementarity problem

In this paper an eigenvalue complementarity problem (EiCP) is studied, which finds its origins in the solution of a contact problem in mechanics. The EiCP is shown to be equivalent to a Nonlinear Complementarity Problem, a Mathematical Programming Problem with Complementarity Constraints and a Global Optimization Problem. A finite Reformulation–Linearization Technique (Rlt)-based tree search algorithm is introduced for processing the EiCP via the lattermost of these formulations. Computational experience is included to highlight the efficacy of the above formulations and corresponding techniques for the solution of the EiCP.     

Cycling in linear complementarity problems

A bound for the minimum length of a cycle in Lemke's Algorithm is derived. An example illustrates that this bound is sharp, and that the fewest number of variables is seven.     

The basic theorem of complementarity revisited

The basic theorm of (linear) complementarity was stated in a 1971 paper [6] by B.C. Eaves who credited C.E. Lemke for giving a constructive proof based on his almost complementary pivot algorithm. This theorem asserts that associated with an arbitrary linear complementarity problem, a certain augmented problem always possesses a solution. Many well-known existence results pertaining to the linear complementarity problem are consequences of this fundamental theorem.In this paper, we explore some further implications of the basic theorem of complementarity and derive new existence results for the linear complementarity problem. Based on these results, conditions for the existence of a solution to a linear complementarity problem with a fully-semimonotone matrix are examined. The class of the linear complementarity problems with aG-matrix is also investigated.The work of this author was based on research supported by the National Science Foundation under grant ECS-8717968.     

Computing integral solutions of complementarity problems

In this paper an algorithm is proposed to find an integral solution of (nonlinear) complementarity problems. The algorithm starts with a nonnegative integral point and generates a unique sequence of adjacent integral simplices of varying dimension. Conditions are stated under which the algorithm terminates with a simplex, one of whose vertices is an integral solution of the complementarity problem under consideration.     

Iterative methods for nonlinear complementarity problems on isotone projection cones

In this paper we present a recursion related to a nonlinear complementarity problem defined by a closed convex cone in a Hilbert space and a continuous mapping defined on the cone. If the recursion is convergent, then its limit is a solution of the nonlinear complementarity problem. In the case of isotone projection cones sufficient conditions are given for the mapping so that the recursion to be convergent.     

Consistent aggregation of linear complementarity problems

Aggregating linear complementarity problems under a general definition of constrained consistency leads to the possibility of consistent aggregation of linear and quadratic programming models and bimatrix games. Under this formulation, consistent aggregation of dual variables is also achieved. Furthermore, the existence of multiple sets of aggregation operators is discussed and illustrated with a numerical example. Constrained consistency can also be interpreted as a disaggregation rule. This aspect of the problem may be important for implementing macro (economic) policies by means of micro (economic) agents.Giannini Foundation Paper No. 548.     

Analysis of nonsmooth vector-valued functions associated with second-order cones

Let be the Lorentz/second-order cone in . For any function f from to , one can define a corresponding function f^soc(x) on by applying f to the spectral values of the spectral decomposition of x with respect to . We show that this vector-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Fréchet differentiability, continuous differentiability, as well as (-order) semismoothness. These results are useful for designing and analyzing smoothing methods and nonsmooth methods for solving second-order cone programs and complementarity problems.Mathematics Subject Classification (1991): 26A27, 26B05, 26B35, 49J52, 90C33, 65K05     

Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems

This paper provides an analysis of the polynomiality of primal-dual interior point algorithms for nonlinear complementarity problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu’s scaled Lipschitz condition, but is also applicable to mappings that are not monotone. We show that a family of primal-dual affine scaling algorithms generates an approximate solution (given a precision ε) of the nonlinear complementarity problem in a finite number of iterations whose order is a polynomial ofn, ln(1/ε) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in Jansen et al., SIAM Journal on Optimization 7 (1997) 126–140. Research supported in part by Grant-in-Aids for Encouragement of Young Scientists (06750066) from the Ministry of Education, Science and Culture, Japan. Research supported by Dutch Organization for Scientific Research (NWO), grant 611-304-028     

Parameter choice methods using minimization schemes

Regularization is typically based on the choice of some parametric family of nearby solutions, and the choice of this family is a task in itself. Then, a suitable parameter must be chosen in order to find an approximation of good quality. We focus on the second task. There exist deterministic and stochastic models for describing noise and solutions in inverse problems. We will establish a unified framework for treating different settings for the analysis of inverse problems, which allows us to prove the convergence and optimality of parameter choice schemes based on minimization in a generic way. We show that the well known quasi-optimality criterion falls in this class. Furthermore we present a new parameter choice method and prove its convergence by using this newly established tool.     

Locally unique solutions of quadratic programs,linear and nonlinear complementarity problems

It is shown that McCormick's second order sufficient optimality conditions are also necessary for a solution to a quadratic program to be locally unique and hence these conditions completely characterize a locally unique solution of any quadratic program. This result is then used to give characterizations of a locally unique solution to the linear complementarity problem. Sufficient conditions are also given for local uniqueness of solutions of the nonlinear complementarity problem.Research supported by National Science Foundation Grant MCS74-20584 A02.