ISBN: 1-886529-31-0, 978-1-886529-31-1
Publication: June, 2009, 256 pages, hardcover
Price: $59.00
Supplementary Chapter 6: Convex Optimization Algorithms
An insightful, concise, and rigorous treatment of the basic theory of convex sets and functions in finite dimensions, and the analytical/geometrical foundations of convex optimization and duality theory.
Convexity theory is first developed in a simple accessible manner, using easily visualized proofs. Then the focus shifts to a transparent geometrical line of analysis to develop the fundamental duality between descriptions of convex sets and functions in terms of points and in terms of hyperplanes. Finally, convexity theory and abstract duality are applied to problems of constrained optimization, Fenchel and conic duality, and game theory to develop the sharpest possible duality results within a highly visual geometric framework.
The book is supplemented by a long web-based chapter (over 150 pages), which covers the most popular convex optimization algorithms (and some new ones), and can be downloaded from this page.
The book may be used as a text for a theoretical convex optimization course; the author has taught several variants of such a course at MIT and elsewhere over the last ten years. It may also be used as a supplementary source for nonlinear programming classes, and as a theoretical foundation for classes focused on convex optimization models (rather than theory). It is an excellent supplement to several of our books: 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).
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 optimization problems, including duality, existence of solutions, and optimality conditions
includes an insightful and comprehensive presentation of minimax theory and zero sum games, and its connection with duality
contains many examples and illustrations in the text, and exercises with complete solutions posted on the internet (see below)
connects with a supplementary freely downloadable, periodically updated chapter on convex optimization algorithms, including novel incremental subgradient methods, proximal and bundle methods, some of Nesterov's optimal complexity algorithms, and a unified framework for inner and outer polyhedral approximation
is structured to be used conveniently either as a standalone text for a theoretically-oriented class on convex analysis and optimization, or as a theoretical supplement to either an applications/convex optimization models class or a nonlinear programming class
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.
The material listed below can be freely downloaded, reproduced, and distributed.