深入理解拉格朗日乘子法和KKT条件

拉格朗日乘子法(Lagrange Multiplier) 和KKT条件是求取有约束条件的优化问题的非常常用而且重要的方法。之前学习的时候,只是直接应用两个方法,没有深入理解为什么要这样去求取最优值?在查找一些资料后,理解整理如下。

什么是拉格朗日乘子法和KKT条件

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

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

​ min f(x);

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

​ min f(x),

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

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

​ min f(x),

​ s.t. gi(x) <= 0; i =1, ..., n

​ hj(x) = 0; j =1, ..., m

对于第(i)类的优化问题,常常使用的方法就是Fermat定理,即使用求取f(x)的导数,然后令其为零,可以求得候选最优值,再在这些候选值中验证;如果是凸函数,可以保证是最优解。

对于第(ii)类的优化问题,常常使用的方法就是拉格朗日乘子法,即把等式约束hi(x)用一个系数与f(x)写为一个式子L(a, x) = f(x) + a*h(x),称为拉格朗日函数,系数a称为拉格朗日乘子。通过拉格朗日函数对各个变量求导,令其为零,可以求得候选值集合,然后验证求得最优值。

对于第(iii)类的优化问题,常常使用的方法就是KKT条件。同样地,把所有的等式、不等式约束与f(x)写为一个式子L(a, b, x)= f(x) + ag(x)+bh(x),也叫拉格朗日函数,系数也称拉格朗日乘子。所谓KKT条件就是说优化问题求取的最优值必须满足以下条件:

  • L(a, b, x)对x求导为零;
  • h(x) =0;
  • a*g(x) = 0;

求取这三个等式之后能得到候选最优值。其中第三个式子非常有趣,因为g(x)<=0,如果要满足这个等式,必须a=0或者g(x)=0. 这是SVM的很多重要性质的来源,如支持向量的概念。

为什么拉格朗日乘子法 和KKT条件能够得到最优值?

以维基百科给出的拉格朗日乘子法为例,假设目标函数z = f(x,y), z取不同的值,则目标函数投影在xOy平面(曲面)上,即成为等高线,如下图,虚线是等高线。假设约束g(x,y)=0,在xOy平面或者曲面上是一条曲线,假设g(x,y)与等高线相交,交点就是同时满足等式约束条件和目标函数的可行域的值,但肯定不是最优值,因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部,使得新的等高线与目标函数的交点的值更大或者更小,只有到等高线与目标函数的曲线相切的时候,可能取得最优值,即等高线和目标函数的曲线在该点的法向量必须在一条直线上,所以最优值必须满足:f(x,y)的梯度 = a* g(x,y)的梯度,a是常数,表示左右两边共线。这个等式就是L(a,x)对参数求导的结果。

001.jpg

假设现在有不等式约束g ( x , y ) − c ≤ 0,五角星区域是我们满足不等式约束的区域。此时我们仍然用拉格朗日乘法将对不等式约束引入拉格朗日乘法。习惯上对等式约束使用β 乘子,对不等式约束使用α 乘子 L ( x , y , λ ) = f ( x , y ) + λ ⋅ ( g ( x , y ) − c ) 。
我们仍然按照三步求导的战略,仍旧可以得到:

  • f ′ ( x ) = λ g ′ ( x )
  • f ′ ( y ) = λ g ′ ( y ) g ( x , y ) − c = 0
  • g(x,y)−c=0
002.png

但是这和等式约束有什么区别在于要想最小值点落在约束不等式所在的曲线上,那么原函数的梯度和约束曲线的梯度一定要是反方向的。
也就是

  • f ′ ( x ) + λ g ′ ( x ) = 0
  • f ′ ( y ) + λ g ′ ( y ) = 0
  • s . t . λ ≥ 0

也就是说如果最优解落在约束曲线上,除了原函数在该点的法向量能被约束曲线线性表出外,原函数的法向量的符号还得和约束曲线们的法向量符号相反,即切点约束条件区域扩大的方向与原函数增大的方向相同。

这就引出KKT条件之大部分(除了条件d):
∇ x L ( x ∗ , α ∗ , β ∗ ) = 0 ( a )

∇ α L ( x ∗ , α ∗ , β ∗ ) = 0 ( b )

∇ β L ( x ∗ , α ∗ , β ∗ ) = 0 ( c )

α i ∗ c i ( x ∗ ) = 0 , i = 1 , 2 , ⋯ k ( d )

c i ( x ∗ ) ≤ 0 , i = 1 , 2 , ⋯ k ( e )

α i ∗ ≥ 0 , i = 1 , 2 , ⋯k ( f )

h j ( x ∗ ) = 0 , j = 1 , 2 , ⋯ l ( g )

  • 条件(a)为原函数在切点的法向量被约束曲线在该点的法向量线性表出
  • (b)(c) 表示最优解落在约束条件所在的曲线上
  • (e)为约束条件的表达形式,都是小于等于的形式
  • (f)使得原函数的法向量与约束曲线的法向量在切点处异号
  • (g)为等式约束的形式

而对于多个不等式约束:

003

由上图可知,g3函数在约束时没有起任何作用,但是在上面的KKT条件中g3和其对应λ 的系数都参与了运算,如何消除其作用呢,这就引出了KKT的最后一个条件d:
α i ∗ c i ( x ∗ ) = 0 , i = 1 , 2 , ⋯ k ( d )
最优解在约束曲线上时,其表达式为0,若不在某条约束曲线上,为了使最后的结果为0,其系数必须为0,从而使不产生作用的曲线在计算时不产生作用。该条件也称为KKT的对偶互补条件。
到此为止我们推出了KKT的所有条件。

拉格朗日对偶性

原始问题,求在等式和不等式约束条件下的函数最小值:

004

为了求解原始问题,我们首先引入广义拉格朗日函数(generalized Lagrange function):

005.png

其中:

  • f ( x )是可微的
  • α i , β j 成为拉格朗日乘子且α i ≥ 0
  • c i ( x ) ≤ 0
  • h i = 0

通过拉格朗日乘法,把约束条件加上新的变量构成了一个新的函数,虽然新的函数中变量变多了,但是没有了限制条件。
考虑x的函数(下标P表示原始问题):

007

这个max的意义在于,我们将所有的x样本根据取值的不同分成了满足条件和不满足条件的两部分,用函数的取值代替了原来的约束条件

现在这个θ*P*(x) 取最大,只要根据x的取值情况来调整其系数α β 即可。x的取值情况有两种:

  • 满足原始问题的约束,这种情况下c i ( x ) ≤ 0 ,h j ( x ) = 0 ,并且α i ≥ 0 ,那我们只要让c i 的拉格朗日系数α为0,就能得到最大的结果f*(x)

  • 不满足原始问题的约束,这种情况下要么 c i ( x ) > 0 或者h j ( x ) ≠ 0,那我们就能通过改变α β 使得 θ**P*(x)取到正无穷。

    所以我们就有如下的式子:
    008

再考虑极小化问题:

009

这个问题的解和原问题是等价的,即它和原始问题(带有约束条件的f(x)最小化问题)有着相同的解。因为对 θ P*(x)取最小值,就是对f*(*x)取最小值。

如果我们定义原始问题的最优解为p ∗ ,那么我们也有
p∗=xmin θ**P(x)
到这里,我们就将原来带有约束条件的极小化问题,变成了不带约束条件的极小极大问题。到这一步我们还是无法求解,所以我们引入对偶问题,将极小极大问题转化为极大极小问题。

对偶问题

定义:
010.png

之前我们是先求极大值,再求极小值,先求极大值的好处是可以根据结果将数据分为满足条件和不满足条件的两部分,然后再对结果求最小,即变成了对满足条件的x求最小值还原了原始问题。

现在我们反过来,先求极小值再求极大值,将该问题成为原始问题的对偶问题,定义对偶问题的最优值:

d∗=α,βmax θD*(α,*β)

原始问题先固定x,求最优化(极大化)的α β 的解,再确定x(通过极小化)
而对偶问题是先固定α ,β ,求最优化(极小化)的x的解,在确定α,β(通过极大化)

原始问题与对偶问题的关系

我将原始问题的最优解,转化为对偶问题的最优解,如果这两个解是等价的,那么解对偶问题最优解就是我们需要的原始问题的最优解。
若原始问题和对偶问题都有最优值,则:
zuiyou.png
证明:
对于任意的x , α , β 有:

zuiyouzhengming.png

因为上述式子是在任意条件下的x , α , β,最大最小是任意条件中的特殊情况,所以上述结论得证。

对偶问题的解小于等于原始问题的解 d ∗ ≤ p ∗ 。只有当等号成立的时候我们才能通过对偶问题来解决原始问题。对偶问题取等需要二者满足强对偶关系,而后有学者在强对偶下提出了KKT条件,且KKT条件的成立要满足constraint qualifications,而constraint qualifications之一就是Slater条件,即:凸优化问题,如果存在一个点x,使得所有等式约束都成立,并且所有不等式约束都严格成立(即取严格不等号,而非等号)。