Primal-Dual Interior-Point Methods

by Stephen J. Wright

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.AudienceSome 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 self-contained. The book will be useful for graduate students and researchers in the sciences and engineering who are interested in using large-scale 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 interior-point 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.About the AuthorStephen J. Wright is Computer Scientist, Mathematics and Computer Science Division, Argonne National Laboratory. He is also the founding Director of the Optimization Technology Center, a joint venture of Argonne and Northwestern University. He is the author of more than forty technical papers, including the Optimization Software Guide (SIAM) co-authored with Jorge More' in 1993

Paperback

First published January 1, 1987