0%

凸优化

优化问题

凸优化

1.基本概念:

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

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

2.实例讲解:

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

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

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

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

对该函数求一阶导,得到:

Li(θ)=11+exp(yiθTxi)exp(yiθTxi)(yixi)=yixi1+exp(yiθTxi)\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矩阵:
2Li(θ)=yixiexp(yiθTxi)yixiT(1+exp(yiθTxi))2=exp(yiθTxi)(1+exp(yiθTxi))2xixiT\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}

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

主成分分析对应的优化问题是非凸优化问题。令X=[x1,,xn]X=\left[x_{1}, \ldots, x_{n}\right]为数据中心后构成的矩阵,则主成分分析的优化问题为minVVT=IkL(V)=XVTVXF2\min_{V V^{T}=I_{k}} L(V)=\left\|X-V^{T} V X\right\|_{F}^{2},通过凸函数的定义可以验证该优化问题的目标函数为非凸函数。令 VV^*为优化问题的全局极小值,

则 $ -V^* $也是该问题的全局极小值,且有:

L(12V+12(V))=L(0)=XF2>XVTVXF2=12L(V)+12L(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}

这不满足凸函数的定义,因此主成分分析的优化问题为非凸优化问题。

3.知识补充:

定义:设AA是实对称矩阵。如果对任意的实非零列向量xxxTAx0x^TAx≥0,就称A为半正定矩阵。如果xTAx>0x^TAx>0,则为正定矩阵。
几何解释:正定/半正定矩阵AA指的是一个向量经过AA的变化后的向量与其本身的夹角小于/小于等于90度。

实数矩阵与其转置矩阵相乘为半正定矩阵,如果可逆,则为正定矩阵。

一些明显的凸函数:

  1. 指数函数是凸函数;
  2. 对数函数是凹函数,然后负对数函数就是凸函数;
  3. 对于一个凸函数进行仿射变换,可以理解为线性变换,结果还是凸函数;
  4. 二次函数是凸函数(二次项系数为正);
  5. 高斯分布函数是凹函数;
  6. 多个凸函数的线性加权,如果权值是大于等于零的,那么整个加权结果函数是凸函数。
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道