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

4 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.
LanguageEnglish
Pages1-22
Number of pages22
JournalReports of the Faculty of Technical Mathematics and Informatics
Volume98
Issue number15
Publication statusPublished - 1998

Fingerprint

Linear complementarity problem
Polynomials
Preparation
Rate of convergence
Complementarity
Exact solution
Interior point method

Keywords

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

Cite this

@article{b5d02794fb454959a8856c09dfb59fdc,
title = "A strongly polynomial rounding procedure yielding a maximally complementary solution for P(*)(k) linear complementarity problems",
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 = "linear complementarity problem, error bounds on the size of the variables, optimal partition, maximally complementary solution, rounding procedure",
author = "T. Ill{\'e}s and J. Peng and C. Roos and T. Terlaky",
year = "1998",
language = "English",
volume = "98",
pages = "1--22",
journal = "Reports of the Faculty of Technical Mathematics and Informatics",
issn = "0922-5641",
number = "15",

}

A strongly polynomial rounding procedure yielding a maximally complementary solution for P(*)(k) linear complementarity problems. / Illés, T.; Peng, J.; Roos, C.; Terlaky, T.

In: Reports of the Faculty of Technical Mathematics and Informatics, Vol. 98, No. 15, 1998, p. 1-22.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Illés, T.

AU - Peng, J.

AU - Roos, C.

AU - Terlaky, T.

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

KW - linear complementarity problem

KW - error bounds on the size of the variables

KW - optimal partition

KW - maximally complementary solution

KW - rounding procedure

UR - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.9230&rep=rep1&type=pdf

M3 - Article

VL - 98

SP - 1

EP - 22

JO - Reports of the Faculty of Technical Mathematics and Informatics

T2 - Reports of the Faculty of Technical Mathematics and Informatics

JF - Reports of the Faculty of Technical Mathematics and Informatics

SN - 0922-5641

IS - 15

ER -