by Dimitri P. Bertsekas
with Angelia Nedic and Asuman E. Ozdaglar
Publication: April, 2003, 560 pages, hardcover
Contents, Preface, Ordering, Home
A uniquely pedagogical, insightful, and rigorous treatment of the analytical/geometrical foundations of optimization.
This major book provides a comprehensive development of convexity theory, and its rich applications in optimization, including duality, minimax/saddle point theory, Lagrange multipliers, and Lagrangian relaxation/nondifferentiable optimization. It is an excellent supplement to several of our books: Convex Optimization Theory (Athena Scientific, 2009), Convex Optimization Algorithms (Athena Scientific, 2015), Nonlinear Programming (Athena Scientific, 1999), Network Optimization (Athena Scientific, 1998), Introduction to Linear Optimization (Athena Scientific, 1997), and Network Flows and Monotropic Optimization (Athena Scientific, 1998).
Aside from a thorough account of convex analysis and optimization, the book aims to restructure the theory of the subject, by introducing several novel unifying lines of analysis, including:
A unified development of minimax theory and constrained optimization duality as special cases of duality between two simple geometrical problems.
A unified development of conditions for existence of solutions of convex optimization problems, conditions for the minimax equality to hold, and conditions for the absence of a duality gap in constrained optimization.
A unification of the major constraint qualifications allowing the use of Lagrange multipliers for nonconvex constrained optimization, using the notion of constraint pseudonormality and an enhanced form of the Fritz John necessary optimality conditions.
"The book's treatment of convexity theory is rigorous, insightful, and
quite comprehensive, with all major aspects of the subject receiving
substantial treatment. The mathematical development is ambitiously novel and
uses a handful of unifying principles that can be easily visualized and understood
... The writing style is very clear with many figures and exercises
supporting the text ... This is a ground-breaking and highly pedagogical book on a
fundamental subject, which will be greatly appreciated by students
and researchers. I highly recommend this book.
From the review by Serge G. Kruk (Mathematical Reviews, 2006):
"The text is therefore ideally suited for classroom use. The pre-requisite material, basic linear algebra and real analysis, is presented in the first chapter and is covered in undergraduate classes. The presentation stresses geometry and simple proofs at all times."
Among its features, the book:
develops rigorously and comprehensively the theory of convex sets and functions, in the classical tradition of Fenchel and Rockafellar
provides a geometric, highly visual treatment of convex and nonconvex optimization problems, including existence of solutions, optimality conditions, Lagrange multipliers, and duality
includes an insightful and comprehensive presentation of minimax theory and zero sum games, and its connection with duality
describes dual optimization, the associated computational methods, including the novel incremental subgradient methods, and applications in linear, quadratic, and integer programming
contains many examples, illustrations, and exercises with complete solutions (about 200 pages) posted on the internet (see below)
Dimitri P. Bertsekas is McAfee Professor of Engineering at the Massachusetts Institute of Technology and a member of the prestigious United States National Academy of Engineering. He is the recipient of the 2001 A. R. Raggazini ACC education award and the 2009 INFORMS expository writing award. Angelia Nedic, is Assistant Professor, Univ. of Illinois. Asuman E. Ozdaglar, is Associate Professor, Massachusetts Institute of Technology.
The material listed below can be freely downloaded, reproduced, and distributed.