优化问题

作者: 9933fdf22087 | 来源:发表于2019-06-21 11:26 被阅读2次

优化问题

凸优化

1.基本概念：

定义：函数 $L(\cdot)$ 是凸函数当且仅当对定义域中的任意两点x,y和任意实数 $\lambda\in[0,1]$ 总有 $L(\lambda x+(1-\lambda) y) \leqslant \lambda L(x)+(1-\lambda) L(y)$

直观解释：凸函数曲面上任意两点的连线而成的线段，其上的任意一点都不会处于该函数曲面的下方。

image.png

2.实例讲解：

对于二分类问题， $Y=\{1,-1\}$ ,假设模型参数为 $\theta$ ，则逻辑回归的优化问题为：

$\min _{\theta} L(\theta)=\sum_{i=1}^{n} \log \left(1+\exp \left(-y_{i} \theta^{\mathrm{T}} x_{i}\right)\right)$

可以通过计算目标函数的二阶Hessian矩阵来验证：

$L_{i}(\theta)=\log \left(1+\exp \left(-y_{i} \theta^{\top} x_{i}\right)\right)$

对该函数求一阶导，得到：

$\begin{aligned} \nabla L_{i}(\theta) &=\frac{1}{1+\exp \left(-y_{i} \theta^{\mathrm{T}} x_{i}\right)} \exp \left(-y_{i} \theta^{\mathrm{T}} x_{i}\right) \cdot\left(-y_{i} x_{i}\right) \\ &=\frac{-y_{i} x_{i}}{1+\exp \left(y_{i} \theta^{\mathrm{T}} x_{i}\right)} \end{aligned}$

继续求导，得到函数的Hessian矩阵：
$\begin{aligned} \nabla^{2} L_{i}(\theta) &=\frac{y_{i} x_{i} \cdot \exp \left(y_{i} \theta^{\mathrm{T}} x_{i}\right) \cdot y_{i} x_{i}^{\mathrm{T}}}{\left(1+\exp \left(y_{i} \theta^{\mathrm{T}} x_{i}\right)\right)^{2}} \\ &=\frac{\exp \left(y_{i} \theta^{\mathrm{T}} x_{i}\right)}{\left(1+\exp \left(y_{i} \theta^{\mathrm{T}} x_{i}\right)\right)^{2}} x_{i} x_{i}^{\mathrm{T}} \end{aligned}$

该矩阵满足半正定的性质 $\nabla^{2} L_{i}(\theta) \succeq 0$ ，因此 $\nabla^{2} L(\theta)=\sum_{i=1}^{n} \nabla^{2} L_{i}(\theta) \geq 0$ ，函数 $L(\cdot)$ 为凸函数。对于凸优化问题，所有的局部极小值都是全局极小值。

主成分分析对应的优化问题是非凸优化问题。令 $X=\left[x_{1}, \ldots, x_{n}\right]$ 为数据中心后构成的矩阵，则主成分分析的优化问题为 $\min _{V V^{T}=I_{k}} L(V)=\left\|X-V^{T} V X\right\|_{F}^{2}$ ，通过凸函数的定义可以验证该优化问题的目标函数为非凸函数。令 $V^*$ 为优化问题的全局极小值，则 $-V^*$ 也是该问题的全局极小值，且有：
$\begin{aligned} L\left(\frac{1}{2} V^{*}+\frac{1}{2}\left(-V^{*}\right)\right)=L(0) &=\|X\|_{\mathrm{F}}^{2}>\left\|X-V^{* \mathrm{T}} V^{*} X\right\|_{\mathrm{F}}^{2} \\ &=\frac{1}{2} L\left(V^{*}\right)+\frac{1}{2} L\left(-V^{*}\right) \end{aligned}$