Unified Approach to Interior Point Algorithms for Linear Complementarity Problems
| Author/creator | Kojima, M. Author |
| Other author | Megiddo, N. Author |
| Other author | Noma, T. Author |
| Format | Electronic |
| Publication Info | New York : Springer |
| Description | VIII, 108 p. 24.200 x 017.000 cm. |
| Supplemental Content | Full text available from SpringerLINK Lecture Notes in Computer Science |
| Supplemental Content | Full text available from Springer Books |
| Series | Lecture Notes in Computer Science Ser. |
| Summary | Annotation 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. |
| Access restriction | Available only to authorized users. |
| Technical details | Mode of access: World Wide Web |
| Genre/form | Electronic books. |
| ISBN | 9783540545095 |
| ISBN | 3540545093 (Trade Paper) Active Record |
| Standard identifier# | 9783540545095 |
| Stock number | 3540545093 00024965 |
Availability
| Library | Location | Call Number | Status | Item Actions |
|---|---|---|---|---|
| Electronic Resources | ✔ Available |