Convex Optimization

Citation

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. Free official edition: https://web.stanford.edu/~boyd/cvxbook/

Chapter Summary

The book has eleven chapters in three parts (Theory, Applications, Algorithms), three appendices, and a set of exercises at the end of each chapter. The preface states the goal as a working knowledge of convex optimization: the ability to recognize, formulate and solve convex problems.

Chapter 1: Introduction

The chapter sets out the general optimization problem, singles out least-squares and linear programming as classes with reliable solution methods, and presents convex optimization as their common generalization. It contrasts local and global optimization, shows how convex problems help with nonconvex ones (initialization, heuristics such as sparse solutions, lower bounds), and outlines the three parts.

Chapter 2: Convex sets

Affine and convex sets, cones, and the standard examples (hyperplanes, balls and ellipsoids, norm cones, polyhedra and the positive semidefinite cone) come first. The chapter then gives the operations that preserve convexity, generalized inequalities with respect to proper cones, separating and supporting hyperplanes, and dual cones.

Chapter 3: Convex functions

The chapter defines convex functions through first- and second-order conditions, sublevel sets, the epigraph and Jensen's inequality, and lists a large catalogue of examples. It develops the calculus of convexity-preserving operations (sums, pointwise maximum, composition, minimization, perspective), then the conjugate function, quasiconvex functions, log-concave and log-convex functions, and convexity with respect to generalized inequalities.

Chapter 4: Convex optimization problems

This is the formulation chapter. It covers the standard form, equivalent problems and the optimality criterion for differentiable objectives, then the main problem families in order of generality: linear programs, quadratic programs and second-order cone programs, geometric programs, conic and semidefinite programs, and vector (multicriterion) optimization with Pareto optimality and scalarization.

Chapter 5: Duality

The Lagrangian, the dual function and the dual problem lead to weak and strong duality and Slater's constraint qualification. The chapter then gives geometric and saddle-point interpretations, the KKT optimality conditions, perturbation and sensitivity analysis, worked examples of transforming a problem before dualizing, theorems of alternatives, and the extension to generalized inequalities.

Chapter 6: Approximation and fitting

Norm approximation, least-norm problems, regularized approximation (including bi-criterion trade-offs, smoothing and de-noising), robust approximation (stochastic and worst-case) and function fitting and interpolation, with sparse descriptions via basis pursuit as one of the fitting topics.

Chapter 7: Statistical estimation

Maximum likelihood and maximum a posteriori estimation, nonparametric distribution estimation, optimal detector design and hypothesis testing, Chebyshev and Chernoff bounds, and experiment design, each posed as a convex problem.

Chapter 8: Geometric problems

Projection on a set, distance between sets, Euclidean distance and angle problems, extremal volume ellipsoids, centering (Chebyshev, maximum volume ellipsoid and analytic centers), classification by linear and nonlinear discrimination, placement and location, and floor planning.

Chapter 9: Unconstrained minimization

Descent methods are introduced with strong convexity assumptions, followed by gradient descent, steepest descent in different norms and Newton's method, each with convergence analysis and numerical examples. The chapter then introduces self-concordance, a condition on which a further convergence analysis of Newton's method rests, and ends with implementation notes on computing the Newton step.

Chapter 10: Equality constrained minimization

Newton's method is extended to problems with linear equality constraints, first by elimination and by the dual, then through the Newton step with equality constraints and the infeasible start Newton method. Convex-concave games appear as an application, and the implementation section treats solving the KKT system.

Chapter 11: Interior-point methods

The logarithmic barrier and the central path lead to the barrier method, with convergence analysis, phase I methods for finding a feasible point, and a complexity analysis based on self-concordance. The chapter extends the barrier method to generalized inequalities, describes primal-dual interior-point methods, and ends with implementation for linear and semidefinite programs and network rate optimization. The summary of the complexity section notes that the worst-case bounds are far higher than iteration counts seen in practice.

Appendices A–C: Mathematical background; Problems involving two quadratic functions; Numerical linear algebra background

Appendix A collects norms, analysis, functions, derivatives and linear algebra and fixes notation. Appendix B treats optimization problems with two quadratic functions (the S-procedure and the field of values of two symmetric matrices) and includes proofs of the strong duality results for them. Appendix C covers matrix structure and flop counts, factor-solve methods, LU, Cholesky and LDL^T factorization, block elimination and Schur complements.

Key Concepts

Chapters 2–3: Convex sets; Convex functions

• Convexity-preserving operations: rules such as intersection, affine maps, nonnegative sums and pointwise maximum that let a reader recognize a complicated set or function as convex from simple pieces.
• Generalized inequality: an ordering defined by a proper cone, which lets vector and matrix inequalities be treated like scalar ones.

Chapter 4: Convex optimization problems

