Optimality for Convex Optimization

min⁡x∈Rnf(x) subject to x∈C⊆Rn\underset{x\in \R^n}{\min} f(x) \text{ subject to } x\in C\subseteq \R^n

  • f:Rn→Rf:\R^n\to \R continuous differentiable and convex

  • C⊆RnC\subseteq \R^n convex

Unconstrained (C⊆RnC\subseteq \R^n)

x∗∈arg min⁡x∈Rn⇔0≤f’(x∗;x−x∗),∀x∈Rn=∇f(x∗)T(x−x∗)⇔∇f(x∗)=0\begin{aligned}x^* \in \underset{x\in \R^n}{\argmin} &\Leftrightarrow \begin{aligned}0&\le f’(x^*;x-x^*), \forall x\in\R^n \\ &=\nabla f(x^*)^T(x-x^*)\end{aligned} \\ &\Leftrightarrow \nabla f(x^*)=0\end{aligned}

Constrained (C⊆RnC\subseteq \R^n)

x∗∈arg min⁡x∈Cf(x)⇔0≤f’(x∗;x−x∗),∀x∈C=∇f(x∗)T(x−x∗),∀x∈Cx^* \in \underset{x\in C}{\argmin}f(x) \Leftrightarrow \begin{aligned}0 &\le f’(x^*;x-x^*),\forall x\in C\\&=\nabla f(x^*)^T(x-x^*),\forall x\in C\end{aligned}

directional derivative is non-negative in all feasible directions

−∇f(x∗)∈NR+2(x∗)⇔−∇f(x∗)T(x−x∗)≤0,∀x∈C-\nabla f(x^*)\in N_{\R_+^2}(x^*)\Leftrightarrow -\nabla f(x^*)^T(x-x^*)\le 0,\forall x\in C

Normal Cone of a set C⊆RnC\subseteq \R^n of a point x∈Cx\in C

NC(x)={g∈Rn∣gT(z−x)≤0,∀z∈C}N_C(x)=\{g\in \R^n \mid g^T(z-x)\le 0, \forall z\in C\}

Example. C={x∈Rn∣Ax=b}C= \{x\in \R^n \mid Ax=b \}

NC(x)={g∈Rn∣gT(z−x)≤0,∀z∈C}={g∈Rn∣gTd≤0,∀d∈null(A)}={g∈Rn∣gTd=0,∀d∈null(A)}=null(A)⊥=range(AT)\begin{aligned}N_C(x)&=\left\{g\in \R^n \mid g^T(z-x)\le 0, \forall z\in C\right\}\\&=\left\{g\in\R^n\mid g^Td \le0,\forall d\in null(A)\right\}\\&=\left\{g\in \R^n \mid g^Td=0,\forall d\in null(A)\right\}\\&=null(A)^{\perp}\\&=range(A^T)\end{aligned}

if z∈Cz\in C, and x∈Cx\in C

Ax=bAx=b

Az=bAz=b

A(z−x)=Az−Ax=b−b=0A(z-x)=Az-Ax=b-b=0

range(A)⊕null(AT)=Rmrange(A) \oplus null(A^T)=\R^m

range(AT)⊕null(A)=Rnrange(A^T)\oplus null(A)=\R^n

Linearly Constrained Optimization

min⁡x∈Rnf(x) subject to Ax=b⇔x∈C\underset{x\in\R^n}{\min}f(x)\text{ subject to } Ax=b \Leftrightarrow x\in C

x∗x^* is a minimizer only if

{∇f(x∗)=ATy for some y∈RmAx∗=b\left \{ \begin{aligned}&\nabla f(x^*)=A^Ty\text{ for some } y\in\R^m \\ &Ax^*=b\end{aligned}\right., where AA is a m×nm\times n matrix.

New Lagrange of Normal Cones

−∇f(x∗)∈NC(x∗),x∗∈C⇔−∇f(x∗)∈range(AT),Ax∗=b⇔∃y∗ s.t. −∇f(x∗)=ATy\begin{aligned}&-\nabla f(x^*)\in N_C(x^*), x^*\in C \\ \Leftrightarrow & -\nabla f(x^*)\in range(A^T),Ax^*=b \\ \Leftrightarrow & \exist y^* \text{ s.t. } -\nabla f(x^*)=A^Ty\end{aligned}

PreviousGlobal Optimal of Convex OptimizationNextProjection Onto Convex Sets

Last updated