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 journalArticle

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 languageEnglish
Pages (from-to)1-22
Number of pages22
JournalReports of the Faculty of Technical Mathematics and Informatics
Volume98
Issue number15
Publication statusPublished - 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.

Cite this