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

Tibor Illes, Cornelis Roos, Tamás Terlaky

Research output: Chapter in Book/Report/Conference proceedingConference 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.
LanguageEnglish
Title of host publicationRecent Advances in Optimization
Subtitle of host publicationProceedings of the 8th French-German Conference on Optimization Trier, July 21–26, 1996
Pages119-137
Number of pages19
Volume452
DOIs
Publication statusPublished - 1997
Externally publishedYes

Publication series

NameLecture Notes in Economics and Mathematical Systems
PublisherSpringer Berlin Heidelberg
Volume452
ISSN (Print)0075-8442

Fingerprint

Affine Scaling
Linear Complementarity Problem
P-matrix
Polynomial
Positive Semidefinite Matrix
Linear Optimization
Primal-dual
Polynomial-time Algorithm
Optimization Problem
Iteration
Scaling
Linear complementarity problem
Polynomials

Keywords

  • linear complementary problems
  • matrices
  • affine scaling method
  • affine-scaling algorithms

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

Illes T, Roos C, Terlaky T. 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. 1997. p. 119-137. (Lecture Notes in Economics and Mathematical Systems). https://doi.org/10.1007/978-3-642-59073-3_9