库恩塔克定理
6-1 最优性条件
现考虑一般形式的非线性规划数学模型:
min f (X ), X ∈E
n
h i (X ) =0, (i =1, 2, , m ) g
j
(X ) ≥0, (j =1, 2, , l )
假设f (X ) 、h (X ) 和g
i
j
(X )
均具有一阶连续偏导
数,X 是非线性规划的一个可行解。现考虑某一
(0)
不等式约束g 能:(1)g
j
j
(X ) ≥0
,X 满足该不等式有两种可
(0)
(0)
(0)
(X
(0)
) >0
,此时X 不在由该约束形成的
可行域边界上,因此该约束对X 的微小变动不起限制作用,从而称该约束为无效约束;(2)
g j (X
(0)
) =0
,此时X 处在由该约束形成的可行域边
(0)
(0)
界上,因此该约束对X 的微小变动会起某种限制作用,从而称该约束为有效约束。显而易见,所有等式约束都是有效约束。
X
(0)
是非线性规划的一个可行解,对于此点的
(0)
某一方向D ,若存在实数 λ0>0使任意 λ∈[0, λ0]均有X
(0)
+
λD ∈R ,就称方向D 是X 点的一个可行方
(0)
向,此处R 代表非线性规划的可行域。
若D 是X 点的任一可行方向,则对该点所有有效约束g
j
(X ) ≥0
均有:
∇g j (X
(0)
) D ≥0
T
,
j ∈J
(6-18)
其中J 代表在X 点所有有效约束下标的集合,如
(0)
图6-14所示。
另一方面,由泰勒展开式
λ∇g (X ) D +0(λ)
可知对所有有效约束,当λ>0足够小时,只要
g j (X
(0)
+
λD ) =g
j
(X
(0)
) +
(0) T
j
∇g j (X
(0)
) D >0
T
,
j ∈J
(6-19) 就有
g j (X
(0)
(0)
+
λD ) ≥0,j ∈J
此外,对X 点所有的无效约束来讲,由于约束函数的连续性,当λ>0足够小时,上式依然成立。从而,只要方向D 满足式(6-19),即可保证
D
是X 点的可行方向。
(0)
非线性规划的某一可行点X ,对该点的任一
(0)
方向来说,若存在实数λ0>0使任意λ∈[0, λ0]均有
f (X
(0)
+
λD )
f (X
(0)
)
,就称方向D 是X 点的一个下降方
(0)
(0)
向。
将目标函数f (X ) 在X 处作一阶泰勒展开,若方向D 满足
∇f (X
(0)
) D
T
(6-20)
则D 必是X 点的一个下降方向。
(0)
如果方向D 既是X 点的一个可行方向又是
(0)
一个下降方向,就称D 是X 点的一个可行下降方
(0)
向。显然,如果某点存在可行下降方向,那么该点就不会是极小点;另一方面,如果某点是极小点,则该点不存在可行下降方向。
[定理3] 设X 是非线性规划的一个局部极小
*
点,目标函数f (X ) 在X 处可微,而且
*
g j (X )
在X 处可微,当j ∈J 时
*
g j (X )
在X 处连续,当j ∉J 时
*
*
(此处J 代表在X 处有效约束的下标集合)则在
X
*
点不存在可行下降方向,从而不存在向量D 同
∇f (X ) D
*
T
时满足
,
j ∈J
-(6-21)
*
∇g j (X ) D
*T
事实上,若在X 点存在向量D 满足式(6-21),则从X 点出发沿方向D 搜索可找到比X 点更好的
*
*
点,这与X 点是一个局部极小点的假设相矛盾;
*
所以这个定理是显然成立的。
式(6-21)的几何意义是十分明显的,即X 点
*
处满足该条件的方向D 与X 点目标函数负梯度方
*
向的夹角为锐角,与X 点所有有效约束梯度方向
*
的夹角也为锐角。
假设X 是非线性规划的极小点,该点可能处
*
于可行域的内部,也可能处于可行域的边缘上。若为前者,该规划问题实质是一个无约束极值问题,X 必满足∇f (X
*
*
) =0
;若为后者,情况就复杂多
*
了,接下来我们就对这一复杂情况进行分析。
不失一般性,设X 位于第一个约束所形成的可行域的边缘上,即第一个约束是X
点处的有效
*
约束,g (X
1
*
*
) =0
。若X 是极小点,则∇g (X ) 必与-∇f (X
*
*
1
*
1
*
)
在同一直线上,且方向相反(这里假定∇g (X ) 和
f (X )
皆不为“0”);否则,在X 点处就一定存在可
*
*
行下降方向,如图6-15所示。图6-15中的X 点是满足上述条件的极小点,角度 β 表示非极小点X 处的可行下降方向的范围。既然∇g (X ) 与
*
1
*
-∇f (X )
在同一直线上,且方向相反,则必存在一
1
个实数γ
*
>0
*
,使∇f (X
(X ) =0
**
*
) -γ1∇g 1(X ) =0
*
。
*
若X 点处在两个有效约束边缘上,比如说
g 1(X ) =0∇g 1(X )
*
和g
2
2
。在这种情况下,∇f (X ) 必处于
*
*
和∇g
(X )
的夹角之内;如若不然,X 点必存
在可行下降方向,这与X 是极小点的相矛盾,如图6-16所示。
由此可见,如果X 是极小点,而且X 点的有
*
*
效约束的梯度∇g (X ) 和∇g
*
1
2
(X )
*
线性独立,则可以将
∇f (X )
*
表示成为∇g (X ) 和∇g
*
1
2
(X )
*
的非负线性组合;也,使: ∇g (X ) =0
*
2
就是说,存在实数γ
*
1
>0
和γ
*
2
>0
2
∇f (X ) -γ1∇g 1(X ) -γ
如此类推,可以得到:
∇f (X ) -
*
∑γ
j ∈J
j
∇g j (X ) =0
*
(6-22)
为使所有无效约束也同上述有效约束一样包含在式(6-22)中,增加约束条件{γ当g
j
j
g j (X ) =0; γ
*
j
≥0}
,
(X ) =0
*
时γ
j
>0
;当g
j
(X ) ≠0
*
时γ
j
=0
。如此即可得
到式(6-23)所示的库恩-塔克条件(Kuhn-Tucker ,简称K-T 条件,满足这一条件的点称为K-T 点)。设X 是非线性规划{min
*
*
f (X ), g j (X ) ≥0, j =1, 2, , n }
的极小
点,而且X 点各有效约束的梯度线性独立,则存在向量Γ
*
=(γ1, γ2, , γn )
***
,使下述条件成立:
n
*
∇f (X ) -
∑γ
j =1
*
j
∇g j (X ) =0
*
j =1, 2, , n
γj g j (X ) =0
**
,
(6-23
γ
*j
≥0
,j =1, 2, , n
*
由于等式约束总是有效约束,所以一般形式的非线性规划的库恩-塔克条件可表达为:设X 是非线性规划
{minf (X ); h i (X ) =0, i =1, 2, , m ; g j (X ) ≥0, j =1, 2, , n }
的极小点,而且X 点的所有有效约束的梯度
*
∇h i (X ) (i =1, 2, , m )
*
和∇g
*
j
(X ) (j ∈J )
*
*
*
线性独立,则存在向量
n
λ=(λ1, λ2, , λm )
****
和Γ
=(γ1, γ2, , γn )
m
*
,使下述条件成立:
*i
∇f (X ) -
*
∑λ
i =1
∇h i (X ) -
*
∑γ
j =1
*j
∇g j (X ) =0
*
γj g j (X ) =0
**
,
j =1, 2, , n
(6-24
γ
*j
≥0
*i
,j =1, 2, , n
*j
式(6-24)中的λ和γ称为广义拉格朗日乘子(Lagrange Multipliers)。
库恩-塔克条件是非线性规划领域中最重要的理论成果之一,是确定某点为极值点的必要条件;但一般来讲它并不是充分条件,因此满足这一条件的点并非一定就是极值点。对于凸规划,库恩-塔克条件是极值点存在的充分必要条件。