Optimality conditions for constrained convex problems - Mines Nancy

We now turn our attention to convex constrained optimization problems of the form

\begin{array}{ll} \minimize& f_0({x})\\ \st & x \in \Omega \end{array}

(1)

where $f_0$ is a convex function and $\Omega$ a convex set (by definition of a convex optimization problem). We also assume that $f_0$ is differentiable (i.e., $f_0 \in C^1$ ).

One of the key feature of convex optimization problems is that any local optimum is also a global optimum (see this theorem).

First-order characterization of optimal points for convex problems¶

Proof

${\Leftarrow}$ Let ${x}^\star\in \Omega$ such that the condition is satisfied. Then by convexity of $f_0$ , one has for ${y} \in \Omega$ , $f_0({y}) \geq f_0({x}^\star) + \nabla f_0({x}^\star)^\top ({y}-{x}^\star) \geq f_0({x}^\star)$ . Thus ${x}^\star$ is optimal.
${\Rightarrow}$ Suppose ${x}^\star \in \Omega$ is optimal but the conditions does not hold. There is some ${y} \in \Omega$ for which $\nabla f_0({x}^\star)^\top ({y} - {x}^\star) < 0$ . Consider ${z}(t) = t {y} + (1-t){x}^\star$ for $t \in [0, 1]$ . Since $\Omega$ is convex, ${z}(t) \in \Omega$ . Moreover, observe that $\frac{\mathrm{d}}{\mathrm{d}t} f_0({z}(t)) = \nabla f_0({z}(t))^\top ({y}-{x}^\star)$ and thus for $t=0$ one has $\frac{\mathrm{d}}{\mathrm{d}t} f_0({z}(t))\vert_{t=0} = \nabla f_0({x}^\star)^\top ({y}-{x}^\star) < 0$ . For small positive $t$ , we thus have $f_0({z}(t)) < f_0({x}^\star)$ which shows that ${x}^\star$ is not optimal. Hence we have a contradiction.

Geometric interpretation¶

If $\nabla f_0({x}^\star) \neq 0$ , the vector $-\nabla f_0({x}^\star)$ defines a supporting hyperplane to $\Omega$ at ${x}^\star$ .

In the context of Theorem 1, letting $a = -\nabla f_0(x^\star)$ the condition (2) rewrites as ${a}^\top {y} \leq {a}^\top {x}^\star$ for all $y \in \Omega$ . Therefore, $\lbrace {y} \mid {a}^\top {y} = {a}^\top {x}^\star \rbrace$ is a supporting hyperplane to $\Omega$ at point $x^\star$ .

Optimality condition illustration — A geometric illustration of the optimality condition for convex problems.

References¶

Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge University Press.

2.5 Optimality conditions for constrained convex problems

First-order characterization of optimal points for convex problems¶

Geometric interpretation¶