A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems

1. Front Matter

   PDF

2. Introduction

   Pages 1-5

3. Summary

   Pages 7-23

4. The class of linear complementarity problems with P ₀-matrices

   Pages 25-34

5. Basic analysis of the UIP method

   Pages 35-58

6. Initial points and stopping criteria

   Pages 59-73

7. A class of potential reduction algorithms

   Pages 75-85

8. Proofs of convergence theorems

   Pages 87-96

9. Back Matter

   PDF

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.

• Complementarity
• Innerer-Punkt-Methode
• Interior-Point Method
• Komplementarität
• Linear Programming
• Lineares Programmieren
• Mathematics of Computing
• Mathematik der Informationsverarbeitung
• Optimierung
• algorithms
• linear optimization
• optimization

Policies and ethics