只记录机器学习方法中需要用到的最优化知识,不做系统总结,持续更新ing。
1 凸优化
1、凸集
一个点集或者区域,如果连接任何两点X1.X2之间的线段可以全部被包含在该集合里面,就称该点集为凸集,否则为非凸集。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608140408673.png#pic_center)
2、凸性条件
-
1 根据一阶导数(函数的梯度)来判断凸性
设f(x)为定义在凸集R上,且具有连续的一阶导数的函数,则f(x)在R上为凸函数的充要条件是对凸集R内任意不同两点x1,x2,有不等式恒成立:
![在这里插入图片描述](https://img-blog.csdnimg.cn/2021060814063240.png#pic_center)
-
2 根据二阶导数(Hesse矩阵)来判断凸性
设f(x)为定义在凸集R上且具有连续二阶导数的函数,则f(x)在R上为凸函数的充要条件:
Hesse矩阵在R上处处半正定
3、凸规划
对于约束问题:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608140758740.png#pic_center)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608140817477.png#pic_center)
4、凸规划性质
- 若给定一点x0,则集合R={x|f(x)<=f(x0)}为凸集
- 可行域R={x|g(x)<=0,j=1,2…}为凸集
- 凸规划的任何局部最优解就是全局最优解
5、凸优化问题
凸优化问题是指约束最优化问题:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608141241377.png#pic_center)
其中,目标函数f(w) 和约束函数gi(w)都是Rn上连续可微的凸函数,约束函数hj(w)是Rn上的仿射函数。当目标函数为二次函数,g函数为仿射函数时,为凸二次规划问题。
2 拉格朗日函数及其对偶问题
1、拉格朗日函数(含KKT条件)
最优化问题根据约束条件分为三类(无约束、等式约束、不等式约束)
1)对于"无约束"优化问题:
比较简单,令偏导数=0,联立方程组得到的点就可能是极值点(只是必要条件),在具体带入函数判断即可。对于有约束问题都是通过构造拉格朗日函数来进行求解。
2)对于等式约束问题:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608152650837.png#pic_center)
构造拉格朗日函数:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608152853722.png#pic_center)
其中,每个约束条件都对应着一个拉格朗日乘子。
拉格朗日函数对x求偏导即得到:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608152922843.png#pic_center)
3)对于“等式约束”+“不等式约束”优化问题
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608153921978.png#pic_center)
最终要转换为无约束的简单问题,分为两步:
- 1.把不等式约束转换为等式约束:引入松弛变量(KKT算子)
- 2.把等式约束转换为无约束的优化条件:引入拉格朗日乘子
构造出拉格朗日函数为:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608154257285.png#pic_center)
其中,阿尔法和贝塔就是引入的KKT算子和拉格朗日乘子。
接下来就是对无约束优化问题求偏导来找极值点,即得到KKT条件(必要条件)
KKT条件:
KKT条件详解
2、拉格朗日对偶问题
已知构造的拉格朗日函数为:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608154257285.png#pic_center)
显然其中:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608155907664.png#pic_center)
考虑极小问题:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608160005947.png#pic_center)
这就是原问题的拉格朗日函数极小极大问题。
引入KKT乘子和拉格朗日算子当作参数,关于x取最小值为:
![在这里插入图片描述](https://img-blog.csdnimg.cn/2021060816030890.png#pic_center)
则有:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608160537521.png#pic_center)
这就是拉格朗日函数的极大极小问题,也是原问题的对偶问题。显然可以推导出:对偶问题的最优解是原问题的一个下界。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608161052117.png#pic_center)
- 当满足KKT条件时,原始问题和对偶问题的可行解X星和a,b是两个问题的解,通过列出KKT条件的方程,即可得到原始问题的解。
- 当:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210608161313503.png#pic_center)
原始问题和对偶问题的可行解X星和a,b是两个问题的最优解。
- 强对偶和弱对偶