Linear and nonlinear programming. 3rd ed. (English) Zbl 1207.90003

Luenberger, David G.; Ye, Yinyu

International Series in Operations Research & Management Science 116. New York, NY: Springer (ISBN 978-0-387-74502-2/hbk). xiii, 546 p. (2008).

The aim of this book is to present the central concepts of optimization techniques. Although it covers primarily material that is now fairly standard, it is intended to reflect modern theoretical insights. These provide structure to what might otherwise be simply a collection of techniques and results. This is particularly useful for students at the undergraduate or graduate level who have a technical background in engineering, mathematics, or science. It gives them a means not only to learn existing material but also to develop new results. In particular, the purely analytical character of an optimization problem is strongly connected to the behaviour of algorithms used to solve a problem. This is the major feature of the first two editions of this book. [For the earlier editions, please see D.G. Luenberger, Introduction to linear and nonlinear programming, Reading, Mass. etc.: Addison-Wesley Publishing Company (1973; Zbl 0297.90044); Linear and nonlinear programming. 2nd edition, Reading, Mass. etc.: Addison-Wesley Publishing Company (1984; Zbl 0571.90051), reprint of the 2nd edition, Boston, MA: Kluwer Academic Publishers (2003; Zbl 1134.90040).] The third edition has been substantially developed by a new co-author with the introduction of Interior Point Methods.
As previously, the material in this new edition is organized into three separate parts. Part I is a self-contained introduction to linear programming, a key component of optimization theory. The presentation covers the underlying theory of linear programming, many of the most effective numerical algorithms, and many of its important special applications. In the third edition a new Chapter 5 is devoted to a presentation of the theory and methods of polynomial-time algorithms for linear programming. These methods include, especially, interior point methods that have revolutionized linear programming. Part II includes an expanded treatment of necessary conditions, manifested by not only first- and second-order necessary conditions for optimality, but also by zeroth-order conditions that use no derivative information. This part continues to present the important descent methods for unconstrained problems, but there is new material on convergence analysis and on Newton’s methods which is frequently used as the workhorse of interior point methods for both linear and nonlinear programming. Finally, Part III now includes the global theory of necessary conditions for constrained problems, expressed as zeroth-order conditions. Also interior point methods for general nonlinear programming are explicitly discussed within the sections on penalty and barrier methods. A significant addition to Part III is an expanded presentation of duality from both the global and local perspective. Finally, Chapter 15, on primal-dual methods has additional material on interior point methods and an introduction to the relatively new field of semidefinite programming, including several examples.
To conclude, this very well-written book is a classic textbook in Optimization. It should be present in the bookcase of each student, researcher, and specialist from the host of disciplines from which practical optimization applications are drawn.

Reviewer: Jean-Jacques Strodiot (Namur)

MSC:

90-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90C30	Nonlinear programming
90C05	Linear programming
65K05	Numerical mathematical programming methods
49M37	Numerical methods based on nonlinear programming
90C51	Interior-point methods

Keywords:

nonlinear programming; linear programming; interior point methods; semidefinite programming

Citations:

Zbl 1134.90040; Zbl 0571.90051; Zbl 0297.90044