$$ \underset{x\in \R^n}{\min} f(x) \text{ subject to } x\in C\subseteq \R^n $$

• $f:\R^n\to \R$ continuous differentiable and convex
• $C\subseteq \R^n$ convex

Unconstrained ($C\subseteq \R^n$)

$\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\subseteq \R^n$)

$$ x^* \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

$$ -\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\subseteq \R^n$ of a point $x\in C$

$$ N_C(x)=\{g\in \R^n \mid g^T(z-x)\le 0, \forall z\in C\} $$

Example. $C=\{x\in \R^n \mid Ax=b\}$

$$ \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\in C$, and $x\in C$

$Ax=b$

$Az=b$

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

$range(A) \oplus null(A^T)=\R^m$

$range(A^T)\oplus null(A)=\R^n$

Linearly Constrained Optimization

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