Convex Optimization Problems

Convex objective, convex inequalities, affine equalities — and then every local optimum is global.

The idea

A convex optimization problem is an optimization problem in which the objective and the constraints are convex, in the exact sense below. To say which problems qualify, first fix a common format. In standard form an optimization problem reads

$\begin{array}{ll} \text{minimize} & f_{0}(x)\\ \text{subject to} & f_{i}(x) \le 0, \quad i = 1, \dots, m\\ & a_{i}^{T}x = b_{i}, \quad i = 1, \dots, p \end{array}$

Insisting that every right-hand side be $0$ costs nothing, since a constraint can always be rearranged to put it there, and it lets one set of rules cover every problem.

Definition (Convex optimization problem).

A problem in standard form is convex when three conditions hold: the objective $f_{0}$ is convex, every inequality constraint function $f_{i}$ is convex, and every equality constraint function is affine.

The third condition is stricter than the other two, and it is why the equalities are written $a_{i}^{T}x = b_{i}$ rather than $h_{i}(x) = 0$. The class matters because of one fact.

Theorem.

Every locally optimal point of a convex optimization problem is globally optimal.

A method that stops when no nearby point is better has therefore found the best point anywhere.

Ways to work on it

• Walkthrough. Standard form, the three requirements, and one small problem solved and checked.
• Proof. Why a locally optimal point of a convex problem is globally optimal.
• Practice. Classify problems as convex or not, compute optimal values, and read the terminology.
• Hardest. A convex function minimized over a convex set that is still not a convex problem in standard form.

Not sure where to start? Take the ten-question placement test.