Local and Global Optima in Convex Optimization

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.