A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems

✍ Scribed by Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise (auth.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 1991
• Tongue: English
• Leaves: 110
• Series: Lecture Notes in Computer Science 538
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Introduction....Pages 1-5
Summary....Pages 7-23
The class of linear complementarity problems with P 0 -matrices....Pages 25-34
Basic analysis of the UIP method....Pages 35-58
Initial points and stopping criteria....Pages 59-73
A class of potential reduction algorithms....Pages 75-85
Proofs of convergence theorems....Pages 87-96

✦ Subjects

Numerical Analysis; Systems Theory, Control; Calculus of Variations and Optimal Control; Optimization