Stephen J. Wright
"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
"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 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.
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.
Audience
Some background in linear programming and its associated duality theory, linear algebra, and numerical analysis is helpful, although an extensive appendix ensures that the book is largely selfcontained. The book will be useful for graduate students and researchers in the sciences and engineering who are interested in using largescale optimization techniques in their research, including those interested in pursuing original research in interior point methods. Engineers may also find applications to problems of process control, predictive control, or design optimization. The book may also be used as a text for a special topics course in optimization or a unit of a general course in optimization or linear programming. Researchers and students in the field of interiorpoint methods will find the book invaluable as a reference to the key results, the basic techniques of analysis in the area, and the current state of the art.
Contents
Preface; Notation; Chapter 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; Chapter 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; 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; 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; Chapter 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; Chapter 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; Chapter 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; Chapter 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; 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. SelfDuality; The Simplified HSD Form; The HSDl Form; Identifying a SolutionFree Region; Implementations of the HSD Formulations; Notes and References; Chapter 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; Chapter 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 Formulation; Factoring Symmetric Indefinite Matrices; Starting Points; Termination; Alternative Formulations for the Linear Program; Free Variables; Presolving; PrimalDual Codes; Notes and References; Appendix A: Basic Concepts and Results. Order Notation; Convex Sets and Functions; KKT Conditions; Convexity and Global Solutions; SelfDuality and a Proof of Theorem 9.1; The Natural log Function and a Proof of Lemma 4.1; Singular Value Decomposition, Matrix Rank, and QR Factorization; Hoffman's Lemma; The Stewart–Todd Result and a Proof of Lemma 7.2; The Sherman–Morrison–Woodbury Formula; Asymptotic Convergence; Storing Sparse Matrices; The Turing Machine; Appendix B: Software Packages. BPMPD; CPLEX/Barrier; HOPDM}; LIPSOL; LOQO; mpopt/Barrier; OSL/EKKBSLV; PCx.; Bibliography; Index.
1997 / xx + 289 pages / Softcover / ISBN13: 9780898713824 / ISBN10: 089871382X / List Price $68.50 / SIAM Member Price $47.95 / Order Code OT54
