Local and Global Optima in Convex Optimization

Theorem: Global vs. local optima in convex optimization

For convex problems, any locally optimal point is globally optimal. In addition, the optimal set is convex.

Proof: Let x^ast be a local minimizer of f_0 on the set mathbf{X}, and let y in mathbf{X}. By definition, x^ast in mbox{bf dom} f_0. We need to prove that f_0(y) ge f_0(x^ast) = p^ast. There is nothing to prove if f_0(y) = +infty, so let us assume that y in mbox{bf dom} f_0. By convexity of f_0 and mathbf{X}, we have x_theta := theta y + (1-theta) x^ast in mathbf{X}, and:

 f_0(x_theta) - f_0(x^ast) le theta (f_0(y) - f_0(x^ast)).

Since x^ast is a local minimizer, the left-hand side in this inequality is nonnegative for all small enough values of theta > 0. We conclude that the right hand side is nonnegative, i.e., f_0(y) ge f_0(x^ast), as claimed.

Also, the optimal set is convex, since it can be written

 mathbf{X}^{rm opt} = left{ x in mathbf{R}^n ~:~ f_0(x) le p^ast, ;; x in mathbf{X} right} .

This ends our proof.