Computational complexity of LCPs associated with positive definite symmetric matrices

Murty in a recent paper has shown that the computational effort required to solve a linear complementarity problem (LCP), by either of the two well known complementary pivot methods is not bounded above by a polynomial in the size of the problem. In that paper, by constructing a class of LCPs—one of ordern forn 2—he has shown that to solve the problem of ordern, either of the two methods goes through 2 ⁿ pivot steps before termination.However that paper leaves it as an open question to show whether or not the same property holds if the matrix,M, in the LCP is positive definite and symmetric. The class of LCPs in whichM is positive definite and symmetric is of particular interest because of the special structure of the problems, and also because they appear in many practical applications.In this paper, we study the computational growth of each of the two methods to solve the LCP, (q, M), whenM is positive definite and symmetric and obtain similar results.This research is partially supported by Air Force Office of Scientific Research, Air Force Number AFOSR-78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation thereon.     

On the uniqueness of solutions to linear complementarity problems

This paper characterizes the classU of all realn×n matricesM for which the linear complementarity problem (q, M) has a unique solution for all realn-vectorsq interior to the coneK(M) of vectors for which (q, M) has any solution at all. It is shown that restricting the uniqueness property to the interior ofK(M) is necessary because whenU, the problem (q, M) has infinitely many solutions ifq belongs to the boundary of intK(M). It is shown thatM must have nonnegative principal minors whenU andK(M) is convex. Finally, it is shown that whenM has nonnegative principal minors, only one of which is 0, andK(M)≠R ⁿ , thenU andK(M) is a closed half-space.     

A note on an open problem in linear complementarity

LetK be the class ofn × n matricesM such that for everyn-vectorq for which the linear complementarity problem (q, M) is feasible, then the problem (q, M) has a solution. Recently, a characterization ofK has been obtained by Mangasarian [5] in his study of solving linear complementarity problems as linear programs. This note proves a result which improves on such a characterization.Research sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MCS75-17385.     

A critical index algorithm for nearest point problems on simplicial cones

We consider the linear complementarity problem (q, M) in whichM is a positive definite symmetric matrix of ordern. This problem is equivalent to a nearest point problem [; b] in which = {A.₁,, A. _n } is a basis for R ⁿ ,b is a given point in R ⁿ ; and it is required to find the nearest point in the simplicial cone Pos() tob. We develop an algorithm for solving the linear complementarity problem (q, M) or the equivalent nearest point problem [; b]. Computational experience in comparison with an existing algorithm is presented.Research effort partially supported by the Air Force Office of Scientific Research. Air Force Systems Command, USAF, under grant No. AFOSR 78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes, not withstanding any copyright notation hereon.     

NP-Completeness of the linear complementarity problem

We consider the linear complementarity problem (q, M) for which the data are the integer column vectorq εR ⁿ and the integer square matrixM of ordern. GLCP is the decision problem: Does (q, M) have a solution? We show that GLCP is NP-complete in the strong sense.     

New multiplier method for solving linear complementarity problems

A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. By introducing a Lagrangian of LCP(q, M), a new smooth merit function ϑ(x, λ) for LCP(q, M) is constructed. Based on it, a simple damped Newton-type algorithm with multiplier self-adjusting step is presented. When M is a P-matrix, the sequence {ϑ(x ^k, λ ^k)} (where {(x ^k, λ ^k)} is generated by the algorithm) is globally linearly convergent to zero and convergent in a finite number of iterations if the solution is degenerate. Numerical results suggest that the method is highly efficient and promising. Selected from Numerical Mathematics (A Journal of Chinese Universities), 2004, 26(2): 162–171     

Solution of symmetric linear complementarity problems by iterative methods

A unified treatment is given for iterative algorithms for the solution of the symmetric linear complementarity problem: $$Mx + q \geqslant 0, x \geqslant 0, x^T (Mx + q) = 0$$ , whereM is a givenn×n symmetric real matrix andq is a givenn×1 vector. A general algorithm is proposed in which relaxation may be performed both before and after projection on the nonnegative orthant. The algorithm includes, as special cases, extensions of the Jacobi, Gauss-Seidel, and nonsymmetric and symmetric successive over-relaxation methods for solving the symmetric linear complementarity problem. It is shown first that any accumulation point of the iterates generated by the general algorithm solves the linear complementarity problem. It is then shown that a class of matrices, for which the existence of an accumulation point that solves the linear complementarity problem is guaranteed, includes symmetric copositive plus matrices which satisfy a qualification of the type: $$Mx + q > 0 for some x in R^n $$ . Also included are symmetric positive-semidefinite matrices satisfying this qualification, symmetric, strictly copositive matrices, and symmetric positive matrices. Furthermore, whenM is symmetric, copositive plus, and has nonzero principal subdeterminants, it is shown that the entire sequence of iterates converges to a solution of the linear complementarity problem.     

