> For the complete documentation index, see [llms.txt](https://muhans-notebook.gitbook.io/computational-optimization/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://muhans-notebook.gitbook.io/computational-optimization/global-optimal-of-convex-optimization.md).
# Global Optimal of Convex Optimization
$$
\text{ (P) }\underset{x\in \R^n}{\min}f(x) \text{ s.t. } x\in C
$$
* $$f:\R^n\to\R$$ convex and continuously differentiable
* $$C\subseteq \R^n$$ convex
If $$\bar{x}$$ is a local minimizer, then $$\bar{x}$$ is a global min
* level sets of convex functions
* first and second order optimization: $$\nabla f(x)=0$$; $$\nabla^2f(x)\ge0$$
* Optimality for constrained problems
> ➡️ Fact: If $$f:\R^n\to\R$$ convex, then the level sets $$\[f\le \tau]:={x\in \R^n \mid f(x)\in \tau}$$ are convex sets
Suppose $$\bar{x}\in C$$ solves (P)
$$\underbrace{f(\bar{x})}\_{\equiv \tau}\le f(x), \forall x\in C$$
$$\[f\le \tau]= {x\mid f(x)\le \tau }$$
$$\[f\le \tau]\cap C$$ ⇒ solution set
Take any $$x,y\in \[f\le \tau]$$
Show that $$\lambda x+(1-\lambda)y\in \[f\le \tau]$$ for $$\lambda \in \[0,1]$$, $$f(x)\le \tau$$, $$f(y)\le \tau$$.
Because $$f$$ is conex,
$$\begin{aligned}f(\lambda x+(1-\lambda)y)&\le\lambda f(x)+(1-\lambda)f(y) \ & \le \lambda\tau+(1-\lambda)\tau \ &=\tau\end{aligned}$$$$\checkmark$$
### First-Order Characterization
> ✅ ***Theorem.*** Let $$f:C\to\R$$ be continuously differentiable over $$C\subseteq \R^n$$, where $$C$$ means convex set, then $$f$$ is convex iff
>
> $$
> f(x)+\nabla f(x)^T(z-x)\le f(z), \forall x,z\in C
> $$
Proof Sketch: (⇒ only if direction)
By convexity of $$f$$:
$$f(\lambda z+(1-\lambda)x)\le \lambda f(z)+(1-\lambda)f(x)$$
$$f(\lambda z+(1-\lambda)x)-f(x)\le \lambda\[f(z)-f(x)]$$
Dividing $$\lambda$$ by both sides, $$\frac{f(\lambda z+(1-\lambda)x)-f(x)}{\lambda}\le \[f(z)-f(x)]$$
$$\begin{aligned}&\underset{\lambda\to0}{\lim}\frac{f(\lambda z+(1-\lambda)x)-f(x)}{\lambda}\le \[f(z)-f(x)] \ =&\underset{\lambda\to0}{\lim}\frac{f(x+\lambda(z-x))-f(x)}{\lambda}\le \[f(z)-f(x)]\end{aligned}$$
$$f’(x;z-x)\le f(z)-f(x)$$
Because $$f$$ continuously differentiable, $$f’(x;z-x)=\nabla f(x)^T(z-x)$$
⇒ $$\nabla f(x)^T(z-x)\le f(z)-f(x)$$
⇒ $$f(x)+\nabla f(x)^T(z-x)\le f(z), \forall x,z$$
Consider the unconstrained differentiable problem
$$
\underset{x\in \R^n}{\min}f(x) \text{ (f convex)}
$$
By convexity,
$$
f(x)+\nabla f(x)^T(z-x)\le f(z),\forall x,z\in \R^n
$$
If $$x^\*$$ is a local min, then
$$
\nabla f(x^\*)=0
$$
$$x=x^\*$$
$$
f(x^\*)\le f(z), \forall x\in\R^n
$$
For convex unconstrained problems,
$$
\text{Stationarity} \Leftrightarrow \text{Global Optimality}
$$
For $$f:C\to\R$$ ($$C\subseteq \R^n$$ convex) twice continuous differentiable then $$f$$ is convex iff
$$
\nabla^2 f(x)\ge 0, \forall x\in C
$$
***Example.*** $$f(x)=\frac{1}{2}\lVert x\rVert^2$$
$$\nabla f(x)=x$$
$$\nabla^2 f(x)=I\gt 0$$
### Unconstrained Case ($$C=\R^n$$)
$$
\begin{aligned}x^\* \in \underset{x\in\R^n}{\argmin}f(x)&\Leftrightarrow f’(x^*;x-x^*)=\nabla f(x^*)^T(x-x^*)\ge 0\\&\Leftrightarrow f(x^\*)=0\end{aligned}
$$
### Constrained Case ($$C \subset \R^n$$)
$$
x^\* \in \underset{x\in C}{\argmin}f(x)\Leftrightarrow f’(x^*;x-x^*)=\nabla f(x^*)^T(x-x^*)\ge 0,\forall x\in C
$$
⇒ All feasible directions are non-decreasing on $$f$$.
⇒ $$-\nabla f(x^*)^T(x-x^*)\le0,\forall x\in C$$
