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.
Builds on
Leads to
Not sure where to start? Take the ten-question placement test.