优化问题

凸优化

1.基本概念：

定义：函数是凸函数当且仅当对定义域中的任意两点x,y和任意实数总有

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

image.png

2.实例讲解：

对于二分类问题，,假设模型参数为，则逻辑回归的优化问题为：

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

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

继续求导，得到函数的Hessian矩阵：

该矩阵满足半正定的性质，因此，函数为凸函数。对于凸优化问题，所有的局部极小值都是全局极小值。

主成分分析对应的优化问题是非凸优化问题。令为数据中心后构成的矩阵，则主成分分析的优化问题为，通过凸函数的定义可以验证该优化问题的目标函数为非凸函数。令为优化问题的全局极小值，则也是该问题的全局极小值，且有：

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

3.知识补充：

定义：设是实对称矩阵。如果对任意的实非零列向量有，就称A为半正定矩阵。如果,则为正定矩阵。
几何解释：正定/半正定矩阵指的是一个向量经过的变化后的向量与其本身的夹角小于/小于等于90度。

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

一些明显的凸函数：

1. 指数函数是凸函数；
2. 对数函数是凹函数，然后负对数函数就是凸函数；
3. 对于一个凸函数进行仿射变换，可以理解为线性变换，结果还是凸函数；
4. 二次函数是凸函数（二次项系数为正）；
5. 高斯分布函数是凹函数；
6. 多个凸函数的线性加权，如果权值是大于等于零的，那么整个加权结果函数是凸函数。