The generalized linear complementarity problem revisited

Given a vertical block matrixA, we consider in this paper the generalized linear complementarity problem VLCP(q, A) introduced by Cottle and Dantzig. We formulate this problem as a linear complementarity problem with a square matrixM, a formulation which is different from a similar formulation given earlier by Lemke. Our formulation helps in extending many well-known results in linear complementarity to the generalized linear complementarity problem. We also show that the class of vertical block matrices which Cottle and Dantzig's algorithm can process is the same as the class of equivalent square matrices which Lemke's algorithm can process. We also present some degree-theoretic results on a vertical block matrix.     

A strongly polynomial algorithm for the transportation problem

For the (linear) transportation problem withm supply nodes,n demand nodes andk feasible arcs we describe an algorithm which runs in time proportional tom logm(k + n logn) (assuming w.l.o.g.mn). The algorithm uses excess scaling. The complexity bound is a slight improvement over the bound achieved by an application of a min-cost-flow algorithm of Orlin to the transportation problem.Corresponding author. Research supported in part by grant no. I-84-095.06/88 of the German—Israeli-Foundation for Scientific Research and Development.     

A note on a characterization of P-matrices

In this note we show that the characterization results for P-matrices due to K.G. Murty and A. Tamir which state that a given square matrixM of ordern is a P-matrix if and only if the linear complementarity problem (q, M) has a unique solution for allq in a specified finite subset of ⁿ depending onM are incorrect whenn > 3.Research supported by Dr. K.S. Krishnan (DAE) fellowship for research in Mathematics and Computer Science, Bombay, India.     

Linear Extensions of Semiorders: II

Let M _n (k) denote the family of posets on n points with k ordered pairs that maximize the number of linear extensions among all such posets. Fishburn and Trotter [2] prove that every poset in M _n (k) is a semiorder and identifies all semiorders in M _n (k) for k n. The present paper specifies M _n (k) for all k 2 n – 3.     

Degeneracy in linear complementarity problems: a survey

Given a square matrixM of ordern and a vectorq ⁿ , the linear complementarity problem is the problem of either finding aw ⁿ and az ⁿ such thatw–Mz=q,w0,z0 andw ^T z=0 or showing that no such (w, z) exists. This problem is denoted asLCP(q, M). We say that a solution (w, z) toLCP(q, M) is degenerate if the number of positive coordinates in (w, z) is less thann. As in linear programming, degeneracy may cause cycling in an adjacent vertex following methods like Lemke's algorithm. Moreover, ifLCP(0,M) has a nontrivial solution, a condition related to degeneracy, then unless certain other conditions are satisfied, the algorithm may not be able to decide about the solvability of the givenLCP(q, M). In this paper we review the literature on the implications of degeneracy to the linear complementarity theory.     

On Generators of the Tame Automorphism Group of Free Metabelian Lie Algebras

We prove that the tame automorphism group TAut(M _n ) of a free metabelian Lie algebra M _n in n variables over a field k is generated by a single nonlinear automorphism modulo all linear automorphisms if n ≥ 4 except the case when n = 4 and char(k) ≠ 3. If char(k) = 3, then TAut(M ₄) is generated by two automorphisms modulo all linear automorphisms. We also prove that the tame automorphism group TAut(M ₃) cannot be generated by any finite number of automorphisms modulo all linear automorphisms.     

Constructive proofs of theorems relating to:F(x) = y,with applications

Some theorems are given which relate to approximating and establishing the existence of solutions to systemsF(x) = y ofn equations inn unknowns, for variousy, in a region of euclideann-space E ⁿ . They generalize known theorems.Viewing complementarity problems and fixed-point problems as examples, known results or generalizations of known results are obtained.A familiar use is made of homotopies H: E ⁿ × [0, 1]E ⁿ of the formH(x, t) = (1 –t)F ⁰ (x) + t[F(x) – y] where theF ⁰ in this paper is taken to be linear. Simplicial subdivisionsT ^k of E ⁿ × [0, 1] furnish piecewise linear approximatesG ^k toH. The basic computation is via the generation of piecewise linear curvesP ^k which satisfyG ^k (x, t) = 0. Visualizing a sequence {T ^k } of such subdivisions, with mesh size going to zero, arguments are made on connected, compact limiting curvesP on whichH(x, t) = 0.This paper builds upon and continues recent work of C.B. Garcia.The authors respectively: A. Charnes, research partially supported by Proj. No. NR047-021 Contract N00014-75-C-0269; C.B. Garcia, C.E. Lemke, research partially supported by NSF Grant No. MPS75-09443.     

