In the past decade, primal-dual algorithms have emerged as the most important and useful algorithms from the interior-point class. This book presents the major primal-dual algorithms for linear programming in straightforward terms. A thorough description of the theoretical properties of these methods is given, as are a discussion of practical and computational aspects and a summary of current software. The major primal-dual algorithms covered are path-following algorithms (short- and long-step, predictor-corrector), potential-reduction algorithms, and infeasible-interior-point algorithms. A unified treatment of superlinear convergence, finite termination and detection of infeasible problems is presented. Issues relevant to practical implementation are also discussed, including sparse linear algebra and a complete specification of Mehrotra's predictor-corrector algorithm. Also treated are extensions of primal-dual algorithms to more general problems such as monotone complementarity, semidefinite programming, and general convex programming problems.

Table of Contents:

• Preface
• Notation
• Chapter 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
• Chapter 2: Background: Linear Programming and Interior-Point Methods
• Standard Form
• Optimality Conditions, Duality, and Solution Sets
• The B * 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
• Chapter 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
• Chapter 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 * and *
• Notes and References
• Chapter 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
• Chapter 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 *k
• Proofs of Theorems 6.1 and 6.2
• Limit Points of the Iteration Sequence
• Chapter 7: Superlinear Convergence and Finite Termination. Affine-Scaling Steps
• An Estimate of (*x, * s): The Feasible Case
• An Estimate of (* x, * s): The Infeasible Case
• Algorithm PC Is Superlinear
• Nearly Quadratic Methods
• Convergence of Algorithm LPF+
• Convergence of the Iteration Sequence
• *(A,b,c) and Finite Termination
• A Finite Termination Strategy
• Recovering an Optimal Basis
• More on * (A,b,c)
• Notes and References
• Chapter 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
• Chapter 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
• Chapter 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
• Chapter 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 Formulation
• Factoring Symmetric Indefinite Matrices
• Starting Points
• Termination
• Alternative Formulations for the Linear Program
• Free Variables
• Presolving
• Primal-Dual Codes
• Notes and References
• Appendix A: Basic Concepts and Results