凸优化 - 可微函数
设 S 是 $\mathbb{R}^n$ 中的一个非空开集，则如果存在一个向量 $\bigtriangledown f\left ( \hat{x} ight )$（称为梯度向量）和一个函数 $\alpha :\mathbb{R}^n ightarrow \mathbb{R}$，并且
，则称 $f:S ightarrow \mathbb{R}$ 在 $\hat{x} \in S$ 处可微。$f\left ( x ight )=f\left ( \hat{x} ight )+\bigtriangledown f\left ( \hat{x} ight )^T\left ( x-\hat{x} ight )+\left \| x=\hat{x} ight \|\alpha \left ( \hat{x}, x-\hat{x} ight ), \forall x \in S$ 其中
$\alpha \left (\hat{x}, x-\hat{x} ight ) ightarrow 0 \bigtriangledown f\left ( \hat{x} ight )=\left [ \frac{\partial f}{\partial x_1}\frac{\partial f}{\partial x_2}...\frac{\partial f}{\partial x_n} ight ]_{x=\hat{x}}^{T}$
定理
设 S 为 $\mathbb{R}^n$ 中的非空开凸集，并设 $f:S ightarrow \mathbb{R}$ 在 S 上可微。那么，当且仅当对于 $x_1,x_2 \in S, \bigtriangledown f\left ( x_2 ight )^T \left ( x_1-x_2 ight ) \leq f\left ( x_1 ight )-f\left ( x_2 ight )$，f 才是凸函数。
证明
设 f 为凸函数。即，对于 $x_1,x_2 \in S, \lambda \in \left ( 0, 1 ight )$
$f\left [ \lambda x_1+\left ( 1-\lambda ight )x_2 ight ]\leq \lambda f\left ( x_1 ight )+\left ( 1-\lambda ight )f\left ( x_2 ight )$
$ \Rightarrow f\left [ \lambda x_1+\left ( 1-\lambda ight )x_2 ight ]\leq \lambda \left ( f\left ( x_1 ight )-f\left ( x_2 ight ) ight )+f\left ( x_2 ight )$
$ \Rightarrow\lambda \left ( f\left ( x_1 ight )-f\left ( x_2 ight ) ight )\geq f\left ( x_2+\lambda \left ( x_1-x_2 ight ) ight )-f\left ( x_2 ight )$
$\Rightarrow \lambda \left ( f\left ( x_1 ight )-f\left ( x_2 ight ) ight )\geq f\left ( x_2 ight )+\bigtriangledown f\left ( x_2 ight )^T\left ( x_1-x_2 ight )\lambda +$
其中 $\alpha\left ( x_2, \lambda\left (x_1 - x_2 ight ) ight ) ightarrow 0$ 等于$\lambda ightarrow 0$
两边除以 $\lambda$，我们得到 −
$f\left ( x_1 ight )-f\left ( x_2 ight ) \geq \bigtriangledown f\left ( x_2 ight )^T \left ( x_1-x_2 ight )$
逆
设对于 $x_1,x_2 \in S, \bigtriangledown f\left ( x_2 ight )^T \left ( x_1-x_2 ight ) \leq f\left ( x_1 ight )-f \left ( x_2 ight )$
证明 f 是凸的。
由于 S 是凸的，$x_3=\lambda x_1+\left (1-\lambda ight )x_2 \in S, \lambda \in \left ( 0, 1 ight )$
由于 $x_1, x_3 \in S$，因此
$f\left ( x_1 ight )-f \left ( x_3 ight ) \geq \bigtriangledown f\left ( x_3 ight )^T \left ( x_1 -x_3 ight )$
$ \Rightarrow f\left ( x_1 ight )-f \left ( x_3 ight )\geq \bigtriangledown f\left ( x_3 ight )^T \left ( x_1 - \lambda x_1-\left (1-\lambda ight )x_2 ight )$
$ \Rightarrow f\left ( x_1 ight )-f \left ( x_3 ight )\geq \left ( 1- \lambda ight )\bigtriangledown f\left ( x_3 ight )^T \left ( x_1 - x_2 ight )$
由于，$x_2, x_3 \in S$ 因此
$f\left ( x_2 ight )-f\left ( x_3 ight )\geq \bigtriangledown f\left ( x_3 ight )^T\left ( x_2-x_3 ight )$
$\Rightarrow f\left ( x_2 ight )-f\left ( x_3 ight )\geq \bigtriangledown f\left ( x_3 ight )^T\left ( x_2-\lambda x_1-\left ( 1-\lambda ight )x_2 ight )$
$\Rightarrow f\left ( x_2 ight )-f\left ( x_3 ight )\geq \left ( -\lambda ight )\bigtriangledown f\left ( x_3 ight )^T\left ( x_1-x_2 ight )$
因此，结合上述方程，我们得到 −
$\lambda \left ( f\left ( x_1 ight )-f\left ( x_3 ight ) ight )+\left ( 1- \lambda ight )\left ( f\left ( x_2 ight )-f\left ( x_3 ight ) ight )\geq 0$
$\Rightarrow f\left ( x_3 ight )\leq \lambda f\left ( x_1 ight )+\left ( 1-\lambda ight )f\left ( x_2 ight )$
定理
设 S 为 $\mathbb{R}^n$ 中的非空开凸集，且设 $f:S ightarrow \mathbb{R}$ 在 S 上可微，则 f 在 S 上凸当且仅当对于任何 $x_1,x_2 \in S,\left ( \bigtriangledown f \left ( x_2 ight )-\bigtriangledown f \left ( x_1 ight ) ight )^T \left ( x_2-x_1 ight ) \geq 0$
证明
设 f 为凸函数，则利用前面的定理 −
$\bigtriangledown f\left ( x_2 ight )^T\left ( x_1-x_2 ight )\leq f\left ( x_1 ight )-f\left ( x_2 ight )$ 且
$\bigtriangledown f\left ( x_1 ight )^T\left ( x_2-x_1 ight )\leq f\left ( x_2 ight )-f\left ( x_1 ight )$
将上述两个方程相加，得到 −
$\bigtriangledown f\left ( x_2 ight )^T\left ( x_1-x_2 ight )+\bigtriangledown f\left ( x_1 ight )^T\left ( x_2-x_1 ight )\leq 0$
$\Rightarrow \left ( \bigtriangledown f\left ( x_2 ight )-\bigtriangledown f\left ( x_1 ight ) ight )^T\left ( x_1-x_2 ight )\leq 0$
$\Rightarrow \left ( \bigtriangledown f\left ( x_2 ight )-\bigtriangledown f\left ( x_1 ight ) ight )^T\left ( x_2-x_1 ight )\geq 0$
逆
设对于任意 $x_1,x_2 \in S,\left (\bigtriangledown f \left ( x_2 ight )- \bigtriangledown f \left ( x_1 ight ) ight )^T \left ( x_2-x_1 ight )\geq 0$
证明 f 是凸的。
设 $x_1,x_2 \in S$，因此根据均值定理，$\frac{f\left ( x_1 ight )-f\left ( x_2 ight )}{x_1-x_2}=\bigtriangledown f\left ( x ight ),x \in \left ( x_1-x_2 ight ) \Rightarrow x= \lambda x_1+\left ( 1-\lambda ight )x_2$ 因为 S 是凸集。
$\Rightarrow f\left ( x_1 ight )- f\left ( x_2 ight )=\left ( \bigtriangledown f\left ( x ight )^T ight )\left ( x_1-x_2 ight )$
对于 $x,x_1$，我们知道 −
$\left ( \bigtriangledown f\left ( x ight )-\bigtriangledown f\left ( x_1 ight ) ight )^T\left ( x-x_1 ight )\geq 0$
$\Rightarrow \left ( \bigtriangledown f\left ( x ight )-\bigtriangledown f\left ( x_1 ight ) ight )^T\left ( \lambda x_1+\left ( 1-\lambda ight )x_2-x_1 ight )\geq 0$
$\Rightarrow \left ( \bigtriangledown f\left ( x ight )- \bigtriangledown f\left ( x_1 ight ) ight )^T\left ( 1- \lambda ight )\left ( x_2-x_1 ight )\geq 0$
$\Rightarrow \bigtriangledown f\left ( x ight )^T\left ( x_2-x_1 ight )\geq \bigtriangledown f\left ( x_1 ight )^T\left ( x_2-x_1 ight )$
结合上述方程，我们得到−
$\Rightarrow \bigtriangledown f\left ( x_1 ight )^T\left ( x_2-x_1 ight )\leq f\left ( x_2 ight )-f\left ( x_1 ight )$
因此，使用最后一个定理，f 是一个凸函数。
二次可微函数
设 S 是 $\mathbb{R}^n$ 的一个非空子集，并设 $f:S ightarrow \mathbb{R}$，则如果存在一个向量 $\bigtriangledown f\left (\bar{x} ight )、一个 \:nXn$ 矩阵 $H\left (x ight )$（称为 Hessian 矩阵）和一个函数，则称 f 在 $\bar{x} \in S$ 处是二次可微的$\alpha:\mathbb{R}^n ightarrow \mathbb{R}$ 使得 $f\left ( x ight )=f\left ( \bar{x}+x-\bar{x} ight )=f\left ( \bar{x} ight )+\bigtriangledown f\left ( \bar{x} ight )^T\left ( x-\bar{x} ight )+\frac{1}{2}\left ( x-\bar{x} ight )H\left ( \bar{x} ight )\left ( x-\bar{x} ight )$
其中 $ \alpha \left ( \bar{x}, x-\bar{x} ight ) ightarrow Oasx ightarrow \bar{x}$
