Masakazu Kojima, Akiko Yoshise, Toshihito Noma, Nimrod Megiddo

A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems

Mitarbeit:Kojima, Masakazu; Megiddo, Nimrod; Noma, Toshihito

• Broschiertes Buch

Produktbeschreibung

Following Karmarkar's 1984 linear programming algorithm,numerous interior-point algorithms have been proposed forvarious mathematical programming problems such as linearprogramming, convex quadratic programming and convexprogramming in general. This monograph presents a study ofinterior-point algorithms for the linear complementarityproblem (LCP) which is known as a mathematical model forprimal-dual pairs of linear programs and convex quadraticprograms. A large family of potential reduction algorithmsis presented in a unified way for the class of LCPs wherethe underlying matrix has nonnegative principal minors(P0-matrix). This class includes various importantsubclasses such as positive semi-definite matrices,P-matrices, P_-matrices introduced in this monograph, andcolumn sufficient matrices. The family contains not only theusual potential reduction algorithms but also path followingalgorithms and a damped Newton method for the LCP. The maintopics are global convergence, global linear convergence,and the polynomial-time convergence of potential reductionalgorithms included in the family.

---

Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.

Produktdetails

• Lecture Notes in Computational Science and Engineering 538
• Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
• Artikelnr. des Verlages: 978-3-540-54509-5
• 1991.
• Seitenzahl: 120
• Erscheinungstermin: 25. September 1991
• Englisch
• Abmessung: 235mm x 155mm x 7mm
• Gewicht: 212g
• ISBN-13: 9783540545095
• ISBN-10: 3540545093
• Artikelnr.: 09227157

Inhaltsangabe

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.