问题引入

max f(x, y)

s.t.

g(x,y) <= 0

几何解释

KKT条件原理-LMLPHP

a.  g(x ,y) <= 0为上图中z = 0平面中的圆,圆的边表示g(x, y) = 0,圆的内部表示g(x, y) < 0。

b.  z = f(x, y)为上图中的曲面。

上述极值问题就是要求当点(x, y)落在圆内时(包括圆的边),f(x, y)的最大值。

1、    如果极值点在圆内,则显然有

f'(x, y) = 0

g(x, y) < 0

2、    如果极值点在圆边上,有拉格朗日乘子法我们知道

f’(x, y) + λg’(x ,y) = 0

g(x, y) = 0

如果是数学考试,我们直接求出上面两种情况的所有解(x, y),再带入f(x, y)计算,选取最大值即可。

对偶问题

稍微修改一下文章开头的极值问题,得到新的极值问题1

min f(x, y)

s.t.

g(x,y) <= 0

拉格朗日函数如下

F(x, y, λ) = f(x, y) + λg(x, y)

我们对x, y求导数并令其为0,即

F’(x, y, λ) = f’(x, y) + λg’(x, y) = 0

场景1等价于

F’(x, y, λ) = 0

g(x, y) < 0

λ = 0

场景2等价于

F’(x, y, λ) = 0

g(x, y) = 0

λ > 0

场景二极小值点在圆边上,如果此时f(x, y)与g(x, y)梯度方向相同,说明点(x ,y)往圆内移动,f(x, y)的值会和g(x, y)的值一样减小,显然此时圆边上的点(x, y)不是极小值点。所以如果f(x, y)的极小值点在圆边上,必然f(x, y)与g(x, y)梯度方向相反,即λ > 0。

综合上述两种情况,极值问题1的对偶问题2如下(对偶问题解决了,原问题也就解决了)

max F(x, y, λ) = f(x, y) + λg(x, y)

s.t.

g(x, y) <= 0

λ >= 0

λg(x, y) = 0

点(x, y)在圆圈g(x, y) <= 0内,对于λ >= 0,我们有F(x, y, λ) <= f(x, y),于是F(x, y, λ)的上界就是f(x, y)的下界。

我们把

g(X) <= 0

λ >= 0

λg(X) = 0

称作KKT条件。X表示向量(x1; x2; …; xn)。

05-11 22:55