Polynomial affine-scaling algorithms for P*(k) linear complementary problems

Tibor Illes; Cornelis Roos; Tamás Terlaky

doi:10.1007/978-3-642-59073-3_9

Polynomial affine-scaling algorithms for P*(k) linear complementary problems

Tibor Illes, Cornelis Roos, Tamás Terlaky

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

Abstract

A family of primal-dual affine-scaling algorithms is presented for Linear Complementarity Problems (LCP's) with P*-matrices. These algorithms were first introduced by Jansen et al. for solving linear optimization problems and later also applied to LCP's with positive semidefinite matrices. We show that the same algorithmic concept applies to LCP's with P*-matrices and that the resulting algorithms admit polynomial-time iteration bounds.

Original language	English
Title of host publication	Recent Advances in Optimization
Subtitle of host publication	Proceedings of the 8th French-German Conference on Optimization Trier, July 21–26, 1996
Pages	119-137
Number of pages	19
Volume	452
DOIs	https://doi.org/10.1007/978-3-642-59073-3_9
Publication status	Published - 1997
Externally published	Yes

Publication series

Name	Lecture Notes in Economics and Mathematical Systems
Publisher	Springer Berlin Heidelberg
Volume	452
ISSN (Print)	0075-8442

Keywords

linear complementary problems
matrices
affine scaling method
affine-scaling algorithms

Access to Document

10.1007/978-3-642-59073-3_9

Cite this

Illes, T., Roos, C., & Terlaky, T. (1997). Polynomial affine-scaling algorithms for P*(k) linear complementary problems. In Recent Advances in Optimization: Proceedings of the 8th French-German Conference on Optimization Trier, July 21–26, 1996 (Vol. 452, pp. 119-137). (Lecture Notes in Economics and Mathematical Systems; Vol. 452). https://doi.org/10.1007/978-3-642-59073-3_9

@inproceedings{b59d7fea82ce4e65bcc996ef56a12f85,

title = "Polynomial affine-scaling algorithms for P*(k) linear complementary problems",

abstract = "A family of primal-dual affine-scaling algorithms is presented for Linear Complementarity Problems (LCP's) with P*-matrices. These algorithms were first introduced by Jansen et al. for solving linear optimization problems and later also applied to LCP's with positive semidefinite matrices. We show that the same algorithmic concept applies to LCP's with P*-matrices and that the resulting algorithms admit polynomial-time iteration bounds.",

keywords = "linear complementary problems, matrices, affine scaling method, affine-scaling algorithms",

author = "Tibor Illes and Cornelis Roos and Tam{\'a}s Terlaky",

year = "1997",

doi = "10.1007/978-3-642-59073-3_9",

language = "English",

isbn = "978-3-540-63022-7",

volume = "452",

series = "Lecture Notes in Economics and Mathematical Systems",

publisher = "Springer Berlin Heidelberg",

pages = "119--137",

booktitle = "Recent Advances in Optimization",

}

Illes, T, Roos, C & Terlaky, T 1997, Polynomial affine-scaling algorithms for P*(k) linear complementary problems. in Recent Advances in Optimization: Proceedings of the 8th French-German Conference on Optimization Trier, July 21–26, 1996. vol. 452, Lecture Notes in Economics and Mathematical Systems, vol. 452, pp. 119-137. https://doi.org/10.1007/978-3-642-59073-3_9

Polynomial affine-scaling algorithms for P*(k) linear complementary problems. / Illes, Tibor; Roos, Cornelis; Terlaky, Tamás.
Recent Advances in Optimization: Proceedings of the 8th French-German Conference on Optimization Trier, July 21–26, 1996. Vol. 452 1997. p. 119-137 (Lecture Notes in Economics and Mathematical Systems; Vol. 452).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

TY - GEN

T1 - Polynomial affine-scaling algorithms for P*(k) linear complementary problems

AU - Illes, Tibor

AU - Roos, Cornelis

AU - Terlaky, Tamás

PY - 1997

Y1 - 1997

N2 - A family of primal-dual affine-scaling algorithms is presented for Linear Complementarity Problems (LCP's) with P*-matrices. These algorithms were first introduced by Jansen et al. for solving linear optimization problems and later also applied to LCP's with positive semidefinite matrices. We show that the same algorithmic concept applies to LCP's with P*-matrices and that the resulting algorithms admit polynomial-time iteration bounds.

AB - A family of primal-dual affine-scaling algorithms is presented for Linear Complementarity Problems (LCP's) with P*-matrices. These algorithms were first introduced by Jansen et al. for solving linear optimization problems and later also applied to LCP's with positive semidefinite matrices. We show that the same algorithmic concept applies to LCP's with P*-matrices and that the resulting algorithms admit polynomial-time iteration bounds.

KW - linear complementary problems

KW - matrices

KW - affine scaling method

KW - affine-scaling algorithms

U2 - 10.1007/978-3-642-59073-3_9

DO - 10.1007/978-3-642-59073-3_9

M3 - Conference contribution book

SN - 978-3-540-63022-7

VL - 452

T3 - Lecture Notes in Economics and Mathematical Systems

SP - 119

EP - 137

BT - Recent Advances in Optimization

ER -

Polynomial affine-scaling algorithms for P*(k) linear complementary problems

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this