### Abstract

Original language | English |
---|---|

Pages (from-to) | 1-22 |

Number of pages | 22 |

Journal | Reports of the Faculty of Technical Mathematics and Informatics |

Volume | 98 |

Issue number | 15 |

Publication status | Published - 1998 |

### Fingerprint

### Keywords

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

### Cite this

*Reports of the Faculty of Technical Mathematics and Informatics*,

*98*(15), 1-22.

}

*Reports of the Faculty of Technical Mathematics and Informatics*, vol. 98, no. 15, pp. 1-22.

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

Research output: Contribution to journal › Article

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

JF - Reports of the Faculty of Technical Mathematics and Informatics

SN - 0922-5641

IS - 15

ER -