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. Issue relevant to practical implementation are also discussed, including sparse linear algebra and a complete specification of Mehrota's predictor-correction algorithm. Also treated are extensions of primal-dual algorithms to more general problems such as monotone complementarity, semidefinite programming, and general convex programming problems.
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 self-contained. The book is 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 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 cuorse 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 analysis in the area, and the current state of the art.
Stephen J. Wright is a Computer Scientist at Argonne National Laboratory and Director of the Optimization Technology Center.
Please email the author if you have comments or suggestions to make about this page.
Observant readers have noticed just a few typos.
1996/xx + 289 pages/Softcover/ ISBN 0-89871-382-X
List Price $37.00/SIAM Member Price $29.60/Order Code OT54
Order this book.
Browse SIAM's Book
Catalog.
An evaluation version of BPMPD is available through the web site. Registered users can obtain an enhanced version.
In May, 1997, a new version was released. This one has a C callable interface, and features for dense column handling and warm starting. For more information, email the author of HOPDM, Jacek Gondzio.
Since April, 1997, HOPDM has been available on the NEOS Server NEOS Server.
A new release of PCx (Version 1.0, March, 1997) incorporated dense column handling, scaling, and other features. A Windows 95/NT interface is also available.
A parallel version called pPCx was developed by Tom Coleman, Michael Wagner, and Chunguang Sun at Cornell. This version runs on IBM-SP architectures and uses Sun's parallel sparse Cholesky factorization routine.
You don't need to download PCx to use it; PCx can be executed remotely over the Internet through the NEOS Server.
LBH 12/17/96; updated 8/197