Primal-Dual Interior-Point Methods

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. 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 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 analysis in the area, and the current state of the art.

Preface: Table of Contents

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.

Background Information on Interior-Point Methods and Optimization

• Interior-Point Methods Online, an archive of new technical reports and pointers to interior-point people and places. This site is the gathering place on the internet for the interior-point community.
• NEOS Guide, a service of the Optimization Technology Center at Argonne and Northwestern. The Guide contains a listing of current optimization software (including the packages mentioned below), back-of-the-envelope sketches of the various subdisciplines in optimization, case studies of optimization in applications, and more.

Software for Primal-Dual Interior-Point Methods

• BPMPD is a Fortran code written by Csaba Mészáros. The latest release is 2.21 (June, 1998), which includes new heuristics for the sparse matrix factorization and a more efficient presolve. A Windows 95/NT DLL and executable are also available.

• CPLEX is a commercial software software product for solving linear, integer linear, and network linear programs. Their primal-dual interior-point option is CPLEX/Barrier, which can also handle convex quadratic programs. Parallel solvers are also available for certain platforms.

• HOPDM's Web Site, where version 2.13 of the code (February, 1996) is available for downloading. This is a Fortran 77 code, but a C version (obtained by applying f2c to the Fortran source) is also available. Several papers that describe the solver can also be found at the web site.

  The latest version of HOPDM is version 2.30 of March, 1998. This one has a C callable interface, features for dense column handling and warm starting, a choice of two factorization techniques, and extensions to quadratic programming. For more information, email the author of HOPDM, Jacek Gondzio.

• LIPSOL, the primal-dual code of Yin Zhang, written mostly in Matlab. LIPSOL also uses the direct sparse Cholesky solver of Esmond Ng and Barry Peyton.

• LOQO, a C code developed by Bob Vanderbei and collaborators at Princeton. LOQO can handle nonlinear and quadratic programs in addition to linear programs. LOQO is available free for academic use. Commercial users must obtain a license.

• IBM's commercial optimization package OSL also contains primal-dual interior-point codes. See OSL online Documentation for information on these and many other OSL codes. The primal-dual code is called EKKBSLV. Simplex codes, network codes, etc, are also included in OSL. Documentation of the interior-point algorithms underlying EKKBSLV is quite extensive. There is also a brief description of the underlying method.

• PCx, is the C code of Joe Czyzyk, Sanjay Mehrotra, Michael Wagner, and Steve Wright. The default version of PCx is powered by the sparse Cholesky solver of Esmond Ng and Barry Peyton.

  PCx can also be linked to the WSSMP factorizer of Anshul Gupta and his colaborators for execution on IBM RS6000 platforms. This version is usually considerably faster than the default version on these platforms. WSSMP can be obtained by sending email to Gupta.

  The PCx web page also contains information about the Windows 95/NT version of PCx, the Java front-end, the AMPL interface, and so on. A new release of PCx is expected in Fall, 1999.

Software Benchmarks

• Hans Mittelmann has done extensive benchmarking of some of the codes listed above. He reports their performance on a selection of problems in this table. The test problems included in the table are mostly larger problems, selected to highlight differences in performance between the codes.

Modeling Languages

• GAMS
• AMPL
• MPL
• AIMMS
• LINGO
• XPRESS-MP-Model Builder