• Problem hierarchy: linear, quadratic, second-order cone, geometric and semidefinite programs as increasingly general convex classes.
• Pareto optimality: the notion of an optimal trade-off in multicriterion problems, explored through scalarization.

Chapter 5: Duality

• Lagrange dual and strong duality: the dual gives a lower bound on the optimal value, and Slater's condition ensures that the bound is tight for convex problems.
• KKT conditions: optimality conditions combining primal and dual feasibility with complementary slackness.
• Sensitivity analysis: reading how the optimal value responds to changes in the constraints from the dual variables.

Chapters 6–8: Applications

• Regularization and robustness: trading data fit against a second criterion, or protecting against uncertainty in the data.
• Maximum likelihood estimation: parameter estimation posed as the maximization of a log-likelihood function.

Chapters 9–11: Algorithms

• Newton step and decrement: the descent direction from the quadratic model and the quantity used to measure progress and stop.
• Self-concordance: a condition on third derivatives that supports complexity bounds for Newton's method.
• Barrier method and central path: solving an inequality constrained problem through a sequence of equality constrained ones.

Critical Analysis

Strengths

• Formulation is the organizing skill. The preface and Chapter 1 argue that the art in convex optimization lies in recognizing and formulating problems, and the structure follows: Chapters 2 to 4 train recognition through catalogues of sets, functions and problem classes, and Part II applies them.
• Short, accessible applications. Part II uses simplified cases from statistics, geometry and data fitting, kept short for non-experts.
• A clear hierarchy of algorithms. Part III builds from quadratic problems to Newton's method with equality constraints and then to interior-point methods, so each method is reduced to a sequence of simpler ones.
• Exercises that train formulation. Many exercises ask the reader to establish convexity or to formulate a problem, and some numerical ones need modest programming.

Limitations

• Not a theory of convex analysis. The preface says that the book is not primarily about convex analysis and does not give results in their most general form; readers who need that depth must turn to other texts.
• Selected algorithms only. Part III is limited to Newton-type and interior-point methods in simplified form. The authors list quasi-Newton, conjugate-gradient, bundle and cutting-plane methods among the omitted classes.
• Mixed exercise difficulty. The introduction states that difficulty varies without warning from straightforward to tricky, so selecting exercises takes some care.
• Mathematical maturity expected. The preface requires good knowledge of advanced calculus and linear algebra, and notes that readers without basic analysis and probability can still get the essential ideas but may not follow every argument.

Where It Fits in the Course

Boyd and Vandenberghe is the course's focused text on convex optimization. Two other books in the list start earlier: A Gentle Introduction to Optimization is aimed at students who have had a first linear algebra course and develops linear and integer programming and the simplex method, and Chong, Lu and Żak's An Introduction to Optimization covers unconstrained, linear and constrained nonlinear optimization for advanced undergraduates. Either gives a base in optimality conditions and linear programming before this book, whose preface names advanced linear algebra and linear programming as the natural preceding topics.

Boyd and Vandenberghe differs from both in organizing everything around convexity: duality, conic programming and interior-point methods are central rather than late additions. The other books in the list, on advanced mathematical methods and on mathematics for economics and business, are broader treatments in which optimization is one topic among several, so this is the book to use when a project calls for modeling and solving convex problems in earnest.

How to Use This Book

The book is meant for researchers, scientists and engineers who use optimization, and for graduate courses. The authors report covering most of it, not in detail, in a one-quarter graduate course, with a semester allowing more applications and a project. The only stated background is advanced calculus and linear algebra; some analysis and probability make every argument followable.

A practical plan:

• Core: Chapter 1, then Chapters 2 and 3 selectively (examples and the convexity-preserving operations matter more than every proof), then Chapters 4 and 5 in full. These four chapters carry the formulation and duality skills.
• Applications: pick from Chapters 6 to 8 according to interest, for example Chapter 6 for fitting and regularization, Chapter 7 for statistics, Chapter 8 for geometry and classification.
• Algorithms: read Chapters 9 to 11 in order, since each builds on the previous one. The complexity analysis in Section 11.5 can be skipped on a first pass; the section's own summary calls it mostly of theoretical interest.
• Appendices: consult Appendix A for notation, and Appendix C before implementing the Newton and KKT steps.

Do the exercises that ask for formulation or a proof of convexity before the numerical ones, and write each formulation down in standard form. Checking a formulation with a solver on a small instance is the most direct test of understanding.

Edition and Sources

This guide covers the first edition (Cambridge University Press, 2004), as read in the authors' posted copy, which is the seventh printing with corrections (2009). The free official edition is at https://web.stanford.edu/~boyd/cvxbook/. The edition is documented by the preface, the full table of contents, all section and subsection headings, the introduction in full, and selected passages from the chapters, including the Chapter 11 complexity summary and the Newton step implementation notes.