Basic-set algorithm for a generalized linear complementarity problem

In this paper, the authors develop a new direct method for the solution of a BLCP, that is, a linear complementarity problem (LCP) with upper bounds, when its matrix is a symmetric or an unsymmetricP-matrix. The convergence of the algorithm is established by extending Murty's principal pivoting method to an LCP which is equivalent to the BLCP. Computational experience with large-scale BLCPs shows that the basic-set method can solve efficiently large-scale BLCPs with a symmetric or an unsymmetricP-matrix.     

Nonlinear complementarity problem and systems of convex inequalities

LetH be a nonempty closed convex subset of a topological vector spaceE andF be a real-valued function onH × H Then, we prove that, under some conditions, there existsx ₀H such thatF(x ₀,y)0 for ally H. Furthermore, we obtain a necessary and sufficient condition that a finite system of convex inequalities is irreducibly inconsistent.This work was supported in part by the Matsunaga Research Grant. The author wishes to express his sincere thanks to Professor H. Umegaki for his invaluable suggestions and advice.     

Extensions of Lemke's algorithm for the linear complementarity problem

Lemke's algorithm for the linear complementarity problem fails when a desired pivot is not blocked. A projective transformation overcomes this difficulty. The transformation is performed computationally by adjoining a new row to a schema of the problem and pivoting on the element in this row and the unit constant column. Two new algorithms result; some conditions for their success are discussed.This research was partially supported by National Science Foundation, Grant GK-42092.     

A two-stage successive overrelaxation algorithm for solving the symmetric linear complementarity problem

We propose a two-stage successive overrelaxation method (TSOR) algorithm for solving the symmetric linear complementarity problem. After the first SOR preprocessing stage this algorithm concentrates on updating a certain prescribed subset of variables which is determined by exploiting the complementarity property. We demonstrate that this algorithm successfully solves problems with up to ten thousand variables.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFSOR-86-0172 and AFSOR-86-0255 while the author was at the Computer Sciences Department at the University of Wisconsin-Madison, USA.     

On the parametric linear complementarity problem: A generalized solution procedure

This paper presents a solution procedure for the parametric linear complementarity problemIw–Mz=q+sp,w ^T z=0,w0, andz0, whereM is a positive semidefinite matrix or aP-matrix. This procedure is different from existing ones in the way it handles initialization. By exploiting special relationships between the vectorsq andp, it can reduce computational effort. Sinceq is an arbitrary vector, the procedure can be used for the ordinary linear complementarity problem. In that case, it produces pivots exactly analogous to those of Lemke's algorithm.This paper is based on the author's doctoral dissertation at Johns Hopkins University, 1977. The author wishes to thank her advisors, Professors C. S. ReVelle and D. J. Elzinga. During the last year of her graduate studies, the author held an AAUW-IBM dissertation fellowship.     

On weak generalized positive subdefinite matrices and the linear complementarity problem

In this article, we present a weaker version of the class of generalized positive subdefinite matrices introduced by Crouzeix and Komlósi [J.P. Crouzeix and S. Komlósi, The Linear Complementarity Problem and the Class of Generalized Positive Subdefinite Matrices, Applied Optimization, Vol. 59, Kluwer, Dordrecht, 2001, pp. 45–63], which is new in the literature, and obtain some properties of weak generalized positive subdefinite (WGPSBD) matrices. We show that this weaker class of matrices is also captured by row-sufficient matrices introduced by Cottle et al. [R.W. Cottle, J.S. Pang, and V. Venkateswaran, Sufficient matrices and the linear complementarity problem, Linear Algebra Appl. 114/115 (1989), pp. 231–249] and show that for WGPSBD matrices under appropriate assumptions, the solution set of a linear complementarity problem is the same as the set of Karush–Kuhn–Tucker-stationary points of the corresponding quadratic programming problem. This further extends the results obtained in an earlier paper by Neogy and Das [S.K. Neogy and A.K. Das, Some properties of generalized positive subdenite matrices, SIAM J. Matrix Anal. Appl. 27 (2006), pp. 988–995].     

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.     

Generalized equations and the generalized Newton method

