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