Error bounds for nondegenerate monotone linear complementarity problems

Error bounds and upper Lipschitz continuity results are given for monotone linear complementarity problems with a nondegenerate solution. The existence of a nondegenerate solution considerably simplifies the error bounds compared with problems for which all solutions are degenerate. Thus when a point satisfies the linear inequalities of a nondegenerate complementarity problem, the residual that bounds the distance from a solution point consists of the complementarity condition alone, whereas for degenerate problems this residual cannot bound the distance to a solution without adding the square root of the complementarity condition to it. This and other simplified results are a consequence of the polyhedral characterization of the solution set as the intersection of the feasible region {zMz + q 0, z 0} with a single linear affine inequality constraint.This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228 and Air Force Office of Scientific Research Grant AFOSR-86-0172.     

Convergence behavior of interior-point algorithms

We show that most interior-point algorithms for linear programming generate a solution sequence in which every limit point satisfies the strict complementarity condition. These algorithms include all path-following algorithms and some potential reduction algorithms. The result also holds for the monotone complementarity problem if a strict complementarity solution exists. In general, the limit point is a solution that maximizes the number of its nonzero components among all solutions.Research supported in part by NSF Grant DDM-8922636, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.     

Generalized linear complementarity problems treated without fixed-point theory

We study the (monotone) linear complementarity problem in reflexive Banach space. The problem is treated as a quadratic program and shown to satisfy appropriate constraint qualifications. This leads to a theory of the generalized monotone linear complementarity problem which is independent of Brouwer's fixed-point theorem. Certain related results on linear systems are given. The final section concerns copositive operators.This research was partially supported by NSERC Grant No. A-5516.The author thanks the referee for his painstaking and thorough comments on this paper.     

A path-following interior-point algorithm for linear and quadratic problems

We describe an algorithm for the monotone linear complementarity problem (LCP) that converges from any positive, not necessarily feasible, starting point and exhibits polynomial complexity if some additional assumptions are made on the starting point. If the problem has a strictly complementarity solution, the method converges subquadratically. We show that the algorithm and its convergence properties extend readily to the mixed monotone linear complementarity problem and, hence, to all the usual formulations of the linear programming and convex quadratic programming problems.This research was supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Error bounds and strong upper semicontinuity for monotone affine variational inequalities

Global error bounds for possibly degenerate or nondegenerate monotone affine variational inequality problems are given. The error bounds are on an arbitrary point and are in terms of the distance between the given point and a solution to a convex quadratic program. For the monotone linear complementarity problem the convex program is that of minimizing a quadratic function on the nonnegative orthant. These bounds may form the basis of an iterative quadratic programming procedure for solving affine variational inequality problems. A strong upper semicontinuity result is also obtained which may be useful for finitely terminating any convergent algorithm by periodically solving a linear program.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grants CCR-9101801 and CCR-9157632.     

Complementarity problems over cones with monotone and pseudomonotone maps

The notion of a monotone map is generalized to that of a pseudomonotone map. It is shown that a differentiable, pseudoconvex function is characterized by the pseudomonotonicity of its gradient. Several existence theorems are established for a given complementarity problem over a certain cone where the underlying map is either monotone or pseudomonotone under the assumption that the complementarity problem has a feasible or strictly feasible point.This work was supported in part by the National Science Foundation, Grant No. GP-34619.     

A Lipschitzian error bound for monotone symmetric cone linear complementarity problem

We first discuss some properties of the solution set of a monotone symmetric cone linear complementarity problem (SCLCP), and then consider the limiting behaviour of a sequence of strictly feasible solutions within a wide neighbourhood of central trajectory for the monotone SCLCP. Under assumptions of strict complementarity and Slater’s condition, we provide four different characterizations of a Lipschitzian error bound for the monotone SCLCP in general Euclidean Jordan algebras. Thanks to the observation that a pair of primal-dual convex quadratic symmetric cone programming (CQSCP) problems can be exactly formulated as the monotone SCLCP, thus we obtain the same error bound results for CQSCP as a by-product.     

Global Error Bound for the Generalized Linear Complementarity Problem over a Polyhedral Cone

In this paper, the global error bound estimation for the generalized linear complementarity problem over a polyhedral cone (GLCP) is considered. To obtain a global error bound for the GLCP, we first develop some equivalent reformulations of the problem under milder conditions and then characterize the solution set of the GLCP. Based on this, an easily computable global error bound for the GLCP is established. The results obtained in this paper can be taken as an extension of the existing global error bound for the classical linear complementarity problems. This work was supported by the Research Grant Council of Hong Kong, a Chair Professor Fund of The Hong Kong Polytechnic University, the Natural Science Foundation of China (Grant No. 10771120) and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

A dual exact penalty formulation for the linear complementarity problem

We consider a dual exact penalty formulation for the monotone linear complementarity problem. Tihonov regularization is then used to reduce the solution of the problem to the solution of a sequence of positive-definite, symmetric quadratic programs. A modified form of an SOR method due to Mangasarian is proposed to solve these quadratic programs. We also indicate how to obtain approximate solutions to predefined tolerance by solving a single quadratic program, in special cases.This research was sponsored by US Army Contract DAAG29-80-C-0041, by National Science Foundation Grants DCR-8420963 and MCS-8102684, and AFSOR Grant AFSOR-ISSA-85-0880.     

Stable monotone variational inequalities

