KKT条件(精品文档).pdf

深入理解拉格朗日乘子法（LagrangeMultiplier)和KKT条

在求取有约束条件的优化问题时，拉格朗日乘子法（LagrangeMultiplier)和KKT条件是非常重要的两

求取方法，对于等式约束的优化问题，可以应用拉格朗日乘子法去求取最优值；如果含有不等式约束，

可以应用KKT条件去求取。当然，这两个方法求得的结果只是必要条件，只有当是凸函数的情况下，才

能保证是充分必要条件。KKT条件是拉格朗日乘子法的泛化。之前学习的时候，只知道直接应用两个方

法，但是却不知道为什么拉格朗日乘子法（LagrangeMultiplier)和KKT条件能够起作用，为什么要这样

去求取最优值呢？

本文将首先把什么是拉格朗日乘子法（LagrangeMultiplier)和KKT条件叙述一下；然后开始分别谈谈为

什么要这样求最优值。

一.拉格朗日乘子法（LagrangeMultiplier)和KKT条件

通常我们需要求解的最优化问题有如下几类：

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

minf(x);

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

minf(x),

s.t.h_i(x)=0;i=1,...,n

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

minf(x),

s.t.g_i(x)=0;i=1,...,n

h_j(x)=0;j=1,...,m

对于第(i)类的优化问题，常常使用的方法就是Fermat定理，即使用求取f(x)的导数，然后令其为零，可

以求得候选最优值，再在这些候选值中验证；如果是凸函数，可以保证是最优解。

对于第(ii)类的优化问题，常常使用的方法就是拉格朗日乘子法（LagrangeMultiplier)，即把等式约束

h_i(x)用一个系数与f(x)写为一个式子，称为拉格朗日函数，而系数称为拉格朗日乘子。通过拉格朗日函

数对各个变量求导，令其为零，可以求得候选值集合，然后验证求得最优值。

对于第(iii)类的优化问题，常常使用的方法就是KKT条件。同样地，我们把所有的等式、不等式约束与

f(x)写为一个式子，也叫拉格朗日函数，系数也称拉格朗日乘子，通过一些条件，可以求出最优值的必要

条件，这个条件称为KKT条件。

(a)拉格朗日乘子法（LagrangeMultiplier)

对于等式约束，我们可以通过一个拉格朗日系数a把等式约束和目标函数组合成为一个式子L(a,x)=f(x)

+a*h(x),这里把a和h(x)视为向量形式，a是横向量，h(x)为列向量，之所以这么写，完全是因为csdn

很难写数学公式，只能将就了。

然后求取最优值，可以通过对L(a,x)对各个参数求导取零，联立等式进行求取，这个在高等数学里面有讲，

但是没有讲为什么这么做就可以，在后面，将简要介绍其思想。

(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)=0，如果要满足这个等

式，必须a=0或者g(x)=0.这是SVM的很多重要性质的来源，如支持向量的概念。

二.为什么拉格朗日乘子法（LagrangeMultiplier)和KKT条件能够得到最优值？

为什么要这么求能得到最优值？先说拉格朗日乘子法，设想我们的目标函数z=f(x),x是向量,z取不同

的值，相当于可以投影在x构成的平面（曲面）上，即成为等高线，如下图，目标函数是f(x,y)，这里x

是标量，虚线是等高线，现在假设我们的约束g(x)=0，x是向量，在x构成的平面或者曲面