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

Tibor Illés, Jiming Peng, Cornelis Roos, Tamás Terlaky

Research output: Contribution to journal › Article

24 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 O(1), O(mu), and O(root 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 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)320-340
Number of pages21
JournalSIAM Journal on Optimization
Volume11
Issue number2
DOIs
Publication statusPublished - 27 Sep 2000
Externally publishedYes

Fingerprint

Central Path
Linear Complementarity Problem
Rounding
Polynomials
Polynomial
Interior Point Method
Complementarity
Preparation
Polynomial time
Rate of Convergence
Exact Solution
Roots
Converge
Imply

Keywords

  • linear complementarity problems
  • P∗(κ) matrices
  • error bounds on the size of the variables
  • optimal partition
  • maximally complementary solution
  • rounding procedure

Cite this

Illés, Tibor ; Peng, Jiming ; Roos, Cornelis ; Terlaky, Tamás. / A strongly polynomial rounding procedure yielding a maximally complementary solution for P(*)(k) linear complementarity problems. In: SIAM Journal on Optimization. 2000 ; Vol. 11, No. 2. pp. 320-340.
@article{90f0e064f29742b1bcce06bb2b809806,
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 O(1), O(mu), and O(root 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 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 problems, P∗(κ) matrices, error bounds on the size of the variables, optimal partition, maximally complementary solution, rounding procedure",
author = "Tibor Ill{\'e}s and Jiming Peng and Cornelis Roos and Tam{\'a}s Terlaky",
year = "2000",
month = "9",
day = "27",
doi = "10.1137/S1052623498336590",
language = "English",
volume = "11",
pages = "320--340",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
number = "2",

}

Illés, T, Peng, J, Roos, C & Terlaky, T 2000, 'A strongly polynomial rounding procedure yielding a maximally complementary solution for P(*)(k) linear complementarity problems', SIAM Journal on Optimization, vol. 11, no. 2, pp. 320-340. https://doi.org/10.1137/S1052623498336590

A strongly polynomial rounding procedure yielding a maximally complementary solution for P(*)(k) linear complementarity problems. / Illés, Tibor; Peng, Jiming; Roos, Cornelis; Terlaky, Tamás.

In: SIAM Journal on Optimization, Vol. 11, No. 2, 27.09.2000, p. 320-340.

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, Tibor

AU - Peng, Jiming

AU - Roos, Cornelis

AU - Terlaky, Tamás

PY - 2000/9/27

Y1 - 2000/9/27

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 O(1), O(mu), and O(root 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 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 O(1), O(mu), and O(root 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 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 problems

KW - P∗(κ) matrices

KW - error bounds on the size of the variables

KW - optimal partition

KW - maximally complementary solution

KW - rounding procedure

U2 - 10.1137/S1052623498336590

DO - 10.1137/S1052623498336590

M3 - Article

VL - 11

SP - 320

EP - 340

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 2

ER -

Illés T, Peng J, Roos C, Terlaky T. A strongly polynomial rounding procedure yielding a maximally complementary solution for P(*)(k) linear complementarity problems. SIAM Journal on Optimization. 2000 Sep 27;11(2):320-340. https://doi.org/10.1137/S1052623498336590

Access to Document