# A strongly polynomial rounding procedure yielding a maximally complementary solution for P(*)(k) linear complementarity problems

T. Illés, J. Peng, C. Roos, T. Terlaky

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

## 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.
Original language English 1-22 22 Reports of the Faculty of Technical Mathematics and Informatics 98 15 Published - 1998

## Keywords

• linear complementarity problem
• error bounds on the size of the variables
• optimal partition
• maximally complementary solution
• rounding procedure

## Fingerprint

Dive into the research topics of 'A strongly polynomial rounding procedure yielding a maximally complementary solution for P(*)(k) linear complementarity problems'. Together they form a unique fingerprint.