深度学习笔记(二)

拉格朗日乘数法与KKT条件

Posted by Pelhans on April 11, 2019

眼睛看过只是别人的,整理出来并反复学习才是自己的。

概览

通常情况下,最优化问题会答题可分为三种情况:无约束条件、等式约束条件、不等式约束条件,对应的算法为费马定理、拉格朗日乘数法、KKT条件。

无约束条件

最简单的情况,根据费马定理,解决方法通常是函数对变量求导,零导数函数等于0的点可能是极值点。将结果待会原函数进行验证即可。

等式约束条件

设目标函数为$f(x)$,约束条件为$h_{k}(x)$,公式表示为:

对应的解决方法就是消元法或拉格朗日法。求解过程为:

首先定义拉格朗日函数 F(x):

然后解变量的偏导方程:

若有 l 个约束条件,n个变量,那么就会有 l+i 个方程。求出方程组的解为驻点,包含原函数的极值点。将结果带回原方程验证就可得到解。

那么为什么这么做就可以得到最优解呢?根据参考中知乎的回答可以进行理解。

我们可以画出F的等高线图,如上图。此时,约束h=c由于只有一个自由度,因此也是图中的一条曲线(红色曲线所示)。显然地,当约束曲线h=c与某一条等高线f=d1相切时,函数f取得极值。两曲线相切等价于两曲线在切点处拥有共线的法向量。因此可得函数f(x,y)与h(x,y)在切点处的梯度(gradient)成正比。于是我们便可以列出方程组求解切点的坐标(x,y),进而得到函数F的极值。

一道练习题

已知函数 $ f(x, y, z) = 8xyz$,约束条件为 $\frac{x^{2}}{a^{2}} + \frac{y^{2}}{b^{2}} + \frac{z^{2}}{c^{2}} = 1 $,求函数 $f(x)$的最大值。

解:首先对约束条件改写为右侧为0的形式:

在前面乘以拉格朗日乘子 $\lambda $与目标函数联合得:

对各变量及 $\lambda$求偏导有:

联立头三个方程有: $bx = ayaz = cx $$,带入第四个方程得到解:

带入第四个方程有 $f(x,y,z)$中得到最大体积为:

不等式约束

KKT条件可以看做拉格朗日乘数法的一种泛化。这里Karush-Kuhn-Tucker (KKT)条件说的很好。我尝试理解,并整理成自己记忆习惯的。

首先我们有带不等式约束的优化问题:

根据约束条件定义可行域 $K = x\in R^{n}|g(x) \leq 0 $。设最优解为$x^{}$。当$g(x^{}) < 0$时,最优解在K的内部,此时约束条件无效,也就是g(x)不起作用,问题就变成了无约束优化问题,即$\nabla f = 0$且 $\lambda = 0$。

当$g(x^{*})=0$,此时最优解落在K的边界,约束条件生效,$g(x)=0$,和拉格朗日乘数法相同。因此无论是内部解还是边界解,$\lambda g(x)=0 $都成立,成为互补松弛性。整合上述两种情况,最佳解的必要条件包括拉格朗日函数的定常方程式、原始可行性、对偶可行性以及互补松弛性:

这些条件合称 KKT条件。当最小化f(x)变成最大化时,$\lambda \leq 0$。

例子

参考

深入理解拉格朗日乘子法(Lagrange Multiplier) 和KKT条件
如何理解拉格朗日乘子法?
Karush-Kuhn-Tucker (KKT)条件