A Strongly Polynomial Rounding Procedure Yielding a Maximally Complementary Solution for $P_*(\kappa)$ Linear Complementarity Problems
Authors:
- Tibor IllésTITibor Illés
- Jiming PengJPJiming Peng
- Cornelis RoosCRCornelis Roos
- Tamás TerlakyTTTamás Terlaky
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 11 (2) , 320-340
Abstract
We deal with linear complementarity problems (LCPs) with $P_*(\kappa)$ matrices. First we establish the convergence rate of the complementary variables along the central path. The central path is parameterized by the barrier parameter $\mu$, as usual. Our elementary proof reproduces the known result that the variables on or close to the central path fall apart in three classes in which these variables are ${\cal O}(1), {\cal O}(\mu),$ and ${\cal O}(\sqrt{\mu})$, respectively. The constants hidden in these bounds are expressed in or bounded by the input data. All this is preparation for our main result: a strongly polynomial rounding procedure. Given a point with sufficiently small complementarity gap and which is close enough to the central path, the rounding procedure produces a maximally complementary solution in at most ${\cal O} (n^3)$ arithmetic operations. The result implies that interior point methods (IPMs) not only converge to a complementary solution of $P_*(\kappa)$ LCPs, but, when furnished with our rounding procedure, they can also produce a maximally complementary (exact) solution in polynomial time.
Keywords
This publication has 28 references indexed in Scilit:
- Basis- and partition identification for quadratic programming and linear complementarity problemsMathematical Programming, 1999
- P*-Matrices Are Just SufficientLinear Algebra and its Applications, 1996
- Condition numbers for polyhedra with real number dataOperations Research Letters, 1995
- A predictor-corrector method for solving the P*(k)-matrix lcp from infeasible starting pointsOptimization Methods and Software, 1995
- Local convergence of interior-point algorithms for degenerate monotone LCPComputational Optimization and Applications, 1994
- The linear complimentarity problem, sufficient matrices, and the criss-cross methodLinear Algebra and its Applications, 1993
- A class of linear complementarity problems solvable in polynomial timeLinear Algebra and its Applications, 1991
- Sufficient matrices and the linear complementarity problemLinear Algebra and its Applications, 1989
- Lipschitz Continuity of Solutions of Linear Inequalities, Programs and Complementarity ProblemsSIAM Journal on Control and Optimization, 1987
- Some continuity properties of polyhedral multifunctions1981