 |
|
|
|
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.
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
Packages are listed in alphabetical order...
- 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
The nearly universal format for specifying linear programs is the MPS
file, whose format was developed in the 1950s. Modeling languages provide
a much nicer interface, allowing users to specify linear models intuitively
in terms of the underlying application. Several modeling languages have
either embedded LP capabilities, or else can be linked to linear programming
packages with little effort. Examples include:
|
|
|
For questions about book orders, contact siambooks@siam.org.
SIAM uses EasyCart to process book orders. Books are linked
from SIAM's site to EasyCart's secure site for processing. Purchase options
are located at the bottom of the catalog page for each book. Select quantity
and member or list price and click the "Click to Order" button
to add books to your shopping cart. |
|
