Overview

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.

Full Product Details

Author:   Masakazu Kojima ,  Nimrod Megiddo ,  Toshihito Noma ,  Akiko Yoshise
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   1991 ed.
Volume:   538
Dimensions:   Width: 15.50cm , Height: 0.60cm , Length: 23.30cm
Weight:   0.454kg
ISBN:  

9783540545095

ISBN 10:   3540545093
Pages:   112
Publication Date:   25 September 1991
Audience:   College/higher education ,  Professional and scholarly ,  Postgraduate, Research & Scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

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.

Reviews

Author Information

Tab Content 6

Author Website:  

Countries Available

All regions