A new pivoting algorithm for the linear complementarity problem allowing for an arbitrary starting point

The linear complementarity problem is to find nonnegative vectors which are affinely related and complementary. In this paper we propose a new complementary pivoting algorithm for solving the linear complementarity problem as a more efficient alternative to the algorithms proposed by Lemke and by Talman and Van der Heyden. The algorithm can start at an arbitrary nonnegative vector and converges under the same conditions as Lemke's algorithm.This research is part of the VF-program Competition and Cooperation.     

Simplicial approximation of solutions to the nonlinear complementarity problem with lower and upper bounds

Ideas of a simplicial variable dimension restart algorithm to approximate zero points onR ⁿ developed by the authors and of a linear complementarity problem pivoting algorithm are combined to an algorithm for solving the nonlinear complementarity problem with lower and upper bounds. The algorithm can be considered as a modification of the2n-ray zero point finding algorithm onR ⁿ . It appears that for the new algorithm the number of linear programming pivot steps is typically less than for the2n-ray algorithm applied to an equivalent zero point problem. This is caused by the fact that the algorithm utilizes the complementarity conditions on the variables. This work is part of the VF-program “Equilibrium and Disequilibrium in Demand and Supply,” which has been approved by the Netherlands Ministry of Education and Sciences.     

New improved error bounds for the linear complementarity problem

New local and global error bounds are given for both nonmonotone and monotone linear complementarity problems. Comparisons of various residuals used in these error bounds are given. A possible candidate for a best error bound emerges from our comparisons as the sum of two natural residuals.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grant CCR-9101801.     

On a “stability” in the linear complementarity problem

In this work we re-wrote the Linear Complementarity Problem in a formulation based on unknown projector operators. In particular, this formulation allows the introduction of a concept of “stability” that, in a certain way, might explain the way block pivotal algorithm performs.     

An O(n 3 L) adaptive path following algorithm for a linear complementarity problem

In this paper we propose an O(n ³ L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n ³ L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n ³ L).Research supported in part by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research supported in part by NSF grants ECS-8602534 and DMS-8904406 and ONR contract N-00014-87-K0212.     

Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem

This paper deals with the LCP (linear complementarity problem) with a positive semi-definite matrix. Assuming that a strictly positive feasible solution of the LCP is available, we propose ellipsoids each of which contains all the solutions of the LCP. We use such an ellipsoid for computing a lower bound and an upper bound for each coordinate of the solutions of the LCP. We can apply the lower bound to test whether a given variable is positive over the solution set of the LCP. That is, if the lower bound is positive, we know that the variable is positive over the solution set of the LCP; hence, by the complementarity condition, its complement is zero. In this case we can eliminate the variable and its complement from the LCP. We also show how we efficiently combine the ellipsoid method for computing bounds for the solution set with the path-following algorithm proposed by the authors for the LCP. If the LCP has a unique non-degenerate solution, the lower bound and the upper bound for the solution, computed at each iteration of the path-following algorithm, both converge to the solution of the LCP.Supported by Grant-in-Aids for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Young Scientists (63730014) and for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.     

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.     

GAUSSIAN PIVOTING METHOD FORSOLVING LINEAR COMPLEMENTARITY PROBLEM

In this paper, a new direct algorithm for solving linear complementarity problem with Z-matrix is proposed. The algorithm exhibits either a solution or its nonexistence after at most n steps (where n is the dimension of the problem) and the computational complexity is at most 1/3n^2 O(n^2)     

A polynomial-time algorithm for a class of linear complementarity problems

Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x 0,y 0,x _i y _i = 0 (i = 1, 2,,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n ³ L) arithmetic operations by tracing the path of centers,{(x, y) S: x _i y _i = (i = 1, 2,,n) for some > 0} of the feasible regionS = {(x, y) 0:y = Mx + q}, whereL denotes the size of the input data of the problem.     

The largest step path following algorithm for monotone linear complementarity problems

Path-following algorithms take at each iteration a Newton step for approaching a point on the central path, in such a way that all the iterates remain in a given neighborhood of that path. This paper studies the case in which each iteration uses a pure Newton step with the largest possible reduction in complementarity measure (duality gap). This algorithm is known to converge superlinearly in objective values. We show that with the addition of a computationally trivial safeguard it achieves Q-quadratic convergence, and show that this behaviour cannot be proved by usual techniques for the original method. Research done while visiting Delft University of Technology, and supported in part by CAPES-Brazil.     

