如何理解拉格朗日乘子法和KKT条件?
之前简单介绍了拉格朗日乘子法的基本思路:如何理解拉格朗日乘子法?
本文会继续介绍拉格朗日乘子法的细节,以及对其进行适当的推广(也就是所谓的KKT条件)。
1 无约束下的极值
1.1 直观
根据梯度的意义(参看如何理解梯度)可知,在函数 的极值点梯度为0:
1.2 代数
要求( 的意思是求极小值):
只需解如下方程:
2 单等式约束下的极值
关于这一节,更详细的请参看:如何理解拉格朗日乘子法?
2.1 直观
要求方程 与原点的最小距离:
问题被转化为了同心圆与 什么时候相切:
相切就是在极小值点有相同的切线:
只要能通过数学把相切这个条件表示出来,就可以得到解。
我们把同心圆可以看作凸函数 的等高线:
把方程 看作凸函数
的等高线中的一条:
这样 的等高线,同心圆,的法线就是
:
的等高线的其中一条,方程
,的法线就是
两者相切就意味着,在切点,两者法线平行:
也就是:
2.2 代数
上面的问题形式化后,用代数表示为( 的意思是服从于,约束于的意思):
只需解如下方程组:
3 多等式约束下的极值
比如下图:
要求 被
约束后的极值,可以证明在极值点
必然在
张成的空间中。
那么上面的问题形式化后就是:
只需解如下方程组:
更一般的,如果有 个约束等式:
只需解如下方程组:
4 不等式约束下的极值
比如,我们要求刚才同心圆的最小值:
那肯定就是原点啦,半径为0肯定就是最小值了。
从代数上看就是要求:
解:
4.1 情况一
我们给它添加一个不等式约束,也就是求:
可以看到,这个不等式约束实际上包含了原点:
所以这个约束等于没有,依然求解:
4.2 情况二
换一个不等式约束:
不等式约束看起来是这样的:
因为同心圆是凸函数的等高线,所以等高线的值是这么排列的:
所以,在不等式约束下,最小值是在边缘相切的地方取得:
和用等式 进行约束效果是一样的:
因此可以通过解方程组求出答案:
4.3 新增的条件
仔细研究,不等式实际上带来了新的条件。
同心圆是凸函数的等高线,等高线的值如下排列,所以在相切处,法线也就是 的方向如下(法线也就是梯度,指向增长最快的方向,也就是等高线的值变大的方向):
而凸函数 的法线
也一样指向
增长的方向,这个方向正好和
相反:
因此:
其中, 就表明
方向相反。
因此刚才的方程组可以再增加一个条件:
5 KKT条件
因此,综合上面的所有情况,可以把求如下的极值:
通过解下面这个方程组来得到答案:
这个方程组也就是所谓的KKT条件。
进一步解释下方程组的各个项:
文章最新版本在(有可能会有后续更新):如何理解拉格朗日乘子法与KKT条件?