深入理解拉格朗日乘子法和KKT条件
背景介绍
在求取有约束条件的优化问题时，拉格朗日乘子法(Lagrange Multiplier)和KKT条件是非常重要的两个求取方法。
- 对于等式约束的优化问题，可以应用拉格朗日乘子法去求取最优值；
- 如果含有不等式约束，可以应用KKT条件去求取。
当然，这两个方法求得的结果只是必要条件，只有当是凸函数的情况下，才能保证是充分必要条件。KKT条件是拉格朗日乘子法的泛化。那么为什么拉格朗日乘子法（Lagrange Multiplier) 和KKT条件能够起作用，为什么要这样去求取最优值呢？
拉格朗日乘子法(Lagrange Multiplier)和KKT条件
最优化问题分解
- 无约束优化问题，可以写为:
\[minf(x)\] - 有等式约束的优化问题,可以写为: \[minf(x)\] \[s.t. h_i(x) = 0; i =1, …, n \]
- 有不等式约束的优化问题，可以写为： \[min f(x)\] \[s.t. g_i(x) \leq 0; i =1, …, n\] \[h_j(x) = 0; j =1, …, m\]
最优化问题求解
- 对于第1类的优化问题，常常使用的方法就是Fermat定理，即使用求取f(x)的导数，然后令其为零，可以求得候选最优值，再在这些候选值中验证；如果是凸函数，可以保证是最优解。
-
对于第2类的优化问题，常常使用的方法就是拉格朗日乘子法(Lagrange Multiplier)，即把等式约束$h_i(x)$用一个系数与$f(x)$写为一个式子，称为拉格朗日函数，而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导，令其为零，可以求得候选值集合，然后验证求得最优值。
即对于等式约束，我们可以通过一个拉格朗日系数$\lambda$把等式约束和目标函数组合成为一个式子: \[L(\lambda, x) = f(x) + \lambda h(x)\] 这里把$\lambda$和$h(x)$视为向量形式，$\lambda$是横向量，$h(x)$为列向量 然后求取最优值，可以通过对$L(\lambda,x)$对各个参数求导取零，联立等式进行求取。
-
对于第3类的优化问题，常常使用的方法就是KKT条件。同样地，我们把所有的等式、不等式约束与$f(x)$写为一个式子，也叫拉格朗日函数，系数也称拉格朗日乘子，通过一些条件，可以求出最优值的必要条件，这个条件称为KKT条件。
同样地，把所有的不等式约束、等式约束和目标函数全部写为一个式子: \[L(\lambda, \mu, x)= f(x)+\lambda g(x)+\mu h(x)\] KKT条件是说最优值必须满足以下条件：
- $L(\lambda, \mu, x)$对$x$求导为零
- $h(x) =0$
- $\lambda g(x) = 0, \lambda \geq 0$
求取这三个等式之后就能得到候选最优值。其中第三个式子非常有趣，因为$g (x)\leq 0$，如果要满足这个等式，必须$\lambda=0$或者$g(x)=0$。
以后进一步更新为什么拉格朗日乘子法(Lagrange Multiplier)和KKT条件有效
