Convex Optimization Algorithms, 凸最適化アルゴリズム, 9781886529281,978-1-886529-28-1
Description
This book aims at an up-to-date and accessible development of algorithms for solving convex optimization problems. The book covers almost all the major classes of convex optimization algorithms. Principal among these are gradient, subgradient, polyhedral approximation, proximal, and interior point methods. Most of these methods rely on convexity (but not necessarily differentiability) in the cost and constraint functions, and are often connected in various ways to duality. The book contains numerous examples describing in detail applications to specially structured problems.
The book complements our Convex Optimization Theory (Athena Scientific, 2009) book, but can be read independently. The latter book focuses on convexity theory and optimization duality, while the present book focuses on algorithmic issues. The two books share mathematical prerequisites, notation, and style, and together cover the entire finite-dimensional convex optimization field. Both books rely on rigorous mathematical analysis, but also aim at an intuitive exposition that makes use of visualization where possible. This is facilitated by the extensive use of analytical and algorithmic concepts of duality, which by nature lend themselves to geometrical interpretation.
The book may be used as a text for a convex optimization course with a focus on algorithms; the author has taught several variants of such a course at MIT and elsewhere over the last fifteen years. It may also be used as a supplementary source for nonlinear programming classes, and as an algorithmic foundation for classes focused on convex optimization models. It is an excellent supplement to several of our books: Convex Optimization Theory (Athena Scientific, 2009), 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).
Special features:
・develops comprehensively the theory of descent and approximation methods, including gradient and subgradient projection methods, cutting plane and simplicial decomposition methods, and proximal methods
・describes and analyzes augmented Lagrangian methods, and alternating direction methods of multipliers
・develops the modern theory of coordinate descent methods, including distributed asynchronous convergence analysis
・comprehensively covers incremental gradient, subgradient, proximal, and constraint projection methods
・includes optimal algorithms based on extrapolation techniques, and associated rate of convergence analysis
・describes a broad variety of applications of large-scale optimization and machine learning
・contains many examples, illustrations, and exercises
・is structured to be used conveniently either as a standalone text for a class on convex analysis and optimization, or as a theoretical supplement to either an applications/convex optimization models class or a nonlinear programming class