Continuous linear complementarity problem

We investigate a form of linear complementarity problem posed over a space of measures onX, where the matrix which occurs in the finite-dimensional linear complementarity problem is replaced by a continuous functionM(x, y),x,yX. We give a number of conditions which ensure the existence of solutions, and we discuss the extension of Lemke's algorithm to this problem.     

On the identification of degenerate indices in the nonlinear complementarity problem with the proximal point algorithm

In this paper we focus on the problem of identifying the index sets P(x):=i|x_i>0, N(x):={i|F_i(x)>0 and C(x):=i|x_i=F_i(x)=0} for a solution x of the monotone nonlinear complementarity problem NCP(F). The correct identification of these sets is important from both theoretical and practical points of view. Such an identification enables us to remove complementarity conditions from the NCP and locally reduce the NCP to a system which can be dealt with more easily. We present a new technique that utilizes a sequence generated by the proximal point algorithm (PPA). Using the superlinear convergence property of PPA, we show that the proposed technique can identify the correct index sets without assuming the nondegeneracy and the local uniqueness of the solution.This work was supported in part by a Grant-in-Aid for Scientific Research from the Ministry of Education, Science, Sports and Culture of Japan.Mathematics Subject Classification (2000): 90C33, 65K10     

On the modulus algorithm for the linear complementarity problem

Concerning three subclasses of P-matrices the modulus algorithm and the projected successive overrelaxation (PSOR) method solving the linear complementarity problem are compared to each other with respect to convergence. It is shown that the modulus algorithm is convergent for all three subclasses whereas the convergence of the PSOR method is only guaranteed for two of them.     

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.     

On computer-assisted proofs for solutions of linear complementarity problems

In this paper we consider the linear complementarity problem where the components of the input data M and q are not exactly known but can be enclosed in intervals. We compare three tests to each other each of which can be used by a computer that supports interval arithmetic to give guaranteed bounds for a solution of the LCP defined by M and q.     

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.     

Asynchronous parallel successive overrelaxation for the symmetric linear complementarity problem

Convergence is established for asynchronous parallel successive overrelaxation (SOR) algorithms for the symmetric linear complementarity problem. For the case of a strictly diagonally dominant matrix convergence is achieved for a relaxation factor interval of (0, 2] with line search, and (0, 1] without line search. Computational tests on the Sequent Symmetry S81 multiprocessor give speedup efficiency in the 43%–91% range for the cases for which convergence is established. The tests also show superiority of the asynchronous SOR algorithms over their synchronous counterparts.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grant AFOSR-86-0172.     

Error bounds for monotone linear complementarity problems

We give a bound on the distance between an arbitrary point and the solution set of a monotone linear complementarity problem in terms of a condition constant that depends on the problem data only and a residual function of the violations of the complementary problem conditions by the point considered. When the point satisfies the linear inequalities of the complementarity problem, the residual consists of the complementarity condition plus its square root. This latter term is essential and without it the error bound cannot hold. We also show that another natural residual that has been employed to bound errors for strictly monotone linear complementarity problems fails to bound errors for the monotone case considered here. Sponsored by the United States Army under contract No. DAAG29-80-C-0041. This material is based on research sponsored by National Foundation Grant DCR-8420963 and Air Force Office of Scientific Research Grant AFOSR-ISSA-85-00080.     

An improvement of the error bounds for linear complementarity problems of Nekrasov matrices

A new error bound for the linear complementarity problems, which involves a parameter, is given when the involved matrices are Nekrasov matrices. It is shown that there exists an optimal value of the parameter such that the new bound is sharper than that provided by Li et al. (Numer Algor. 2017;74:997–1009). Numerical examples are given to illustrate the corresponding results.     

Superfluous matrices in linear complementarity

Superfluous matrices were introduced by Howe (1983) in linear complementarity. In general, producing examples of this class is tedious (a few examples can be found in Chapter 6 of Cottle, Pang and Stone (1992)). To overcome this problem, we define a new class of matrices and establish that in superfluous matrices of any ordern 4 can easily be constructed. For every integerk, an example of a superfluous matrix of degreek is exhibited in the end.