PrimalDual InteriorPoint Methods
 Author: Stephen J. Wright, Argonne National Laboratory, Illinois
 Date Published: December 1997
 availability: This item is not supplied by Cambridge University Press in your region. Please contact Soc for Industrial & Applied Mathematics for availability.
 format: Paperback
 isbn: 9780898713824
Paperback
Looking for an inspection copy?
This title is not currently available for inspection. However, if you are interested in the title for your course we can consider offering an inspection copy. To register your interest please contact asiamktg@cambridge.org providing details of the course you are teaching.

In the past decade, primaldual algorithms have emerged as the most important and useful algorithms from the interiorpoint class. This book presents the major primaldual 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 wellwritten work. The major primaldual algorithms covered in this book are pathfollowing algorithms (short and longstep, predictorcorrector), potentialreduction algorithms, and infeasibleinteriorpoint 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 predictorcorrector algorithm. Also treated are extensions of primaldual algorithms to more general problems such as monotone complementarity, semidefinite programming, and general convex programming problems.
Reviews & endorsements
'The current hottest topic in optimization is interiorpoint methods. Steve Wright, a renowned expert in optimization, has written a truly excellent introduction to this topic. We have used this book in a termlong 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 interiorpoints is still under development, this book promises to be an important reference for many years to come.' Professor Henry Wolkowicz, University of Waterloo
See more reviews'This is a beautifully crafted book on a specialized but very important topic. Primaldual methods are now recognized by both theoreticians and practitioners as the best available interiorpoint 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 primaldual interiorpoint 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 interiorpoint 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
Customer reviews
Not yet reviewed
Be the first to review
Review was not posted due to profanity
×Product details
 Date Published: December 1997
 format: Paperback
 isbn: 9780898713824
 length: 309 pages
 dimensions: 254 x 172 x 17 mm
 weight: 0.539kg
 availability: This item is not supplied by Cambridge University Press in your region. Please contact Soc for Industrial & Applied Mathematics for availability.
Table of Contents
Preface
Notation
1. Introduction. Linear Programming
PrimalDual Methods
The Central Path
A PrimalDual Framework
PathFollowing Methods
PotentialReduction Methods
Infeasible Starting Points
Superlinear Convergence
Extensions
Mehrotra's PredictorCorrector Algorithm
Linear Algebra Issues
Karmarkar's Algorithm
2. Background. Linear Programming and InteriorPoint 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
PrimalDual 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
PrimalDual Methods and Rational Arithmetic
Linear Programming and Rational Numbers
Moving to a Solution from an Interior Point
Complexity of Simplex, Ellipsoid, and InteriorPoint Methods
Polynomial and Strongly Polynomial Algorithms
Beyond the Turing Machine Model
More on the RealNumber Model and Algebraic Complexity
A General Complexity Theorem for PathFollowing Methods
Notes and References
4. PotentialReduction Methods. A PrimalDual PotentialReduction 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. PathFollowing Algorithms. The ShortStep PathFollowing Algorithm
Technical Results
The PredictorCorrector Method
A LongStep PathFollowing Algorithm
Limit Points of the Iteration Sequence
Proof of Lemma 5.3
Notes and References
6. InfeasibleInteriorPoint 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. AffineScaling 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. SelfDuality
The Simplified HSD Form
The HSDl Form
Identifying a SolutionFree Region
Implementations of the HSD Formulations
Notes and References
10. Practical Aspects of PrimalDual Algorithms. Motivation for Mehrotra's Algorithm
The Algorithm
Superquadratic Convergence
SecondOrder TrajectoryFollowing Methods
HigherOrder Methods
Further Enhancements
Notes and References
11. Implementations. Three Forms of the Step Equation
The Cholesky Factorization
Sparse Cholesky Factorization. MinimumDegree Orderings
Other Orderings
Small Pivots in the Cholesky Factorization
Dense Columns in A
The Augmented System Formulat
Sorry, this resource is locked
Please register or sign in to request access. If you are having problems accessing these resources please email lecturers@cambridge.org
Register Sign in» Proceed