Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 38 · Convex Sets and Functions

Convex Optimization Problems and Optimality

Define a convex optimization problem, prove why local minima are global, state the optimality condition for constrained problems, and verify it numerically.

You now have convex sets and convex functions. Put them together and you get the central object of this track: the convex optimization problem. In this lesson you see its definition, learn why its solutions are so well behaved, and meet the optimality condition that will guide algorithms in later chapters.

Definition

A problem is a convex optimization problem if it has the form

Text
minimize    f(x)
subject to  g_i(x) ≤ 0    for i = 1, ..., m
            Ax = b

where f and every g_i are convex functions, and the equality constraints are affine (written Ax = b). The feasible set is then convex: each g_i(x) ≤ 0 is a sublevel set of a convex function (convex), the equality set is a flat subspace (convex), and an intersection of convex sets is convex.

Watch the details. A constraint g(x) ≥ 0 with convex g is not convex. A nonlinear equality h(x) = 0 is generally not convex either. The rules are strict because the guarantees depend on them.

Local minima are global

Claim. In a convex problem, every local minimizer is a global minimizer.

Proof sketch. Suppose x is a local minimizer but some feasible y has f(y) < f(x). For small θ > 0, the point z = (1 - θ)x + θy is feasible (the feasible set is convex) and lies as close to x as we like. By convexity, f(z) ≤ (1 - θ)f(x) + θf(y) < f(x). So z is a feasible point near x with a lower value, which contradicts the local minimality of x. ∎

Two more consequences:

  • The set of minimizers is itself convex.
  • If f is strictly convex, the minimizer is unique.

The optimality condition

For a differentiable convex f and feasible set X, a feasible x* is optimal if and only if

Text
∇f(x*)ᵀ(y - x*) ≥ 0    for every feasible y

In words: from x*, every feasible direction y - x* points "uphill or sideways" with respect to f. The gradient makes an angle of at most 90° with every feasible direction. If X is the whole space, the condition forces ∇f(x*) = 0, the familiar unconstrained rule.

Take a concrete example: minimize f(x) = (x - 3)² over X = [0, 2]. The gradient is 2(x - 3). At x* = 2 it equals -2. For any y ∈ [0, 2], ∇f(x*)(y - x*) = -2(y - 2) ≥ 0, because y ≤ 2. So x* = 2 is optimal: the constraint stops us at the boundary.

Python Check the optimality condition

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At (2.5, 1.5) the gradient is (-1, -1), and every feasible direction has a non-negative product with it. At (1, 1) the gradient is (-4, -2) and moving toward (2.5, 1.5) goes downhill, so (1, 1) is not optimal.

A picture of the geometry

At the optimum on a boundary, the negative gradient points out of the feasible set, so you cannot descend without leaving it.

Python Gradient points out at the optimum

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why this matters for the rest of the track

Everything that follows is built on this foundation.

  • Gradient descent (next chapter) finds a point with zero gradient; for convex f that point is optimal.
  • Constrained methods use the optimality condition to decide which constraints push back.
  • Duality and KKT conditions (chapter 5) turn the condition into a system of equations and inequalities.

If a problem is not convex as written, it may still become convex after a change of variables or after dropping a hard constraint. Recognizing hidden convexity is a valuable skill and a theme of the practice chapters.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which problem is a convex optimization problem?

    Convex objective, convex inequality constraints in the form g ≤ 0, and affine equalities define a convex problem.
  2. 2. In a convex problem, a local minimizer is

    The proof moves along the segment toward a better point and finds a contradiction.
  3. 3. If f is strictly convex and a minimizer exists, then

    Two distinct minimizers would give a midpoint with a strictly lower value.
  4. 4. With no constraints, the condition ∇f(x*)ᵀ(y - x*) ≥ 0 for all y reduces to

    Choosing y = x* - ∇f(x*) forces the gradient to be the zero vector.

Summary

  • A convex problem has a convex objective, convex inequality constraints g_i ≤ 0 and affine equality constraints.
  • Its feasible set is convex; every local minimizer is global; strict convexity makes the minimizer unique.
  • Optimality: ∇f(x*)ᵀ(y - x*) ≥ 0 for all feasible y, which reduces to ∇f(x*) = 0 without constraints.

Next: Gradient Descent