A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems

A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems

Paperback(1991)

$89.99
Eligible for FREE SHIPPING
  • Get it by Wednesday, April 25 , Order now and choose Expedited Delivery during checkout.

Overview

A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems by Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise

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.

Product Details

ISBN-13: 9783540545095
Publisher: Springer Berlin Heidelberg
Publication date: 10/28/1991
Series: Lecture Notes in Computer Science Series , #538
Edition description: 1991
Pages: 112
Product dimensions: 6.10(w) x 9.17(h) x 0.01(d)

Table of Contents

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.

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews