拉格朗日乘子法 机器学习基础|深入理解拉格朗日乘子法

拉格朗日乘数法无疑是最优化理论中最重要的方法。但是网上没有一篇文章全面介绍了整个方法。为此，边肖整理了以下文章，希望能赢得大家的好评。

拉格朗日乘子法和KKT条件是求解带约束优化问题的两种非常重要的方法。对于等式约束的优化问题，可以使用拉格朗日乘子法来寻找最优值。如果存在不等式约束，可以应用KKT条件来求解。当然，这两种方法得到的结果只是必要条件，只有当它们是凸函数时，才能保证它们是充分必要条件。

KKT条件是拉格朗日乘数法的推广。以前学习的时候只知道直接应用两种方法，不知道拉格朗日乘数和KKT条件为什么能起作用，为什么要用这种方式得到最优值？

本文首先介绍了什么是拉格朗日乘数和KKT条件。然后我们开始讲为什么要用这种方式去寻找最优值。

1.拉格朗日乘数和KKT条件

一般我们需要解决的优化问题如下:

(一)无约束优化问题，可以写成:

最小f(x)；

(ii)等式约束的优化问题可以写成:

最小f(x)，

s . t . h _ I(x)= 0；i =1，...，n

(iii)具有不等式约束的优化问题可以写成:

最小f(x)，

s.t. g_i(x) <。= 0;i =1，...，n

h _ j(x)= 0；j =1。...，m

费马定理常用于类(I)的优化问题，即通过计算f(x)的导数，然后使其为零，可以得到候选最优值，并在这些候选值中进行验证；如果是凸函数，可以保证是最优解。

对于(ii)优化问题，常用的方法是拉格朗日乘子，即把方程约束h_i(x)写成一个带系数和f(x)的公式，称为拉格朗日函数，系数称为拉格朗日乘子。通过拉格朗日函数取各变量的导数并使之为零，就可以得到候选值集，然后通过验证就可以得到最优值。

KKT条件常用于(ⅲ)优化问题。同样，我们把所有的等式、不等式约束和f(x)写成公式，也叫拉格朗日函数，系数也叫拉格朗日乘数。通过一些条件，我们可以找到最优值的必要条件，这就是所谓的KKT条件。

拉格朗日乘数法(拉格朗日乘数)

关于等式约束，我们可以通过一个拉格朗日系数a把等式约束和目标函数结合成一个公式L(a，x) = f(x)+a*h(x)，这里把a和h(x)看作向量形式，a是横量，h(x)是列向量。写这个的原因是csdn很难写数学公式，所以只能将就了。

然后得到最优值，取L(a，x)的导数，每个参数取0，联立方程即可得到。这是高等数学里讲过的，但是不讲为什么这样做也是可以的。后面简单介绍一下思路。

(b) KKT条件

对于不等式约束的优化问题，如何得到最优值？常用的方法是KKT条件。同样，所有不等式约束、等式约束和目标函数都写成公式L(a，b，x)= f(x)+a*g(x)+b*h(x)。KKT条件意味着最优值必须满足以下条件:

1.l (a，b，x)对x的导数为零；

2.h(x)= 0；

3.a * g(x)= 0；

求解这三个方程后，就可以得到候选最优值。第三个方程非常有趣，因为g (x)

2.拉格朗日乘数和KKT条件为什么能得到最优值？

为什么要得到最好的价值？先说拉格朗日乘数法。设想我们的目标函数z = f(x)，x)，其中x是向量，z取不同的值，相当于投影到x组成的平面(曲面)上，也就是变成一条轮廓线。如下图，目标函数为f(x，y)，其中x为标量，虚线为等高线。

现在我们假设我们的约束g(x)=0，x是一个向量，是x形成的平面或曲面上的一条曲线，我们假设g(x)与等高线相交，交点是一个同时满足等式约束和目标函数的值，但肯定不是最优值，因为相交意味着这条等高线内或外一定有其他等高线，这使得新等高线与目标函数的交点变大或变小。只有当轮廓线与目标函数的曲线相切时，才有可能得到最优值，如下图所示，即轮廓线的法向量与目标函数的曲线在该点必须有相同的方向。

所以最优值必须满足:f(x)的梯度= a * g(x)的梯度，a为常数，表示左右两边同向。这个方程是L(a，x)对参数求导的结果。(不知道以上描述是否清楚。如果离我的物理位置近，直接来找我。我会当面解释，更好理解。注意:下图来自wiki。).

KKT条件是满足强对偶条件的最优化问题的必要条件，可以理解为:我们要求min f (x)，l (a，b，x) = f (x)+a * g (x)+b * h (x)，a >；=0，我们可以把f(x)写成max_{a，b} L(a，b，x)。

为什么？G (x)

如果用对偶表达式:max_{a，b} min_x L(a，b，x)，由于我们的优化满足强对偶(强对偶是指对偶公式的最优值等于原问题的最优值)，所以在得到最优值x0的条件下满足f (x0) = max _ {a，b} min_x L

f(x0) = max_{a，b} min_x L(a，b，x) = max_{a，b } min _ x f(x)+a * g(x)+b * h(x)= max _ { a，b} f(x0)+a*g(x0)+b*h(x0) = f(x0)

可以看出，上述黑化的地方本质上是指min_x f(x)+a*g(x)+b*h(x)在x0处得到最小值。利用费马定理，也就是说对于函数f(x)+a*g(x)+b*h(x)，导数必须等于零，即f(x)。

这是kkt条件中的第一个条件:L(a，b，x)对x的导数为零。

前面解释过，a*g(x) = 0，那么kkt条件的第三个条件，当然是已知条件h(x)=0必须满足。以上所有解释表明，满足强对偶条件的优化问题的最优值必须满足KKT条件，即上述三个条件。KKT条件可以看作是拉格朗日乘数法的推广。

声明:本文转载于网络，版权归原作者所有。如果涉及到作品的版权问题，请联系我们，我们会根据您提供的版权证明确认版权并支付报酬或删除内容。