Primal-Dual Interior-Point Methods
Will be published approx. on 31. December 1997
Book
Paperback/Softback
309 pages
978-0-89871-382-4 (ISBN)
Description
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.
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.
Reviews / Votes
'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, DenmarkMore details
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Product notice
Paperback (trade)
Dimensions
Height: 254 mm
Width: 172 mm
Thickness: 17 mm
Weight
539 gr
ISBN-13
978-0-89871-382-4 (9780898713824)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
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
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