A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems

1991
ISBN: 978-3-540-54509-5
Verlag: Springer Berlin Heidelberg

Buch, Englisch, Band 538, 112 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 195 g

Reihe: Lecture Notes in Computer Science

Following Karmarkar's 1984 linear programming algorithm,
numerous interior-point algorithms have been proposed for
various mathematical programming problems such as linear
programming, convex quadratic programming and convex
programming in general. This monograph presents a study of
interior-point algorithms for the linear complementarity
problem (LCP) which is known as a mathematical model for
primal-dual pairs of linear programs and convex quadratic
programs. A large family of potential reduction algorithms
is presented in a unified way for the class of LCPs where
the underlying matrix has nonnegative principal minors
(P0-matrix). This class includes various important
subclasses such as positive semi-definite matrices,
P-matrices, P*-matrices introduced in this monograph, and
column sufficient matrices. The family contains not only the
usual potential reduction algorithms but also path following
algorithms and a damped Newton method for the LCP. The main
topics are global convergence, global linear convergence,
and the polynomial-time convergence of potential reduction
algorithms included in the family.

Zielgruppe

Research

Autoren/Hrsg.

Kojima, Masakazu

Yoshise, Akiko

Megiddo, Nimrod

Noma, Toshihito

Fachgebiete

• Mathematik | Informatik Mathematik Operations Research Spieltheorie
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Numerische Mathematik
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Computeranwendungen in der Mathematik
• Mathematik | Informatik Mathematik Mathematische Analysis Variationsrechnung

Inhaltsverzeichnis

Summary.- The class of linear complementarity problems with P 0-matrices.- Basic analysis of the UIP method.- Initial points and stopping criteria.- A class of potential reduction algorithms.- Proofs of convergence theorems.