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

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