Global Optimal of Convex Optimization

 (P) minxRnf(x) s.t. xC\text{ (P) }\underset{x\in \R^n}{\min}f(x) \text{ s.t. } x\in C
  • f:RnRf:\R^n\to\R convex and continuously differentiable

  • CRnC\subseteq \R^n convex

If xˉ\bar{x} is a local minimizer, then xˉ\bar{x} is a global min

  • level sets of convex functions

  • first and second order optimization: f(x)=0\nabla f(x)=0; 2f(x)0\nabla^2f(x)\ge0

  • Optimality for constrained problems

➡️ Fact: If f:RnRf:\R^n\to\R convex, then the level sets [fτ]:={xRnf(x)τ}[f\le \tau]:=\{x\in \R^n \mid f(x)\in \tau\} are convex sets

Suppose xˉC\bar{x}\in C solves (P)

f(xˉ)τf(x),xC\underbrace{f(\bar{x})}_{\equiv \tau}\le f(x), \forall x\in C

[fτ]={xf(x)τ}[f\le \tau]= \{x\mid f(x)\le \tau \}

[fτ]C [f\le \tau]\cap C ⇒ solution set

Take any x,y[fτ]x,y\in [f\le \tau]

Show that λx+(1λ)y[fτ]\lambda x+(1-\lambda)y\in [f\le \tau] for λ[0,1]\lambda \in [0,1], f(x)τf(x)\le \tau, f(y)τf(y)\le \tau.

Because ff is conex,

f(λx+(1λ)y)λf(x)+(1λ)f(y)λτ+(1λ)τ=τ\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:CRf:C\to\R be continuously differentiable over CRnC\subseteq \R^n, where CC means convex set, then ff is convex iff

f(x)+f(x)T(zx)f(z),x,zCf(x)+\nabla f(x)^T(z-x)\le f(z), \forall x,z\in C

Proof Sketch: (⇒ only if direction)

By convexity of ff:

f(λz+(1λ)x)λf(z)+(1λ)f(x)f(\lambda z+(1-\lambda)x)\le \lambda f(z)+(1-\lambda)f(x)

f(λz+(1λ)x)f(x)λ[f(z)f(x)]f(\lambda z+(1-\lambda)x)-f(x)\le \lambda[f(z)-f(x)]

Dividing λ\lambda by both sides, f(λz+(1λ)x)f(x)λ[f(z)f(x)]\frac{f(\lambda z+(1-\lambda)x)-f(x)}{\lambda}\le [f(z)-f(x)]

limλ0f(λz+(1λ)x)f(x)λ[f(z)f(x)]=limλ0f(x+λ(zx))f(x)λ[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;zx)f(z)f(x)f’(x;z-x)\le f(z)-f(x)

Because ff continuously differentiable, f(x;zx)=f(x)T(zx)f’(x;z-x)=\nabla f(x)^T(z-x)

f(x)T(zx)f(z)f(x)\nabla f(x)^T(z-x)\le f(z)-f(x)

f(x)+f(x)T(zx)f(z),x,zf(x)+\nabla f(x)^T(z-x)\le f(z), \forall x,z

Consider the unconstrained differentiable problem

minxRnf(x) (f convex)\underset{x\in \R^n}{\min}f(x) \text{ (f convex)}

By convexity,

f(x)+f(x)T(zx)f(z),x,zRnf(x)+\nabla f(x)^T(z-x)\le f(z),\forall x,z\in \R^n

If xx^* is a local min, then

f(x)=0\nabla f(x^*)=0

x=xx=x^*

f(x)f(z),xRnf(x^*)\le f(z), \forall x\in\R^n

For convex unconstrained problems,

StationarityGlobal Optimality\text{Stationarity} \Leftrightarrow \text{Global Optimality}

For f:CRf:C\to\R (CRnC\subseteq \R^n convex) twice continuous differentiable then ff is convex iff

2f(x)0,xC\nabla^2 f(x)\ge 0, \forall x\in C

Example. f(x)=12x2f(x)=\frac{1}{2}\lVert x\rVert^2

f(x)=x\nabla f(x)=x

2f(x)=I>0\nabla^2 f(x)=I\gt 0

Unconstrained Case (C=RnC=\R^n)

xarg minxRnf(x)f(x;xx)=f(x)T(xx)0f(x)=0\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 (CRnC \subset \R^n)

xarg minxCf(x)f(x;xx)=f(x)T(xx)0,xCx^* \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 ff.

f(x)T(xx)0,xC-\nabla f(x^*)^T(x-x^*)\le0,\forall x\in C

Last updated