拉格朗日乘子法（Lagrange Multiplier）与 KKT 条件

Question

在求取有约束条件的优化问题时，拉格朗日乘子法（Lagrange Multiplier) 和 KKT 条件是非常重要的两个求取方法，对于等式约束的优化问题，可以应用拉格朗日乘子法去求取最优值；如果含有不等式约束，可以应用 KKT 条件去求取。

当然，这两个方法求得的结果只是必要条件，只有当是凸函数的情况下，才能保证是充分必要条件。KKT 条件是拉格朗日乘子法的泛化。

拉格朗日乘子法（Lagrange Multiplier) 和 KKT 条件

(i) 无约束优化问题，可以写为:

min f(x);  

如果是凸函数那么可以另导数为零求出最值

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

min L(a, x) = f(x) + a*h(x),

拉格朗日乘子法（Lagrange Multiplier) ，即把等式约束 h(x) 用一个系数与 f(x) 写为一个式子，称为拉格朗日函数，而系数 a 称为拉格朗日乘子。通过拉格朗日函数对各个变量求偏导，令其为零，可以求得候选值集合，然后验证求得最优值

具体求法如下

对 L(a, x) 求偏导

∂L/∂x=0
∂L/∂a=0

求出 a, x 的值，代入即可得到目标函数的极值

(iii) 有不等式约束的优化问题，可以写为：

min L(a, b, x)= f(x) + a*g(x)+b*h(x)

把所有的等式、不等式约束与 f(x) 写为一个式子，也叫拉格朗日函数，系数也称拉格朗日乘子，通过一些条件，可以求出最优值的必要条件，这个条件称为 KKT 条件。

等式约束的拉格朗日乘子法

目标函数 z = f(x) ， x 是向量, z 取不同的值，相当于可以投影在 x 构成的平面（曲面）上，即成为等高线，如下图，目标函数是 f(x, y) ，这里 x 是标量，虚线是等高线，现在假设我们的约束 g(x)=0 ， x 是向量，在 x 构成的平面或者曲面上是一条曲线，假设 g(x) 与等高线相交，交点就是同时满足等式约束条件和目标函数的可行域的值，但肯定不是最优值，因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小，只有到等高线与目标函数的曲线相切的时候，可能取得最优值。

含有不等约束的情况

和之前的不同之处在于：约束决定的可行区域由一条直线变成了一段带状区域。这个带状区域由两条边界 g(x, y) = c 和 g (x, y) = d 来决定