Variational inequalities associated with monotone operators (possibly nonlinear and multivalued) and convex sets (possibly unbounded) are studied in reflexive Banach spaces. A variety of results are given which relate to a stability concept involving a natural parameter. These include characterizations useful as criteria for stable existence of solutions and also several characterizations of surjectivity. The monotone complementarity problem is covered as a special case, and the results are sharpened for linear monotone complementarity and for generalized linear programming.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041 at the University of Wisconsin - Madison and by the National Science Foundation under Grant No. DMS-8405179 at the University of Illinois at Urbana-Champaign.     

Additive Schwarz algorithm for the nonlinear complementarity problem with M-function

In this paper, an additive Schwarz algorithm is considered for solving the finite-dimensional nonlinear complementarity problem with M-function. The monotone convergence of the algorithm is obtained with special choices of initial values. Moreover, the weighted max-norm bound is obtained for the iterative errors.     

Regularization Algorithms for Solving Monotone Ky Fan Inequalities with Application to a Nash-Cournot Equilibrium Model

We make use of the Banach contraction mapping principle to prove the linear convergence of a regularization algorithm for strongly monotone Ky Fan inequalities that satisfy a Lipschitz-type condition recently introduced by Mastroeni. We then modify the proposed algorithm to obtain a line search-free algorithm which does not require the Lipschitz-type condition. We apply the proposed algorithms to implement inexact proximal methods for solving monotone (not necessarily strongly monotone) Ky Fan inequalities. Applications to variational inequality and complementarity problems are discussed. As a consequence, a linearly convergent derivative-free algorithm without line search for strongly monotone nonlinear complementarity problem is obtained. Application to a Nash-Cournot equilibrium model is discussed and some preliminary computational results are reported.     

The linear complementarity problem as a separable bilinear program

The nonmonotone linear complementarity problem (LCP) is formulated as a bilinear program with separable constraints and an objective function that minimizes a natural error residual for the LCP. A linear-programming-based algorithm applied to the bilinear program terminates in a finite number of steps at a solution or stationary point of the problem. The bilinear algorithm solved 80 consecutive cases of the LCP formulation of the knapsack feasibility problem ranging in size between 10 and 3000, with almost constant average number of major iterations equal to four.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9322479 and CDA-9024618.     

Error bounds for analytic systems and their applications

Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01.     

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     

An infeasible-interior-point predictor-corrector algorithm for theP *-geometric LCP

AP _*-geometric linear complementarity problem (P _*GP) as a generalization of the monotone geometric linear complementarity problem is introduced. In particular, it contains the monotone standard linear complementarity problem and the horizontal linear complementarity problem. Linear and quadratic programming problems can be expressed in a “natural” way (i.e., without any change of variables) asP _*GP. It is shown that the algorithm of Mizunoet al. [6] can be extended to solve theP _*GP. The extended algorithm is globally convergent and its computational complexity depends on the quality of the starting points. The algorithm is quadratically convergent for problems having a strictly complementary solution. The work of F. A. Potra was supported in part by NSF Grant DMS 9305760     

Robust solution of monotone stochastic linear complementarity problems

We consider the stochastic linear complementarity problem (SLCP) involving a random matrix whose expectation matrix is positive semi-definite. We show that the expected residual minimization (ERM) formulation of this problem has a nonempty and bounded solution set if the expected value (EV) formulation, which reduces to the LCP with the positive semi-definite expectation matrix, has a nonempty and bounded solution set. We give a new error bound for the monotone LCP and use it to show that solutions of the ERM formulation are robust in the sense that they may have a minimum sensitivity with respect to random parameter variations in SLCP. Numerical examples including a stochastic traffic equilibrium problem are given to illustrate the characteristics of the solutions.     

Equivalence of the generalized complementarity problem to differentiable unconstrained minimization

We consider an unconstrained minimization reformulation of the generalized complementarity problem (GCP). The merit function introduced here is differentiable and has the property that its global minimizers coincide with the solutions of GCP. Conditions for its stationary points to be global minimizers are given. Moreover, it is shown that the level sets of the merit function are bounded under suitable assumptions. We also show that the merit function provides global error bounds for GCP. These results are based on a condition which reduces to the condition of the uniform P-function when GCP is specialized to the nonlinear complementarity problem. This condition also turns out to be useful in proving the existence and uniqueness of a solution for GCP itself. Finally, we obtain as a byproduct an error bound result with the natural residual for GCP.We thank Jong-Shi Pang for his valuable comments on error bound results with the natural residual for the nonlinear complementarity problem. We are also grateful to the anonymous referees for some helpful comments. The research of the second author was supported in part by the Science Research Grant-in-Aid from the Ministry of Education, Science, and Culture, Japan.     

A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function

We propose a new full-Newton step infeasible interior-point algorithm for monotone linear complementarity problems based on a simple locally-kernel function. The algorithm uses the simple locally-kernel function to determine the search directions and define the neighborhood of central path. Two types of full-Newton steps are used, feasibility step and centering step. The algorithm starts from strictly feasible iterates of a perturbed problem, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain strictly feasible iterates close enough to the central path of the new perturbed problem. The procedure is repeated until an ?-approximate solution is found. We analyze the algorithm and obtain the complexity bound, which coincides with the best-known result for monotone linear complementarity problems.     

Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search

In this paper, we propose a smoothing algorithm for solving the monotone symmetric cone complementarity problems (SCCP for short) with a nonmonotone line search. We show that the nonmonotone algorithm is globally convergent under an assumption that the solution set of the problem concerned is nonempty. Such an assumption is weaker than those given in most existing algorithms for solving optimization problems over symmetric cones. We also prove that the solution obtained by the algorithm is a maximally complementary solution to the monotone SCCP under some assumptions. This work was supported by National Natural Science Foundation of China (Grant Nos. 10571134, 10671010) and Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200)