凸优化 - 可微函数

---

---

设S是$\mathbb{R}^n$中的一个非空开集，则当存在一个称为梯度向量的向量$\bigtriangledown f\left ( \hat{x} \right )$和一个函数$\alpha :\mathbb{R}^n\rightarrow \mathbb{R}$使得以下等式成立时，$f:S\rightarrow \mathbb{R}$在$\hat{x} \in S$处可微：

$f\left ( x \right )=f\left ( \hat{x} \right )+\bigtriangledown f\left ( \hat{x} \right )^T\left ( x-\hat{x} \right )+\left \| x-\hat{x} \right \|\alpha \left ( \hat{x}, x-\hat{x} \right ), \forall x \in S$，其中

$\alpha \left (\hat{x}, x-\hat{x} \right )\rightarrow 0$，$\bigtriangledown f\left ( \hat{x} \right )=\left [ \frac{\partial f}{\partial x_1}\frac{\partial f}{\partial x_2}...\frac{\partial f}{\partial x_n} \right ]_{x=\hat{x}}^{T}$

定理

设S是$\mathbb{R}^n$中的一个非空开凸集，且$f:S\rightarrow \mathbb{R}$在S上可微。则f是凸函数当且仅当对于$x_1,x_2 \in S$，$\bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right ) \leq f\left ( x_1 \right )-f\left ( x_2 \right )$

证明

设f是一个凸函数。即，对于$x_1,x_2 \in S, \lambda \in \left ( 0, 1 \right )$

$f\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

$ \Rightarrow f\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]\leq \lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )+f\left ( x_2 \right )$

$ \Rightarrow\lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )\geq f\left ( x_2+\lambda \left ( x_1-x_2 \right ) \right )-f\left ( x_2 \right )$

$\Rightarrow \lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )\geq f\left ( x_2 \right )+\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )\lambda +$

$\left \| \lambda \left ( x_1-x_2 \right ) \right \|\alpha \left ( x_2,\lambda\left (x_1 - x_2 \right ) \right )-f\left ( x_2 \right )$

其中$\alpha\left ( x_2, \lambda\left (x_1 - x_2 \right ) \right )\rightarrow 0$，当$\lambda \rightarrow 0$

两边除以$\lambda$，得到：

$f\left ( x_1 \right )-f\left ( x_2 \right ) \geq \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right )

逆命题

设对于$x_1,x_2 \in S$，$\bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right ) \leq f\left ( x_1 \right )-f \left ( x_2 \right )$

要证明f是凸函数。

由于S是凸集，$x_3=\lambda x_1+\left(1-\lambda \right)x_2 \in S, \lambda \in \left ( 0, 1 \right )$

由于$x_1, x_3 \in S$，因此

$f\left ( x_1 \right )-f \left ( x_3 \right ) \geq \bigtriangledown f\left ( x_3 \right )^T \left ( x_1 -x_3\right )$

$ \Rightarrow f\left ( x_1 \right )-f \left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T \left ( x_1 - \lambda x_1-\left (1-\lambda \right )x_2\right )$

$ \Rightarrow f\left ( x_1 \right )-f \left ( x_3 \right )\geq \left ( 1- \lambda\right )\bigtriangledown f\left ( x_3 \right )^T \left ( x_1 - x_2\right )$

由于$x_2, x_3 \in S$，因此

$f\left ( x_2 \right )-f\left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-x_3 \right )$

$\Rightarrow f\left ( x_2 \right )-f\left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-\lambda x_1-\left ( 1-\lambda \right )x_2 \right )$

$\Rightarrow f\left ( x_2 \right )-f\left ( x_3 \right )\geq \left ( -\lambda \right )\bigtriangledown f\left ( x_3 \right )^T\left ( x_1-x_2 \right )$

因此，结合上述等式，得到：

$\lambda \left ( f\left ( x_1 \right )-f\left ( x_3 \right ) \right )+\left ( 1- \lambda \right )\left ( f\left ( x_2 \right )-f\left ( x_3 \right ) \right )\geq 0$

$\Rightarrow f\left ( x_3\right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

定理

设S是$\mathbb{R}^n$中的一个非空开凸集，且$f:S \rightarrow \mathbb{R}$在S上可微，则f在S上是凸函数当且仅当对于任何$x_1,x_2 \in S$，$\left ( \bigtriangledown f \left ( x_2 \right )-\bigtriangledown f \left ( x_1 \right ) \right )^T \left ( x_2-x_1 \right ) \geq 0$

证明

设f是一个凸函数，则根据之前的定理：

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )\leq f\left ( x_1 \right )-f\left ( x_2 \right )$ 且

$\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq f\left ( x_2 \right )-f\left ( x_1 \right )$

将上述两个等式相加，得到：

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )+\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x_2 \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x_1-x_2 \right )\leq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x_2 \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x_2-x_1 \right )\geq 0$

逆命题

设对于任何$x_1,x_2 \in S$，$\left (\bigtriangledown f \left ( x_2\right )- \bigtriangledown f \left ( x_1\right )\right )^T \left ( x_2-x_1\right )\geq 0$

要证明f是凸函数。

设$x_1,x_2 \in S$，则根据均值定理，$\frac{f\left ( x_1\right )-f\left ( x_2\right )}{x_1-x_2}=\bigtriangledown f\left ( x\right ),x \in \left ( x_1,x_2\right ) \Rightarrow x= \lambda x_1+\left ( 1-\lambda\right )x_2$，因为S是一个凸集。

$\Rightarrow f\left ( x_1 \right )- f\left ( x_2 \right )=\left ( \bigtriangledown f\left ( x \right )^T \right )\left ( x_1-x_2 \right )$

对于$x,x_1$，我们知道：

$\left ( \bigtriangledown f\left ( x \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x-x_1 \right )\geq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( \lambda x_1+\left ( 1-\lambda \right )x_2-x_1 \right )\geq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x \right )- \bigtriangledown f\left ( x_1 \right )\right )^T\left ( 1- \lambda \right )\left ( x_2-x_1 \right )\geq 0$

$\Rightarrow \bigtriangledown f\left ( x \right )^T\left ( x_2-x_1 \right )\geq \bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )$

结合上述等式，得到：

$\Rightarrow \bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq f\left ( x_2 \right )-f\left ( x_1 \right )$

因此，根据最后一个定理，f是一个凸函数。

二阶可微函数

设S是$\mathbb{R}^n$的一个非空子集，且$f:S\rightarrow \mathbb{R}$，则当存在一个向量$\bigtriangledown f\left (\bar{x}\right )$，一个nXn矩阵$H\left (x\right )$(称为Hessian矩阵)和一个函数$\alpha:\mathbb{R}^n \rightarrow \mathbb{R}$使得以下等式成立时，f在$\bar{x} \in S$处二阶可微：$f\left ( x \right )=f\left ( \bar{x}+x-\bar{x} \right )=f\left ( \bar{x} \right )+\bigtriangledown f\left ( \bar{x} \right )^T\left ( x-\bar{x} \right )+\frac{1}{2}\left ( x-\bar{x} \right )^T H\left ( \bar{x} \right )\left ( x-\bar{x} \right )+\left\|x-\bar{x}\right\|^2\alpha\left(\bar{x}, x-\bar{x}\right)$

其中 $ \alpha \left ( \bar{x}, x-\bar{x} \right )\rightarrow 0$，当$x\rightarrow \bar{x}$