Local and Global Optima in Convex Optimization

L. El Ghaoui

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^*$ be a local minimizer of $f_0$ on the set $\mathbf{X}$ , and let $y \in \mathbf{X}$ . By definition, $x^* \in \backslash$ bf dom $f_0$ . We need to prove that $f_0(y) \geq f_0\left(x^*\right)=p^*$ . There is nothing to prove if $f_0(y)=+\infty$ , so let us assume that $y \in \backslash$ bf dom $f_0$ . By convexity of $f_0$ and $\mathbf{X}$ , we have $x_\theta:=\theta y+(1-\theta) x^* \in \mathbf{X}$ , and:

$f_0\left(x_\theta\right)-f_0\left(x^*\right) \leq \theta\left(f_0(y)-f_0\left(x^*\right)\right) .$

Since $x^*$ 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) \geq f_0\left(x^*\right)$ , as claimed.
Also, the optimal set is convex, since it can be written

$\mathbf{X}^{\text {opt }}=\left\{x \in \mathbf{R}^n: f_0(x) \leq p^*, \quad x \in \mathbf{X}\right\} .$

This ends our proof.

Local and Global Optima in Convex Optimization

License

Share This Book