UID:
almafu_9959186364802883
Format:
1 online resource (VIII, 112 p.)
Edition:
1st ed. 1991.
Edition:
Online edition Springer Lecture Notes Archive ; 041142-5
ISBN:
3-540-38426-X
Series Statement:
Lecture Notes in Computer Science, 538
Content:
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.
Note:
Bibliographic Level Mode of Issuance: Monograph
,
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.
,
English
In:
Springer eBooks
Additional Edition:
ISBN 3-540-54509-3
Language:
English
DOI:
10.1007/3-540-54509-3
URL:
http://dx.doi.org/10.1007/3-540-54509-3
Bookmarklink