A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems

von Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise

112 Seiten, Taschenbuch

Kurzbeschreibung des Verlags

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.

• Reihe: Lecture Notes in Computer Science
• ISBN: 9783540545095
• Sprache: Englisch
• Erscheinungsdatum: 25.09.1991
• Genre: Mathematik/Sonstiges
• Verlag: Springer Berlin