A class of linear complementarity problems solvable in polynomial time

DOI10.1016/0024-3795(91)90264-WzbMath0742.65054MaRDI QIDQ1174838

Panos M. Pardalos, Yinyu Ye

Publication date: 25 June 1992

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

quadratic programming; linear complementarity problems; polynomial complexity; potential reduction algorithm

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C20: Quadratic programming

90C33: Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)

Related Items

A long-step barrier method for convex quadratic programming, Interior-point algorithms for global optimization, The linear complementarity problem, sufficient matrices, and the criss- cross method, Enumeration approach for linear complementarity problems based on a reformulation-linearization technique, On the solution and complexity of a generalized linear complementarity problem, Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems, Solution of finite-dimensional variational inequalities using smooth optimization with simple bounds, Two interior-point methods for nonlinear \(P_*(\tau)\)-complementarity problems., An interior point potential reduction method for constrained equations, A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem, An investigation of interior-point and block pivoting algorithms for large-scale symmetric monotone linear complementarity problems, Enhanced intersection cutting-plane approach for linear complementarity problems, Iteration complexity of an interior-point algorithm for nonlinear p∗-complementarity problems

Cites Work

• Unnamed Item
• Error bounds for the linear complementarity problem with a P-matrix
• An extension of Karmarkar's projective algorithm for convex quadratic programming
• Sufficient matrices and the linear complementarity problem
• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• An interior point potential reduction algorithm for the linear complementarity problem
• On the number of solutions to the complementarity problem and spanning properties of complementary cones
• A Centered Projective Algorithm for Linear Programming
• Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
• Linear complementarity problems solvable by A single linear program
• Some classes of matrices in linear complementarity theory
• A Characterization of the Constant Parity Property of the Number of Solutions to the Linear Complementarity Problem
• The Linear Complementarity Problem
• Polyhedral sets having a least element