Linear programming has been the dominant paradigm in optimization since Dantzig's development of the simplex method in the 1940s. In 1984, the publication of a paper by Karmarkar started a wave of research into a new class of methods known as interior-point methods, and in the decade since then, primal-dual algorithms have emerged as the most important and useful algorithms from this class.
On the theoretical side, the properties of primal-dual methods for linear programming have been quite well understood by researchers since approximately 1994. On the computational side, most interior-point software written since 1990 has been based on a single primal-dual algorithm: Mehrotra's predictor-corrector algorithm. The interesting results are, however, widely scattered in the literature, and most of the relevant papers and reports assume a significant amount of background knowledge on the part of the reader. In this book, we use a simple, unified framework to describe the major results, and we provide a straightforward, self-contained account of the underlying theory.
Primal-dual methods have excellent theoretical properties, good practical performance, and pleasing relationships to earlier fundamental ideas in mathematical programming. They can be extended to wider classes of problems, including convex quadratic programming, monotone linear complementarity, and semidefinite programming, without losing their attributes of simplicity and good practical behavior. Extensions to more difficult classes of problems (even to nonlinear programming) are under way, but the issues become more complicated with the loss of linearity and convexity. These extensions are keeping many researchers busy.
Chapter 1 presents a broad overview of primal-dual methods and should be read first by all nonspecialist readers. In the next two chapters, we fill in some of the background for primal-dual methods with results from the theory of linear programming (Chapter 2) and complexity theory (Chapter 3). Chapter 2 also contains some general historical background on interior-point methods. Descriptions and full analyses of the most interesting algorithms appear in Chapters 4, 5, and 6. An algorithm based on the primal-dual potential function is the subject of Chapter 4. Chapter 5 describes three algorithms of the path-following genre, while Chapter 6 discusses an infeasible-interior-point method that generalizes the long-step path-following method from the preceding chapter. Issues of fast local convergence and finite termination at an optimal solution are discussed in Chapter 7.
Extensions of primal-dual methods beyond linear programming are outlined in Chapter 8. We discuss monotone linear and nonlinear complementarity problems, convex programming, and semidefinite programming. Techniques for reliable detection of infeasible linear programs, including use of the homogeneous self-dual formulation, are the subject of Chapter 9.
The last two chapters turn to topics of more immediate practical interest. Most current software is based on Mehrotra's predictor-corrector algorithm, which enhances the algorithms of Chapters 4, 5, and 6 with a higher-order search direction and some effective heuristics. These enhancements are motivated and described in Chapter 10. In Chapter 11, we examine the computational issues involved in implementing primal-dual methods. The agenda here is dominated by large sparse systems of linear equations, which must be solved to obtain search directions at each iteration. We also discuss the particular features of some primal-dual codes that have appeared recently in the public domain.
Although this book contains a good deal of analysis, it has a somewhat practical bias. We tend to focus on algorithms that are closely related to practical methods. Primal-dual affine-scaling algorithms are omitted for this reason, despite their fascinating theoretical properties. Within each chapter, the intuitive/descriptive sections of the text are well separated from the more technical sections; the latter can be skipped safely and left to a rainy day.
This book is intended to fulfill a number of needs. It can be used as a text for a course on interior-point methods for linear programming. Selected chapters can be used for a short lecture series within a wider course on optimization or linear programming. The prerequisites are a basic understanding of real analysis and linear algebra and a familiarity with the elements of duality theory for linear programming.
Optimization practitioners and researchers who are not interior-point specialists can use the book as an introduction to some of the major ideas and algorithms. Experts can use it as a reference for the main theoretical results and analytical techniques and also as a guide to aspects of the area with which they are not so familiar.
The field of interior-point methods is an active and competitive one, and the origin of some of the main ideas is sometimes a topic of contention. We have not tried to taxonomize the literature or to trace the development of the various ideas, since these issues are of limited interest to students and nonspecialists. Still, we have tried to point out the key publications, including papers with comprehensive citation lists. No doubt there are some omissions, for which we apologize.
One site on the World Wide Web that will
interest readers of this book, Interior-Point Methods Online,
is the home page for this book, which contains
feedback column, and so on. The URL is
Other Web sites are mentioned in the text as well. The Web is proving to be a valuable adjunct to research activity in this and other fast-moving areas.
I thank Mihai Anitescu, Uri Ascher, Larry Biegler, Joe Czyzyk, Sharon Filipowski, Jean-Pierre Haeberly, Irv Lustig, David Mayne, Michael Overton, Florian Potra, Barry Smith, Yin Zhang, and the anonymous referees of the February 1996 draft for their interest, advice, and extremely valuable comments, which filled numerous gaps in my knowledge. Gail Pieper's assiduous proofreading turned up many infelicities of grammar and logic. As always, her help was invaluable. I am also grateful to Paul Plassmann and Jorge Nocedal for their encouragement during the early stages of this project. Finally, I thank Susan Ciambrano and the staff at SIAM, who made the publication process a sheer delight.
Stephen J. Wright