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
Show more