Primal-Dual Interior-Point Methods

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. This is an excellent, timely, and well-written work. The major primal-dual algorithms covered in this book 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.

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

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. This is an excellent, timely, and well-written work.