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