优化问题
凸优化
1.基本概念:
定义:函数L(⋅)是凸函数当且仅当对定义域中的任意两点x,y和任意实数λ∈[0,1]总有L(λx+(1−λ)y)⩽λL(x)+(1−λ)L(y)
直观解释:凸函数曲面上任意两点的连线而成的线段,其上的任意一点都不会处于该函数曲面的下方。
2.实例讲解:
对于二分类问题,Y={1,−1},假设模型参数为θ,则逻辑回归的优化问题为:
minθL(θ)=∑i=1nlog(1+exp(−yiθTxi))
可以通过计算目标函数的二阶Hessian矩阵来验证:
Li(θ)=log(1+exp(−yiθ⊤xi))
对该函数求一阶导,得到:
∇Li(θ)=1+exp(−yiθTxi)1exp(−yiθTxi)⋅(−yixi)=1+exp(yiθTxi)−yixi
继续求导,得到函数的Hessian矩阵:
∇2Li(θ)=(1+exp(yiθTxi))2yixi⋅exp(yiθTxi)⋅yixiT=(1+exp(yiθTxi))2exp(yiθTxi)xixiT
该矩阵满足半正定的性质∇2Li(θ)⪰0,因此∇2L(θ)=∑i=1n∇2Li(θ)≥0,函数L(⋅)为凸函数。对于凸优化问题,所有的局部极小值都是全局极小值。
主成分分析对应的优化问题是非凸优化问题。令X=[x1,…,xn]为数据中心后构成的矩阵,则主成分分析的优化问题为minVVT=IkL(V)=∥∥X−VTVX∥∥F2,通过凸函数的定义可以验证该优化问题的目标函数为非凸函数。令 V∗为优化问题的全局极小值,
则 $ -V^* $也是该问题的全局极小值,且有:
L(21V∗+21(−V∗))=L(0)=∥X∥F2>∥∥X−V∗TV∗X∥∥F2=21L(V∗)+21L(−V∗)
这不满足凸函数的定义,因此主成分分析的优化问题为非凸优化问题。
3.知识补充:
定义:设A是实对称矩阵。如果对任意的实非零列向量x有xTAx≥0,就称A为半正定矩阵。如果xTAx>0,则为正定矩阵。
几何解释:正定/半正定矩阵A指的是一个向量经过A的变化后的向量与其本身的夹角小于/小于等于90度。
实数矩阵与其转置矩阵相乘为半正定矩阵,如果可逆,则为正定矩阵。
一些明显的凸函数:
- 指数函数是凸函数;
- 对数函数是凹函数,然后负对数函数就是凸函数;
- 对于一个凸函数进行仿射变换,可以理解为线性变换,结果还是凸函数;
- 二次函数是凸函数(二次项系数为正);
- 高斯分布函数是凹函数;
- 多个凸函数的线性加权,如果权值是大于等于零的,那么整个加权结果函数是凸函数。