This book provides an introduction to the applications, theory, and algorithms of linear and nonlinear programming. The emphasis is on practical aspects---modern algorithms, as well as the influence of theory on the interpretation of solutions or on the design of software. Two important goals of this book are to present linear and nonlinear programming in an integrated setting, and to incorporate the new interior-point methods in linear and convex programming.
As an illustration of this unified approach, almost every algorithm in this book is presented in the form of a General Optimization Algorithm. This algorithm has two major steps: an optimality test, and a step that improves the estimate of the solution. This framework is general enough to encompass the simplex method and various interior-point methods for linear programming, as well as Newton's method and active-set methods for nonlinear programming. The optimality test in this algorithm motivates the discussion of optimality conditions for a variety of problems. The step procedure motivates the discussion of feasible directions (for constrained problems) and Newton's method and its variants (for nonlinear problems).
In general, there is an attempt to develop the material from a small number of basic concepts, emphasizing the interrelationships among the many topics. Our hope is that, by emphasizing a few fundamental principles, it will be easier to understand and assimilate the vast panorama of linear and nonlinear programming.
We have attempted to make accessible a number of topics that are not often found in textbooks. Within linear programming, we have emphasized the importance of sparse matrices on the design of algorithms, described computational techniques used in sophisticated software packages, and derived the primal-dual interior-point method together with the predictor-corrector technique. Within nonlinear programming, we have included discussions of truncated-Newton methods for large problems, convergence theory for trust-region methods, and techniques for alleviating the ill-conditioning in barrier methods. Our final chapter describes interior-point methods for convex programming, and the recently developed theory of self-concordant functions. We hope that the book serves as a useful introduction to research papers in these areas.
The book was designed for use in courses and course sequences that discuss both linear programming and nonlinear programming. We have used consistent approaches when discussing the two topics, often using the same terminology and notation in order to emphasize the similarities between the two topics. However it can also be used in traditional (and separate) courses in Linear Programming and Nonlinear Programming---in fact, that is the way we use it in the courses that we teach. At the end of this Preface are chapter descriptions and course outlines indicating these possibilities.
We have also used the book for more advanced courses. The later chapters (and the later sections within chapters) contain a great deal of material that would be difficult to cover in an introductory course. The Notes at the ends of the chapters contain pointers to research papers and other references, and it would be straightforward to use such materials to supplement the book.
The book is divided into four parts plus appendices. Part I (Basics) contains material that might be used in a number of different topics. It is not intended that all of this material be presented in the classroom. Some of it might be irrelevant (as the sample course outlines illustrate). In other cases, material might be familiar to the students from other courses, or simple enough to be assigned as a reading exercise. The material in Part I could also be taught in stages, as it is needed. In a course on Nonlinear Programming, for example, Chapter 3 (Representation of Linear Constraints) could be delayed until after Part III (Unconstrained Optimization). Our intention in designing Part I was to make the book as flexible as possible, and instructors should feel free to exploit this flexibility.
Part II (Linear Programming) and Part III (Unconstrained Optimization) are independent of each other. Either one could be taught or read before the other. In addition, it is not necessary to cover Part II before going on to Part IV (Nonlinear Programming), although the material in Part IV will benefit from an understanding of Linear Programming. The material in the appendices may already be familiar. If not, it could either be presented in class or left for students to read independently.
Many sections in the book can be omitted without interrupting the flow of the discussions (detailed information on this is given below). Proofs of theorems and lemmas can similarly be omitted. The book was organized in this way so that it would be accessible to a wider audience, as well as to increase its flexibility.
Many of the exercises are computational. In some cases, pencil-and-paper techniques would suffice, but the use of a computer is recommended. We have not specified how the computer might be used, and leave this up to the instructor. In courses with an emphasis on modelling, a specialized linear or nonlinear programming package might be appropriate. In other courses, the students might be asked to program algorithms themselves. We leave these decisions up to the instructor. Some information about software packages can be found in Appendix C.
In our own classes, we use the Matlab software package for class demonstrations and homework assignments. It allows us to demonstrate a great many techniques easily, and it allows students to program individual algorithms without much difficulty. It also includes (in its toolboxes) prepared algorithms for many of the optimization problems that we discuss.
We have gone to considerable effort to ensure the accuracy of material in this book. Even so, we expect that some errors remain. For this reason, we have set up an online page for errata