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.
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
'The current hottest topic in optimization is interior-point methods. Steve Wright, a renowned expert in optimization, has written a truly excellent introduction to this topic. We have used this book in a term-long seminar. It was immediately obvious that this book is both comprehensive and 'very readable' to both experts and students new to this area. The book is not just a theoretical text but contains algorithms in enough detail to allow students to write efficient code. Even though the area of interior-points is still under development, this book promises to be an important reference for many years to come.' Professor Henry Wolkowicz, University of Waterloo 'This is a beautifully crafted book on a specialized but very important topic. Primal-dual methods are now recognized by both theoreticians and practitioners as the best available interior-point methods for linear programming. Steve Wright's book is remarkable because it demystifies a very active current research area, synthesizing the important contributions and making the many clever ideas underlying the subject accessible to graduate (or even good undergraduate) students. The book is comprehensive and beautifully written. I could not find a single poorly written sentence or confusing equation. I strongly recommend it to anyone interested in linear programming.' Michael Overton, New York University 'Stephen J. Wright has written an excellent book about primal-dual interior-point methods. The book covers major theoretical developments of the last ten years as well as practical issues related to implementation of the methods. The subject is presented thoroughly, and valuable insight and motivation are also provided. The book can be used as an introduction to interior-point methods for advanced students and is a useful reference book for researchers. I am sure I am going to use the book a lot and cite it often.' Erling D. Andersen, Department of Management, Odense University, Denmark
