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