The Map

Optimization methods are easiest to understand by what they need to know about a problem and what they promise in return. This page lays out the book along those two lines.

What a method needs to know

The first question to ask of any problem is what can be computed about the objective at a point, and what structure the problem has.

flowchart TD
    Q{"What do you know<br/>about the objective?"}
    Q -->|"linear objective,<br/>linear constraints"| LP["Linear programming"]
    Q -->|"sum of squares"| LS["Least squares,<br/>regularization"]
    Q -->|"smooth, with<br/>gradients"| C{"Constraints?"}
    C -->|"none"| G["Gradient and curvature<br/>methods"]
    C -->|"equalities,<br/>inequalities"| K["KKT, barrier,<br/>ADMM"]
    Q -->|"smooth part +<br/>simple kink"| P["Proximal gradient"]
    Q -->|"values only,<br/>or many local minima"| D["Derivative-free and<br/>global search"]
    Q -->|"a likelihood<br/>built from data"| E["Estimation"]
Figure 1: Choosing a family of methods by the structure of the problem.

The boxes correspond to chapters: linear programming to 3  Linear Programming; least squares and proximal gradient to 4  Least Squares and Regularization; gradient and curvature methods to 1; KKT conditions, the barrier method and ADMM to 5  Constraints and Duality; derivative-free and global search to 6  Derivative-Free and Global Search; and estimation to 2.

What a method promises

Structure buys guarantees. The more a problem has, the stronger the promise:

Table 1: Guarantees by problem class.
problem typical method what it promises
linear program simplex, interior point the exact optimum, or a proof there is none
convex, smooth gradient methods, Newton the global minimum, at a known rate set by the condition number
convex, constrained barrier method, ADMM the global minimum, with a duality gap that certifies how close
smooth, non-convex the same gradient methods a stationary point, usually a local minimum
black box, multimodal annealing, populations, Bayesian optimization a good point within the budget; no certificate

The first two parts of the book live in the top rows, where answers are exact or certified. Part III moves down the table, where methods keep working but promise less, and asks the question that makes modern machine learning possible at all: why local methods find good answers on enormous non-convex problems (8  High-Dimensional Landscapes).

The thread through the chapters

Four ideas recur, and following them is a good way to read the book.

Reading paths