Primal-Dual Interior-Point Methods

Table of Contents

Preface
Notation
1. Introduction. Linear Programming
Primal-Dual Methods
The Central Path
A Primal-Dual Framework
Path-Following Methods
Potential-Reduction Methods
Infeasible Starting Points
Superlinear Convergence
Extensions
Mehrotra's Predictor-Corrector Algorithm
Linear Algebra Issues
Karmarkar's Algorithm
2. Background. Linear Programming and Interior-Point Methods
Standard Form
Optimality Conditions, Duality, and Solution Sets
The B {SYMBOL 200 \f "Symbol"} N Partition and Strict Complementarity
A Strictly Interior Point
Rank of the Matrix A
Bases and Vertices
Farkas's Lemma and a Proof of the Goldman–Tucker Result
The Central Path
Background. Primal Method
Primal-Dual Methods. Development of the Fundamental Ideas
Notes and References
3. Complexity Theory. Polynomial Versus Exponential, Worst Case vs Average Case
Storing the Problem Data. Dimension and Size
The Turing Machine and Rational Arithmetic
Primal-Dual Methods and Rational Arithmetic
Linear Programming and Rational Numbers
Moving to a Solution from an Interior Point
Complexity of Simplex, Ellipsoid, and Interior-Point Methods
Polynomial and Strongly Polynomial Algorithms
Beyond the Turing Machine Model
More on the Real-Number Model and Algebraic Complexity
A General Complexity Theorem for Path-Following Methods
Notes and References
4. Potential-Reduction Methods. A Primal-Dual Potential-Reduction Algorithm
Reducing Forces Convergence
A Quadratic Estimate of \Phi _{\rho } along a Feasible Direction
Bounding the Coefficients in The Quadratic Approximation
An Estimate of the Reduction in \Phi _{\rho } and Polynomial Complexity
What About Centrality?
Choosing {SYMBOL 114 \f "Symbol"} and {SYMBOL 97 \f "Symbol"}
Notes and References
5. Path-Following Algorithms. The Short-Step Path-Following Algorithm
Technical Results
The Predictor-Corrector Method
A Long-Step Path-Following Algorithm
Limit Points of the Iteration Sequence
Proof of Lemma 5.3
Notes and References
6. Infeasible-Interior-Point Algorithms. The Algorithm
Convergence of Algorithm IPF
Technical Results I. Bounds on \nu _k \delimiter "026B30D (x^k,s^k) \delimiter "026B30D
Technical Results II. Bounds on (D^k)^{-1} \Delta x^k and D^k \Delta s^k
Technical Results III. A Uniform Lower Bound on {SYMBOL 97 \f "Symbol"}k
Proofs of Theorems 6.1 and 6.2
Limit Points of the Iteration Sequence
7. Superlinear Convergence and Finite Termination. Affine-Scaling Steps
An Estimate of ({SYMBOL 68 \f "Symbol"}x, {SYMBOL 68 \f "Symbol"} s). The Feasible Case
An Estimate of ({SYMBOL 68 \f "Symbol"} x, {SYMBOL 68 \f "Symbol"} s). The Infeasible Case
Algorithm PC Is Superlinear
Nearly Quadratic Methods
Convergence of Algorithm LPF+
Convergence of the Iteration Sequence
{SYMBOL 206 \f "Symbol"}(A,b,c) and Finite Termination
A Finite Termination Strategy
Recovering an Optimal Basis
More on {SYMBOL 206 \f "Symbol"} (A,b,c)
Notes and References
8. Extensions. The Monotone LCP
Mixed and Horizontal LCP
Strict Complementarity and LCP
Convex QP
Convex Programming
Monotone Nonlinear Complementarity and Variational Inequalities
Semidefinite Programming
Proof of Theorem 8.4. Notes and References
9. Detecting Infeasibility. Self-Duality
The Simplified HSD Form
The HSDl Form
Identifying a Solution-Free Region
Implementations of the HSD Formulations
Notes and References
10. Practical Aspects of Primal-Dual Algorithms. Motivation for Mehrotra's Algorithm
The Algorithm
Superquadratic Convergence
Second-Order Trajectory-Following Methods
Higher-Order Methods
Further Enhancements
Notes and References
11. Implementations. Three Forms of the Step Equation
The Cholesky Factorization
Sparse Cholesky Factorization. Minimum-Degree Orderings
Other Orderings
Small Pivots in the Cholesky Factorization
Dense Columns in A
The Augmented System Formulat