We give some convergence results on the generalized Newton method (referred to by some authors as Newton's method) and the chord method when applied to generalized equations. The main results of the paper extend the classical Kantorovich results on Newton's method to (nonsmooth) generalized equations. Our results also extend earlier results on nonsmooth equations due to Eaves, Robinson, Josephy, Pang and Chan. We also propose inner-iterative schemes for the computation of the generalized Newton iterates. These schemes generalize popular iterative methods (Richardson's method, Jacobi's method and the Gauss-Seidel method) for the solution of linear equations and linear complementarity problems and are shown to be convergent under natural generalizations of classical convergence criteria. Our results are applicable to equations involving single-valued functions and also to a class of generalized equations which includes variational inequalities, nonlinear complementarity problems and some nonsmooth convex minimization problems.     

More results on the convergence of iterative methods for the symmetric linear complementarity problem

In an earlier paper, the author has given some necessary and sufficient conditions for the convergence of iterative methods for solving the linear complementarity problem. These conditions may be viewed as global in the sense that they apply to the methods regardless of the constant vector in the linear complementarity problem. More precisely, the conditions characterize a certain class of matrices for which the iterative methods will converge, in a certain sense, to a solution of the linear complementarity problem for all constant vectors. In this paper, we improve on our previous results and establish necessary and sufficient conditions for the convergence of iterative methods for solving each individual linear complementarity problem with a fixed constant vector. Unlike the earlier paper, our present analysis applies only to the symmetric linear complementarity problem. Various applications to a strictly convex quadratic program are also given.The author gratefully acknowledges several stimulating conversations with Professor O. Mangasarian on the subject of this paper. He is also grateful to a referee, who has suggested Lemma 2.2 and the present (stronger) version of Theorem 2.1 as well as several other constructive comments.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571, sponsored by the United States Army under Contract No. DAAG29-80-C-0041, and was completed while the author was visiting the Mathematics Research Center at the University of Wisconsin, Madison, Wisconsin.     

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.     

Existence and uniqueness of solutions for the generalized linear complementarity problem

Cottle and Dantzig (Ref. 1) showed that the generalized linear complementarity problem has a solution for anyqR ^m ifM is a vertical blockP-matrix of type (m ₁,...,m _n ). They also extended known characterizations of squareP-matrices to vertical blockP-matrices.Here we show, using a technique similar to Murty's (Ref. 2), that there exists a unique solution for anyqR ^m if and only ifM is a vertical blockP-matrix of type (m ₁,...,m _n ). To obtain this characterization, we employ a generalization of Tucker's theorem (Ref. 3) and a generalization of a theorem initially introduced by Gale and Nikaido (Ref. 4).     

Tolerance approach to sensitivity analysis in linear complementarity problems

In this paper, we apply the tolerance approach proposed by Wendell for sensitivity analysis in linear programs to study sensitivity analysis in linear complementarity problems. In the tolerance approach, we find the range or the maximum tolerance within which the coefficients of the right-hand side of the problem can vary simultaneously and independently such that the solution of the original and the perturbed problems have the same index set of nonzero elements.The work of the first author was completed while he was at Virginia Commonwealth University, Richmond, Virginia.     

Parallel pivotal algorithm for solving the linear complementarity problem

We propose a parallel implementation of the classical Lemke's algorithm for solving the linear complementarity problem. The algorithm is designed for a loosely coupled network of computers which is characterized by relatively high communication costs. We provide an accurate prediction of speedup based on a simple operation count. The algorithm produces speedup nearp, wherep is the number of processors, when tested on large problems as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-84-20963 and DCR-850-21228 and by Air Force Office of Scientific Research Grants AFSOR-86-0172 and AFSOR-86-0255 while the author was at the University of Wisconsin, Madison, Wisconsin.     

On the numerical solution of the linear complementarity problem

The well-known linear complementarity problem with definite matrices is considered. It is proposed to solve it using a global optimization algorithm in which one of the basic stages is a special local search. The proposed global search algorithm is tested using a variety of randomly generated problems; a detailed analysis of the computational experiment is given.     

Parallel successive overrelaxation methods for symmetric linear complementarity problems and linear programs

A parallel successive overrelaxation (SOR) method is proposed for the solution of the fundamental symmetric linear complementarity problem. Convergence is established under a relaxation factor which approaches the classical value of 2 for a loosely coupled problem. The parallel SOR approach is then applied to solve the symmetric linear complementarity problem associated with the least norm solution of a linear program.This work was sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based on research sponsored by National Science Foundation Grant DCR-84-20963 and Air Force Office of Scientific Research Grants AFOSR-ISSA-85-00080 and AFOSR-86-0172.on leave from CRAI, Rende, Cosenza, Italy.     

An inexact NE/SQP method for solving the nonlinear complementarity problem

In this paper, we present an extension to the NE/SQP method; the latter is a robust algorithm that we proposed for solving the nonlinear complementarity problem in an earlier article. In this extended version of NE/SQP, instead of exactly solving the quadratic program subproblems, approximate solutions are generated via an inexact rule.Under a proper choice for this rule, this inexact method is shown to inherit the same convergence properties of the original NE/SQP method. In addition to developing the convergence theory for the inexact method, we also present numerical results of the algorithm tested on two problems of varying size.     

Interior hybrid proximal extragradient methods for the linear monotone complementarity problem

We present new infeasible path-following methods for linear monotone complementarity problems based on Auslender, Teboulle and Ben-Tiba’s log-quadratic barrier functions. The central paths associated with these barriers are always well defined and, for those problems which have a solution, convergent to a pair of complementary solutions. Starting points in these paths are easy to compute. The theoretical iteration-complexity of these new path-following methods is derived and improved by a strategy which uses relaxed hybrid proximal-extragradient steps to control the quadratic term. Encouraging preliminary numerical experiments are presented.     

Minimum norm solution to the positive semidefinite linear complementarity problem

In this article, we present an algorithm to compute the minimum norm solution of the positive semidefinite linear complementarity problem. We show that its solution can be obtained using the alternative theorems and a convenient characterization of the solution set of a convex quadratic programming problem. This problem reduces to an unconstrained minimization problem with once differentiable convex objective function. We propose an extension of Newton's method for solving the unconstrained optimization problem. Computational results show that convergence to high accuracy often occurs in just a few iterations.     

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.     

Parallel gradient projection successive overrelaxation for symmetric linear complementarity problems and linear programs

A gradient projection successive overrelaxation (GP-SOR) algorithm is proposed for the solution of symmetric linear complementary problems and linear programs. A key distinguishing feature of this algorithm is that when appropriately parallelized, the relaxation factor interval (0, 2) isnot reduced. In a previously proposed parallel SOR scheme, the substantially reduced relaxation interval mandated by the coupling terms of the problem often led to slow convergence. The proposed parallel algorithm solves a general linear program by finding its least 2-norm solution. Efficiency of the algorithm is in the 50 to 100 percent range as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0255.