0.无约束优化问题
问题形式:
对一个无约束问题,
一阶必要条件,
在 处取得0梯度: 二阶必要条件,在该点处黑塞矩阵(Hessian)半正定:
, 是任意的非零向量。 是向量 关于黑塞矩阵 的二次型。不等式
表示二次型是半正定的,也就是说,对于任何非零向量 ,二次型的值都大于等于零。
Hessian矩阵的正定性在判断优化算法可行性时非常有用,简单地说,黑塞矩阵正定,则
- 函数的二阶偏导数恒 > 0
- 函数的变化率(斜率)即一阶导数始终处于递增状态
- 函数为凸
1.等式约束问题
问题形式:
举例:
1.1 感性角度
上述问题可视化如下:
图中左上角的橙色点处,往哪里走达到约束下的最小值?
假设是无约束优化问题,我们知道直接往目标函数负梯度方向走,就可以到达最小
但是现在有一个等式的约束,只能在约束(实际上就是图中的橙色圆)上移动,在圆上移动只能沿着切线方向移动,只要保证每次移动都满足移动方向和目标函数负梯度方向夹角小于90°,就是在向极小值移动!
当移动到图中左下的蓝色点位置时,此刻无论向圆的哪个切线方向移动,夹角都为90°,不满足移动方向和目标函数负梯度方向夹角小于90°了,此时就认为达到了极小值。观察到此时目标函数的负梯度方向与约束函数的梯度方向满足线性关系(在一条线上),即:
1.2 拉格朗日乘子法
我们从一种感性的认知上找到了等式约束下的极小值,现在回到拉格朗日乘子法:
定义拉格朗日函数:
第一条:
是拉格朗日函数对 求梯度, 求梯度的结果是
则原式为
稍微移动变形
;注意 是未知数正负其实无所谓 此时,再看感性认知部分最后的目标函数的负梯度方向与约束函数的梯度方向满足线性关系(在一条线上) 是一致的,这里保证所求一定是一个极值
第二条:
是拉格朗日函数对 求梯度, 求梯度结果
则原式为
就是约束条件,这里保证了所求一定是满足约束条件的
第三条: 保证满足半正定,确定存在一个极小值
注意:如果是一个凸优化问题,满足(1)&(2)就可以找到极小值点(且为全局最小值点,充要条件);若非凸优化问题,仅满足(1)&(2)是必要条件,需要加上(3)才是充要条件
2.不等式约束问题
问题形式:
拉格朗日函数构造和上面一样
注意极值点只能出现在约束边界上
松约束,约束改变没起作用,加了和没加一样:
紧约束,约束起作用:
对于上面两种约束求解最小值的条件总结如下:
将两种形式整合在一起,就形成了KKT条件(单条不等式约束时):
多条不等式约束KKT条件:
3.混合约束问题
多条混合等式、不等式约束KKT条件:
4.总结
无约束问题:直接令梯度等于0求解
等式约束问题:构造拉格朗日函数,对各个分量求偏导,令各个分量偏导为0,即可解出极小值
不等式约束问题:构造拉格朗日函数,代入KKT条件求解
KKT条件求的是局部最值/极值。只要满足最后一条二阶条件无论凸问题、非凸问题,KKT条件都可以求得极值。
仔细想想KKT条件实际上就是教你怎么去利用拉格朗日方程求解最值。在等式约束时,拉格朗日函数对
5.参考资料
通俗易懂讲算法-最优化之拉格朗日乘子与KKT条件: https://www.bilibili.com/video/BV14q4y187wg
“拉格朗日对偶问题”如何直观理解?“KKT条件” “Slater条件” “凸优化”打包理解: https://www.bilibili.com/video/BV1HP4y1Y79e
瑞典皇家理工学院(KTH)“统计学习基础”课程的KKT课件: http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/KKT.pdf
拉格朗日乘子法和KKT条件: https://www.cnblogs.com/liaohuiqiang/p/7805954.html