Computational Optimization
  • Computational Optimization
  • Basics
  • QR Factorization
  • Regularization
  • Gradients
  • Nonlinear Least-Squares
  • Gradient Descent
  • Descent Methods
  • Scaled Descent
  • Cholesky Factorization
  • Linear Constraints
  • Convex Set
  • Convex Functions
  • Global Optimal of Convex Optimization
  • Optimality for Convex Optimization
  • Projection Onto Convex Sets
  • Stochastic Gradient Descent (SGD)
Powered by GitBook
On this page
  • Unconstrained ()
  • Constrained ()
  • Normal Cone of a set of a point
  • Linearly Constrained Optimization
  • New Lagrange of Normal Cones

Optimality for Convex Optimization

PreviousGlobal Optimal of Convex OptimizationNextProjection Onto Convex Sets

Last updated 1 year ago

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^nx∈Rnmin​f(x) subject to x∈C⊆Rn

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

  • C⊆RnC\subseteq \R^nC⊆Rn convex

Unconstrained (C⊆RnC\subseteq \R^nC⊆Rn)

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}x∗∈x∈Rnargmin​​⇔0​≤f’(x∗;x−x∗),∀x∈Rn=∇f(x∗)T(x−x∗)​⇔∇f(x∗)=0​

Constrained (C⊆RnC\subseteq \R^nC⊆Rn)

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}x∗∈x∈Cargmin​f(x)⇔0​≤f’(x∗;x−x∗),∀x∈C=∇f(x∗)T(x−x∗),∀x∈C​

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−∇f(x∗)∈NR+2​​(x∗)⇔−∇f(x∗)T(x−x∗)≤0,∀x∈C

Linearly Constrained Optimization

New Lagrange of Normal Cones

Normal Cone of a set C⊆RnC\subseteq \R^nC⊆Rn of a point x∈Cx\in Cx∈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\}NC​(x)={g∈Rn∣gT(z−x)≤0,∀z∈C}

Example. C={x∈Rn∣Ax=b}C= \{x\in \R^n \mid Ax=b \}C={x∈Rn∣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}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)​

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

Ax=bAx=bAx=b

Az=bAz=bAz=b

A(z−x)=Az−Ax=b−b=0A(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^mrange(A)⊕null(AT)=Rm

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

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 Cx∈Rnmin​f(x) subject to Ax=b⇔x∈C

x∗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.{​∇f(x∗)=ATy for some y∈RmAx∗=b​, where AAA is a m×nm\times nm×n matrix.

−∇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}⇔⇔​−∇f(x∗)∈NC​(x∗),x∗∈C−∇f(x∗)∈range(AT),Ax∗=b∃y∗ s.t. −∇f(x∗)=ATy​