第 九 章 约束优化问题的最优性条件
从本章起， 将 用几章的内容来讨论约束最优化问题 .
我们考察 的 约束最优化问题 的一般形式为
12
m in ( )
( ) 0 , { 1 , 2 , , }s. t.
( ) 0 , { , , , }
ie
i e e
fx
c x i E m
c x i I m m m??
? ? ???
? ? ??
?
?
(9.0.1)
记 (( ) { 0 , }| )iI Ix i c xi? ??，我们称 ()E I x? 为 约束最优化问题 (9.0.1)在 xX? 处的
积极约束指标集 ， 积极约束 又称为 有效约束 、 起作用 的 约束或紧约束 (active constraints or
binding constraints).
如果有某种方式可以知道在最优解 x 处的积极约束指标集 ( )E I x? ，则 约束最优化
问题 (9.0.1)可以 转化为等式约束 最优化 问题
m i n ( )s .t . ( ) ( )0,
i
fxc x i IxE ??? (9.0.2)
一般地，这个问题较原问题 (9.0.1)要简单，但遗憾的是，我们无法预先 知道 ( )E I x? .
§9.1 一阶最优性条件
记
12{ | ( ) 0 , 1 , 2 , , ; ( ) 0 , , , , }n i e i e eD x c x i m c x i m m m??? ? ? ? ? ???? .
设 x D? ， nd?? 是 一个 非零向量 . 如果存在 0?? ， 对任意 [0, ]t ?? ，都有
x td D?? ，
则称 d 为点 x 处的 可行方向 ，点 x 处 的所有可行方向的集合记为 ( , )FDx D .
设 x D? . 若 nd?? 满足
( ) 0,T id Ec x i?? ?， ( ) 0 , ( )T id c x i Ix?? ?，
则称 d 为点 x 处的 线性化可行方向 ，点 x 处的所有线性化可行方向的集合记为
第九章 约束优化问题的最优性条件
128 最优化理论与方法 [乌力吉 ]
( , )LFD x D .
设 x D? . 若存在 趋向于 d 的 序列 {}kd 和 趋向于零的 正数列 {}k? ， 使 对 每个 k ， 都有
k kx d D???，
则称 d 为点 x 处的 序列可行方向 ，点 x 处的所有序列可行方向的集合记为 ( , )SFD x D .
引理 9.1.1 设 xD? 且所有约束函数都在 x 处均可微，则有
( , ) ( , ) ( , )F D x D SF D x D L F D x D??. (9.1.1)
证 如果 ( , )d FD x D? ， 则 存在 0?? ，对任意 [0, ]t ?? 都有 x td D?? ，令 kd d? ，
/2kk??? ， 1,2,k? ? ， 则显然有
k kx d D???且 ()k dd k? ??， ( )k k??? ??，
即 ( , )SFD xd D? ，故 ( , ) ( , )F D x D SF D x D? .
如果 ( , )SFD xd D? ，由序列可行方向的定义可知，存在序列 {}kd 和正数列 {}k? ，
满足
k kx d D???且 ()k dd k? ??， ( )k k??? ??.
由于所有约束函数都在 x 处均可微，故有
0 ( ) ( ) ( || ||) , k T ki k k i kkc x d c x o id dE? ? ?? ? ? ? ? ?，
0 ( ) ( ) ( || ||) , ( )i k k i kk T k kdc x d c x o d i I x? ? ?? ? ? ? ? ?，
在上两式的左右两端除以 k? ， 并 令 k?? ， 可得
( ) 0,T id Ec x i?? ?， ( ) 0 , ( )T id c x i Ix?? ?，
即 ( , )LFD xd D? ， 故 ( , ) ( , )SF D x D LFD x D? .
引理 9.1.2 设 x D? 是 约束最优化问题 (9.0.1)的局部极小点，若 ()fx 和 ()icx
( 1,2, , )im? ? 都在 x 处可微，则 对任意 ( , )SFD xd D? ，都 有 ( ) 0Tf x d??.
证 任给 ( , )SFD xd D? ，由序列可行方向的定义可知，存在序列 {}kd 和正数列 {}k? ，
满足
§ 9.1 一阶最优性条件
最优化理论与方法 [乌力吉 ] 129
k kx d D???且 ()k dd k? ??， ( )k k??? ??.
由于 ()kkxd xk? ? ? ?? 且 x 是局部极小点，故对充分大的 k ，有
( ) ( ) ( ) ( ) ( || ||)kk Tkkf x f x d f x df x o d? ? ?? ? ? ? ? ?，
在上式的左右两端除以 k? ，并令 k?? ，可得 ( ) 0Tf x d??.
注 引理 9.1.2 表明在 约束最优化问题 (9.0.1)的局部 极小点处，所有的序列可行方向都不
是 目标函数的 下降方向 .
定理 9.1.3（ Karush-Kuhn-Tucker 定理 ） 设 x D? 是 约束最优化问题 (9.0.1)的局部极小
点， ()fx和 ()icx ( 1,2, , )im? ? 都在 x 处可微 . 若
( , ) ( , )SFD x D L FD x D? ， (9.1.2)
则存在 i? ( 1,2, , )im? ? ， 满足
1( ) ( )
m
iiif x c x??? ? ??
， (9.1.3)
( ) 0, i Ec xi??， (9.1.4)
0 , ( ) 0 , ( ) 0 , i i i ic x c x i I?? ? ? ? ?. (9.1.5)
证 由引理 9.1.2 及条件 (9.1.2)可知 ， 对任意 ( , )LFD xd D? ，有 ( ) 0Tf x d??. 而由
( , )LFD x D 的定义又知，
( ) 0,T id Ec x i?? ?， ( ) 0 , ( )T id c x i Ix?? ?.
这表明不等式组
( ) 0 , T idc Exi?? ?，
( ) 0 , T idiEcx? ? ? ?
( ) 0 , ( )T id c x i Ix?? ?，
( ) 0Tf x d??
无解 ，从而 由 Farkas 引理知 ， 存在 10i? ? ()iE? 和 20i? ? ()iE? 以及 0i??? ( ( ))i I x?? ，
使得
第九章 约束优化问题的最优性条件
130 最优化理论与方法 [乌力吉 ]
12
( )( ) ( ) ( ) ( )ii i i ii E i I xf x c x c x? ? ???? ? ? ? ? ???
，
再令 12 iii? ? ???( )i E? ， 0i? ? ( ))\(i I I x? ， 再结合 x D? ， 我们得到等式
(9.1.3)，不等式 (9.1.4)和 (9.1.5).
注 （ 1） 称
1( , ) ( ) ( ) ( ) ( )
mT
iiiL x f x c x f x c x? ? ??? ? ? ? ?
为 Lagrange 函数， i? 称为 Lagrange 乘子；
（ 2） (9.1.3)- (9.1.5)通常称为 约束最优化问题 (9.0.1)的 K-K-T 条件（ Karush-Kuhn-Tucker
条件），而满足 (9.1.3)- (9.1.5)的点 x D? 称为 K-K-T 点，（ 9.1.5） 称为互补松弛条件；
（ 3）条件 (9.1.2)称为 约束规范性条件 ，简称约束规范 (Constraint Qualification). 当条
件 (9.1.2)不 成立时，局部极小点不一定是 K-K-T 点 .
例如，考察
1
3
1 1 2
22
m
s.
in
( ) 0 ,
t.
( ) 0
cx
x
xx
c x x
? ? ?
??
显然， (0,0)x ? 是其最优解，而 ( ) (1,0)Tfx?? 不可能 是
1( ) (0,1)Tcx??， 2 ( ) (0,1)Tcx??
的 线性组合，更不用说非负线性组合 . 究其原因，原来
( , ) { | ( 1 , 0) , { | ( 1 , 0) ,0 } } ( , )SF D x D x L F Dx x x xD? ? ? ?? ? ?? ??? ?，
其中 31 2 1 1 2 2 2, ) | ( ) 0 , ( }( 0{ )x c x x xD cx xx? ? ? ? ?? .
（ 4） 如果不要求约束规范性条件 (9.1.2)，我们只能证明如下的 Fritz-John 必要条件：
设 ()fx 和 ()icx ( 1,2, , )im? ? 都在 x 处可微 . 若 x D? 是 约束最优化问题 (9.0.1)的
局部极小点，则必存在 0 0? ? ， i? ?? ， 1,2 ,,i m? ? ，使得
0 1 ( ) ( ) 0
m
iiif x c x???? ? ? ??
，
20 , ( ) 0 , ; ( 0 )i i i i
iIc x i I? ?? ? ? ??
.
§ 9.1 一阶最优性条件
最优化理论与方法 [乌力吉 ] 131
如果 0 0?? 时， 则上述结论就 是 K-K-T 条件； 如果 0 0?? ， 则 目标函数从条件中消失 ，
这时上述结论仅 仅描述了约束条件之间的关系，使得到的 Fritz-John 点不是极小点的可能性
增大， 这 也是 Fritz-John 条件不如 Karush-Kuhn-Tucker 条件使用广泛的原因 .
（ 5） Lagrange 乘子的意义 . 讨论仅含一个约束条件的简单情形 .
对于等式约束情形 m in{ ( ) | 0) }(f x c x ?， 设 x 和 ? 是其 最优解 及对应的 乘子 . 下面
考察这个约束优化问题的扰动问题 m in{ ( ) | ( ) }f x c x ??，假设 其最优解及其乘子 ( )x ? 和
( )??连续可微 ，且满足 (0) xx? ， (0) ??? . 由于 ( ( ))cx ??? ， 利用等式 (9.1.3),
我们 有
0 0 0
( ) ( )( ( ) ) ( ) ( )TTd d x d xf x f x c xd d d
? ? ?
????? ? ?
? ? ?? ? ? ?
，
0 ( ( ) )
d cxd
?? ? ?? ???
.
对于等式约束情形 m in{ ( ) | 0) }(f x c x ?，如果 ( ) 0cx? ，则对充分小的 ? ，也有
( ( ))cx ??? ，这时，由上面的讨论可知
0( ( ))
d fxd
???? ? ?
；如果 ( ) 0cx? ，这时，
x 是无约束最优化问题 min ( )
nx fx??
的一个局部极小点，故对充分小的 ? 有 ( ) xx? ? ，因
此，仍有
00
( ( ) ) ( ) 0 Td d xf x f xdd
????????? ? ? ?
.
定理 9.1.4（线性约束规范， LCQ） 若所有的 ()icx( ( ))i E I x?? 都是线性函数 ，则约
束规范条件 (9.1.2)成立 .
证 对任意 ( , )LFD xd D? ，取 kdd? ， 12
k k? ?
，由于 ()icx( ( ))i E I x?? 是线性
函数 ， x D? 且
( ) 0,T id Ec x i?? ?， ( ) 0 , ( )T id c x i Ix?? ?，
故 有
( ) ( ) ( ) 0ik Ti k ik dc x d c x c x??? ? ? ? ?， iE? ，
第九章 约束优化问题的最优性条件
132 最优化理论与方法 [乌力吉 ]
( ) ( ) ( ) 0ik Ti k ik dc x d c x c x??? ? ? ? ?， ( )i I x? .
而 对 ( )\i I I x? ， 由 ( ) 0icx? 及 0k?? 可 知， 当 k 充分大时 ， 就 有 ( ) 0kikc x d???，
即有 k kx d D???，这表明 ( , )SFD xd D? ，从而有 ( , ) ( , )LFD x D SF D x D? . 再结
合 (9.1.1)可知 (9.1.2)成立 .
定理 9.1.5（ Mangasarian-Fromowitz 约束规范， MFCQ） 如果
（ 1） ( )( )ic x i E??线性无关 ，
（ 2） 集合 ? ? ( ) 0 , ; ( ) 0 , ( )TT
iiS d d c x i E d c x i I x? ? ? ? ? ? ?
非空 ，
则约束规范条件 (9.1.2)成立 .
证 设 d 是 S? 中任一 非零 向量，令 ( 1, 2 , , 1)ied i n m? ? ?? 是子空间
12s p a n { ( ) , ( ) , , ( ) , }emc x c x c x d? ? ??
的正交补中的标准正交基 . 由于 dS?? ，故 d 与 1( )( )c x i E??正交， 因而上述生成子空间
的维数为 1em? . 考虑下面以 ? 为参数的非线性方程组
( ) 0 , 1 , 2 , , ,
( ) 0 , 1 , 2 , , 1 ,
( ) 0 ,
ie
T
T
c x i m
d x x i n m
d x x ?
????
? ? ? ? ??
? ? ? ??
?
? （ 9.1.6）
它将确定以 ? 为参数的一个隐函数 ()xx?? . 由于在 xx? 处， 非线性 方程组 （ 9.1.6） 的
Jacobi 矩阵非奇异，且 0, xx? ??是方程组的解 . 根据隐函数定理，对充分小的 ? ，必存
在解 ()xx?? 且满足 0 2( ) / || ||x d d?? ?? ? . 事实上，将方程组确定的隐函数对 ? 求导，有
( ) ( ) 0 , 1 , 2 , , ,
( ) 0 , 1 , 2 , , 1 ,
( ) 1 ,
T
ie
T
T
c x x i m
d x i n m
dx
?
?
?
?? ? ? ??
? ? ? ? ??
? ? ??
?
? （ 9.1.7）
令 0?? ， 则 方程组 (9.1.7)的 系数矩阵非奇异，故有唯一解，显然 ， 2/|| ||dd是其 解， 故有
0 2( ) / || ||x d d?? ?? ? .
由于 ()x? 是由方程组 (9.1.6)确定的隐函数， 故有 ( ( )) 0 ( )ic x i E? ??； 当 ( )i I x? 时，
由 S? 的定义，有 ( ) 0T id c x??， 故当 ? 充分小时，有
§ 9.1 一阶最优性条件
最优化理论与方法 [乌力吉 ] 133
( ( ) ) ( ( ) ) ( ) ( ( ) ) ( ( 0 ) ) ( ( ) ) ( )Ti i i i i ic x c x c x c x c x c x x? ? ? ? ? ??? ? ? ? ? ?，
由于当 0?? 时，有
2( ( ) ) ( ) ( ) ( 0 ) ( ) / || || 0T T Ti i ic x x c x x c x d d?? ??? ? ? ? ? ?，
故 ( ( )) 0icx? ? ； 当 ( )\i I I x? 时， 由于 ( ) 0icx? ， 故当 ? 充分小时，有 ( ( )) 0icx? ? . 因
此 当 ? 充分小时， 有 ()xD? ? .
对充分小的 0k?? ，取 [ ( ) ] / kk kd x x????， 1,2,k? ? ，则有
2[ ( ) ] / ''( 0 ) / || 0)|| (k kkkd x x x d d?? ?? ? ? ? ?，
由 前面的讨论知 ( )kkkx d x D??? ? ?， 而 由 ( , )SFD x D 定义 知 2/ || || ( , )d d SFD x D? ，
故 ( , )d SFD x D? .
这样，我们证明了 ( , )S SFD x D? ? . 再由 ( , )SFD x D 是闭集 ，有
cl( ) ( , )S SFD x D? ? .
由于
? ?c l ( ) ( ) 0 , ; ( ) 0 , ( ) ( , )TTiiS d d c x i E d c x i I x L F D x D? ? ? ? ? ? ? ? ?，
故等式 (9.1.2)成立 .
定理 9.1.6（线性无关约束规范， LICQ） 若在 x 处 ( )icx? ( ( ))i E I x?? 线性无关，
则约束规范条件 (9.1.2)成立 .
证 若 ( )Ix?? ，则 由 定理 9.1.5 可知 结论成立 .
假设 ( )Ix?? ，不妨设 ? ?( ) 1, 2 , ,E I x k?? ?.
对任意 ( )j I x? ， 由于 ( )icx? ( 1,2 ),, ki ? ? 线性无关 ，记 1 1 1, , , , ,j j ka a a a????是
1 1 1s p a n { ( ) , , ( ) , ( ) , , ( ) }j j kc x c x c x c x??? ? ? ? (9.1.8)
的 一组标准正交基 .
取 ( ) ( )
Tj i i
ij jc x c x a ad ????? ? ?
，则 d 与 ()ia ij?? 均正交 ，从而与生成空间 (9.1.8)
正交， 且有
第九章 约束优化问题的最优性条件
134 最优化理论与方法 [乌力吉 ]
2( ) ( ( ) ) | | | |jT T Tj i i
ijc x d d c x ad a d??? ? ? ? ??
.
取 2/ || ||j dd d? ，则有
( ) 1Tjjcx d? ? ， ( ) 0Tijcx d? ? ()ij?? . (9.1.9)
对每个 ( )j I x? ，均可构造出 具有性质 (9.1.9)的 jd ， 令
()jj I xdd??? ?
， 易见 dS?? ，
故 S? 非空， 从而 由定理 9.1.5 可知结论成立 .
定理 9.1.7（一阶充分性条件） 设 xD? ，若 ()fx和 ()icx在 x 处都可微，且 对任意
( , )d SFD x D? ，都有
( ) 0Td f x??， （ 9.1.10）
则 x 是 约束最优化问题 (9.0.1)的 严格局部极小点 .
证 假设 x 不是严格 局部 极小点，则存在 kxD? ，使得 ( )kx x k? ??， kxx?
( 1,2, )k? ? ，且满足
( ) ( )kf x f x? . （ 9.1.11）
令
, || |||| || kkkkkxxd x xxx ??? ? ?? ，
不失一般性，设 lim
k kdd?? ?
（否则，取其收敛子序列）， 这表明 ( , )d SFD x D? . 再 由 （ 9.1.11）
及 Lagrange 中值定理 ， 对任意 k ， 有
( ) ( ) 0kT kf x x x? ? ?，
其中 kx 位于由 kx 与 x 确定的线段上 ， 进而 对任意 k ， 有
( )( ) 0|| ||kT kkxxfx xx????，
令 k?? ，即得 ( ) 0Td f x??， 这与 条件 （ 9.1.10）矛盾 ，矛盾表明定理结论成立 .
§ 9.2 二阶最优性条件
最优化理论与方法 [乌力吉 ] 135
§9.2 二阶最优性条件
若 对任意 0 ( , )d SFD x D?? ，都有 ( ) 0T fxd ??， 则由 定理 9.1.7 可 知 x 是 约束最
优化问题 (9.0.1)的 严格 局部 极小点； 若存在 0 ( , )d SFD x D?? ， 使得 ( ) 0T fxd ??， 则 d
是 x 处的一个下降可行方向，因而 x 不是极小点 . 但若这两种情形都不出现，即 对任意
( , )d SFD x D? ，都有
( ) 0T fxd ??， （ 9.2.1）
且 存在 0 ( , )d SFD x D?? ，使得
( ) 0T fxd ??， （ 9.2.2）
如果仍假定约束规范性条件满足，那么类似定理 9.1.3 的证明 ， 可知 x 是 K-K-T 点 . 记 ?
是相应的 Lagrange 乘子，显然对使（ 9.2.2）成立的 d ，有
1( ) 0)(
mTT
ii id f x d c x??? ? ? ??
.
而 由 ( , ) ( , )SF D x D LFD x D? 知 ， ( , )d LFD x D? ， 从而 由 ( , )LFD x D 的定义和 上式
可 得，对任意 ( )i Ix? ，有 (0 )T ii d c x? ??.
设 x 是 K-K-T 点 ， ? 是相应的 Lagrange 乘子， 若 ( , )d LFD x D? 满足： 对任意
( )i Ix? ，有 (0 )T ii d c x? ??， 则称 d 是在 x 处 的 线性化零约束方向 ， x 处 所有线性
化零约束方向 的集合 记为 ( , )Gx? . 若 x 处 的 Lagrange 乘子 ? 唯一，则简记为 ()Gx .
设 x 是 K-K-T 点， ? 是相应的 Lagrange 乘子， 如果存在向量序列 {}kd 和 正 数列 {}k? ，
使得
k kx d D???，
1 )0 (
m
ik kii c x d??? ???
，
且有 ( )kd d k? ??， 0( )k k? ? ??，则称 d 是 在 x 处的 序列零约束方向 ， x 处所
有序列零约束方向的集合 记为 ( , )Sx? .
由定义显然有
第九章 约束优化问题的最优性条件
136 最优化理论与方法 [乌力吉 ]
( , ) ( , )G x LF D x D? ? ， ( , ) ( , )S x SFD x D? ? .
且类似于 ( , ) ( , )SF D x D LFD x D? ，可以证明 ( , ) ( , )S x G x??? .
事实上，任取 ( , )d S x ?? ，由 ( , )Sx? 的定义知，存在 序列 {}kd 和正数列 {}k? ，
使得 ( )kd d k? ??， 0( )k k? ? ??， k kx d D???，且有
( ) 0kikc x d???， ( )i E I x?? ? ； ( ) 0kikc x d???， \( ) ( )i I x I x?? ，
这里 ( ) { ( ) 0 }| iI x i I x ?? ? ??.
当 ( )i E I x?? ? 时，有
0 ( ) ( ) ( ) ( ) ( ) ( )k T k k T ki k i k i k k i k kc x d c x c x d d c x d d? ? ? ? ? ? ?? ? ? ? ? ? ? ? ?，
两边除 k? ， 并 令 k?? ，得 ( ) 0T id c x??.
当 \( ) ( )i I x I x?? 时，有
0 ( ) ( ) ( )k T ki k k k kic x d c x d d? ? ? ?? ? ? ? ?，
类似可得 ( ) 0T id c x??， 故有 ( , )d G x ?? ，从而 有 ( , ) ( , )S x G x??? .
定理 9.2.1（二阶必要条件） 设 x 是 约束最优化问题 (9.0.1)的局部极小点 ， ? 是对应
的 Lagrange 乘子， 则对任意 ( , )d S x ?? ，必有
2 ( , ) 0T xxd L x d???. （ 9.2.3）
证 任给 ( , )Sxd ?? ，若 0d? ，则 (9.2.3)显然成立 . 故不妨设 0d? ，由 ( , )Sx?
的定义知，存在 向量序列 {}kd 和正数列 {}k? ，使得
k kx d D???，
1 )0 (
m
ik kii c x d??? ???
，
且有 ( )kd d k? ??， 0( )k k? ? ??，因此，有
( ) ( , )kkkkf x d L x d? ? ?? ? ?
2 2 21( , ) ( )2( , ) ( , )T k T kk k k kL x dL ddxL ox??? ? ? ?? ? ? ???
§ 9.2 二阶最优性条件
最优化理论与方法 [乌力吉 ] 137
2 2 21( ) ( )2 ( , )Tkk k kLf x d x do ???? ? ??， （ 9.2.4）
由于 x 是 (9.0.1)的局部极小点，故对充分大的 k ，有 () ) (kk ff x d x? ?? . 从而由 (9.2.4)，
有
2 2 2( , )1 ()2 0Tkk k kddx oL ??????，
不等号两边除以 2k? 并令 k?? ， 可得到不等式 (9.2.3).
定理 9.2.2（二阶充分条件） 设 x 是 约束最优化问题 (9.0.1)的 一个 K-K-T 点， ? 是对
应的 Lagrange 乘子 . 如果 对任意 0 ( , )d G x ??? ， 都有
2 ( , ) 0T xxd L x d???， （ 9.2.5）
则 x 是严格 局部 极小点 .
证 假设 x 是严格局部极小点，则存在 kx D? ，使得 kx x? 且 (( ) )kf fxx ? ，
1,2,k? ? . 不失一般性，我们假设
|| | | ()
k
kxxxx dk?? ? ? ?
，
由定理 9.1.7 的证明看到，
( ) 0T fxd ??， ( , )Sxd D? .
而由 ( , ) ( , )S x D L x Dd ??，我们有
1( ) ( ) 0
mTT
iiiddf x c x??? ? ? ??
.
因此，必有 ( ) 0T fxd ??且对任意 ( )i Ix? 有 ( )0Tiid cx? ??，即 ( , )Gxd ?? . 而
由 (( ) )kf fxx ? ，我们又有
2 2 21( , ) ( , ) ( )( , ) ( ,2 )k T kk k kL x LL x L x d d ox? ? ??? ?????? ，
其中 |||| kk x x? ?? . 由此可得 2 ( , ) 0Td L x d???，与不等式 (9.2.5)矛盾，矛盾表明 x 是
约束最优化问题 (9.0.1)的严格局部极小点 .
第九章 约束优化问题的最优性条件
138 最优化理论与方法 [乌力吉 ]
注 （ 1） 一阶充分性条件与二阶充分性条件不是谁比谁弱的关系，彼此之间不存在简单
的逻辑蕴含 关系 .
（ 2） 对于 一阶充分性条件 (9.1.10)， 若出现某些 ( , )d SFD x D? ， 使得 ( ) 0Td f x??，
这时一阶 充分 条件无效，可以转而考察二阶 充分 条件 .
§9.3 凸规划问题
在一个约束最优化问题中，如果目标函数 ()fx是凸函数，且可行域 D 是凸集，则称优
化问题 min ( )
Dx fx?
为凸规划问题 . 特别地，约束最优化问题
12
m in ( )
s . t. ( ) 0 , { 1 , 2 , , }
( ) 0 , { , , , }
ie
i e e
fx
c x i E m
c x i I m m m??
? ? ?
? ? ?
?
?
(9.3.1)
当 ()fx和 ( )( )ic x i I? ? 是凸函数， ( )( )i xc iE? 是仿射函数时，优化问题 (9.3.1)是凸规划 问
题 .
定理 9.3.1 凸规划问题 min ( )
Dx fx?
的任意局部极小点都是全局极小点 .
证 设 xD? 为 min ( )
Dx fx?
的局部最优解，若它不是全局最优解，则必存在 yD? ，满
足 ( ) ( )f y f x? ，因此，对 任意 (0,1)?? ，有
[ ( 1 ) ] ( 1 ) ( ) ( ) ( )f x y f x f y f x? ? ? ?? ? ? ? ? ?，
故当 0?? 时， 有
(1 )x y x??? ? ?且 [(1 ) ] ( )f x y f x??? ? ?，
但这 与 x 为 min ( )
Dx fx?
的局部最优解矛盾，矛盾表明 x 必为全局最优解 .
定理 9.3.2 若 ()fx为严格凸函数，且凸规划问题 min ( )
Dx fx?
有最优解，则最优解必唯
一 .
证 设 x 是 min ( )
Dx fx?
的全局最优解，而 y 是另一个全局最优解， yx? . 由严格凸函数
的定义可知，对任意 (0,1)?? ，有
[ ( 1 ) ] ( 1 ) ( ) ( ) ( )f x y f x f y f x? ? ? ?? ? ? ? ? ?，
§ 9.3 凸规划问题
最优化理论与方法 [乌力吉 ] 139
这与 x 为 min ( )
Dx fx?
的全局 最优解矛盾， 矛盾表明 最优解唯一 .
定理 9.3.3 在 凸规划问题 (9.3.1)中， 若 ()fx和 ( )( )i x i E Ic ??都在 x 可微，且 x 是
(9.3.1)的 K-K-T 点，则 x 是 (9.3.1)的全局最优解 .
证 由于 ()fx是可行域 D 上的凸函数，故对任意 x D? ，有
( ) ( ) ( ) ( )Tf x f x f x x x? ? ? ?，
再由 ()icx? 的凸性，有
( ) ( ) ( ) ( )Ti i ic x c x c x x x? ? ? ?.
当 ( )i E I x?? 时， ( ) 0icx? ，而 ( ) 0icx? ，故有
( ) ( ) 0Tic x x x? ? ?，
而当 ( )\i I I x? 时，由互补松弛条件有 0i?? ， 从而
( ) ( ) 0Tiic x x x? ? ? ?，
于是，我们 有
1( ) ( ) ( ) ( ) ( )
m T
iiif x f x c x x x f x??? ? ? ? ??
，
这表明 x 是 (9.3.1)的 全局最优解 .
第九章 约束优化问题的最优性条件
140 最优化理论与方法 [乌力吉 ]
|
|
