Interior Point Approach to Linear, Quadratic and Convex Programming Algorithms and Complexity
This book describes the rapidly developing field of interior point methods (IPMs). An extensive analysis is given of path-following methods for linear programming, quadratic programming and convex programming. These methods, which form a subclass of interior point methods, follow the central path, w...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Dordrecht
Springer Netherlands
1994, 1994
|
| Edition: | 1st ed. 1994 |
| Series: | Mathematics and Its Applications
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 1 Introduction of IPMs
- 1.1 Prelude
- 1.2 Intermezzo: Complexity issues
- 1.3 Classifying the IPMs
- 1.4 Scope of the book
- 2 The logarithmic barrier method
- 2.1 General framework
- 2.2 Central paths for some examples
- 2.3 Linear programming
- 2.4 Convex quadratic programming
- 2.5 Smooth convex programming
- 2.6 Miscellaneous remarks
- 3 The center method
- 3.1 General framework
- 3.2 Centers for some examples
- 3.3 Linear programming
- 3.4 Smooth convex programming
- 3.5 Miscellaneous remarks
- 4 Reducing the complexity for LP
- 4.1 Approximate solutions and rank-one updates
- 4.2 Adding and deleting constraints
- 5 Discussion of other IPMs
- 5.1 Path-following methods
- 5.2 Affine scaling methods
- 5.3 Projective potential reduction methods
- 5.4 Affine potential reduction methods
- 5.5 Comparison of IPMs
- 6 Summary, conclusions and recommendations
- Appendices
- A Self-concordance proofs
- A.1 Some general composition rules
- A.2 The dual geometric programming problem
- A.3 The extended entropy programming problem
- A.4 The primal 4-programming problem
- A.5 The dual 4-programming problem
- A.6 Other smoothness conditions
- B General technical lemmas