A method for solving the general parametric linear complementarity problem

This paper presents a solution method for the general (mixed integer) parametric linear complementarity problem pLCP(q(θ),M), where the matrix M has a general structure and integrality restriction can be enforced on the solution. Based on the equivalence between the linear complementarity problem and mixed integer feasibility problem, we propose a mixed integer programming formulation with an objective of finding the minimum 1-norm solution for the original linear complementarity problem. The parametric linear complementarity problem is then formulated as multiparametric mixed integer programming problem, which is solved using a multiparametric programming algorithm. The proposed method is illustrated through a number of examples.     

A finite characterization ofK-matrices in dimensions less than four

The class of realn × n matricesM, known asK-matrices, for which the linear complementarity problemw – Mz = q, w 0, z 0, w ^T z =0 has a solution wheneverw – Mz =q, w 0, z 0 has a solution is characterized for dimensionsn <4. The characterization is finite and practical. Several necessary conditions, sufficient conditions, and counterexamples pertaining toK-matrices are also given. A finite characterization of completelyK-matrices (K-matrices all of whose principal submatrices are alsoK-matrices) is proved for dimensions <4.Partially supported by NSF Grant MCS-8207217.Research partially supported by NSF Grant No. ECS-8401081.     

A set intersection theorem and applications

Using Scarf's algorithm for “computing” a fixed point of a continuous mapping, the following is proved: LetM ₁ ? M _n be closed sets inR ⁿ which cover the standard simplexS, so thatM _i coversS _i , the face ofS opposite vertexi. We say a point inS iscompletely labeled if it belongs to everyM _i andk-almost-completely labeled if it belongs to all butM _k . Then there exists a closed setT ofk-almost-completely labeled points which connects vertexk with some completely labeled point. This result is used to prove Browder's theorem (a parametric fixed-point theorem) inR ⁿ . It is also used to generate “algorithms” for the nonlinear complementarity problem which are analogous to the Lemke—Howson algorithm and the Cottle—Dantzig algorithm, respectively, for the linear complementarity problem.     

Intersection of Isomorphic Linear Codes

Given an (n, k) linear code over GF(q), the intersection of with a codeπ( ), whereπS_n, is an (n, k₁) code, where max{0, 2k−n}k₁k. The intersection problem is to determine which integers in this range are attainable for a given code . We show that, depending on the structure of the generator matrix of the code, some of the values in this range are attainable. As a consequence we give a complete solution to the intersection problem for most of the interesting linear codes, e.g. cyclic codes, Reed–Muller codes, and most MDS codes.     

Locally homogeneous Riemannian manifolds and Cartan triples

Ann-dimensional Cartan triple is a triple (g, , ) consisting of a Lie subalgebra g of so(n) (endowed with the Killing form), a linear map : ⁿ g and a bilinear antisymmetric map ²( ⁿ , g), which together satisfy (1.25)–(1.28) of Section 1. LetM _n be the set ofmaximal n-dimensional Cartan triples, and letA _n be thenatural action of the orthogonal group O(n) onM _n (Section 3). One shows that there is a bijective mapping from the set of local isometry classes ofn-dimensional locally homogeneous Riemannian manifolds to the set of orbits ofA _n (Theorem 3.1(a)). Under this bijection, the classes of homogeneous Riemannian manifolds correspond to orbits ofclosed Cartan triples.     

Fundamental Groups of Closed Manifolds with Positive Curvature and Torus Actions

We determine the fundamental group of a closed n-manifold of positive sectional curvature on which a torus T^k (k large) acts effectively and isometrically. Our results are: (A) If k>(n − 3)/4 and n ≥ 17, then the fundamental group π₁(M) is isomorphic to the fundamental group of a spherical 3-space form. (B) If k ≥ (n/6)+1 and n≠ 11, 15, 23, then any abelian subgroup of π₁(M) is cyclic. Moreover, if the T^k-fixed point set is empty, then π₁(M) is isomorphic to the fundamental group of a spherical 3-space form.Mathematics Subject Classification (2000). 53-XX*Supported partially by NSF Grant DMS 0203164 and by a reach found from Beijing normal university.**Supported partially by NSFC 10371008.