第 十三 章 可行方向法
可行方向法是求解约束最优化问题的一类 方法 ， 其 基本思想是 从 一个 可行点出发 ， 沿着
目标函数的一个 下降方向进行 一维 搜索， 得到 使目标函数值下降的新的可行点 . 由于 可行方
向法的 主要 步骤是选择可行搜索方向和确定沿此方向保证下一个迭代点仍为可行点的步长，
因此 ，它 可以看作是 无约束最优化问题下降算法 在 处理 约束最优化问题上 的一个合理推广 .
根据确定 搜索方向的不同 策略， 形成 了如下几个经典的 可行 方向法 . 在本章中，我们首
先针对具有线性约束的最优化问题，给出一般可行方向法的基本框架 .
§13.1 线性约束最优化 问题的可行方向
考察具有线性约束的最优化问题
{}
m in ( )
, 1 , 2 , ,. .
, { 1 , 2 , , }
T
i i e
T
i i e e
fx
a x b i mst
a x b i m m m
E
I
? ????
? ? ? ?
?
? ??
?
?
（ 13.1.1）
将其可行域记为
| 0 0 ,{} ; 0 ,TTi i in iD x a x b i a x bE i I?? ? ? ? ? ? ??? ，
（ 13.1.2）
并记 不等式约束的 积极约束 指标集为
{( ) | }0TiiI x i I a x b? ? ? ?.
（ 13.1.3）
定理 13.1.1 设 x 是 线性 约束 最优化 问题（ 13.1.1）的可行点，则 非零向量 d 为（ 13.1.1）
在 x 处的 可行方向的充分必要条件是
,()0 .0,,Ti
Ti
a d iad EIxi?? ?? ??
?
（ 13.1.4）
证 必要性 . 设 x 是 可行点 ， d 为 x 处的可行方向，则存在 0?? ，使当 [0, ]t ?? 时，
有 x td D??，即有
? ?? ? 0,0, ,( ) .TiiTa x td b ia x td b i EIx??? ? ?? ? ?
（ 13.1.5）
由于 x D? ，故有 0, ()Tiia x b i E I x???? ，从而 (13.1.4)式 成立 .
充分性 . 设 x 是可行点，向量 d 满足 (13.1.4)式 . 则对任意 0t? ，式 (13.1.5)总成立 . 当
\ ( )i I I x? 时，由于 0Tiia x b??，只要取
第十三章 可行方向法
228 最优化理论与方法 [乌力吉 ]
m i n { | \ ( ) } , \0 , { | 0 , ( ) } ,
,
TTTi
iiiT
i
a I I x a I I xa x b d i i d ida? ? ? ? ??? ? ???? ?
? ??? 否 则 ，
（ 13.1.6）
则当 [0,t ?? ） 时，都有 x td D??，这表明 d 是 x 处的 一个 可行方向 .
由定理 13.1.1 不难看到，如果非零向量 d 同时满足（ 13.1.4）和下降方向的条件
( ) 0T fd x??，
（ 13.1.7）
则 d 为 x 处 的可行下降方向 .
因此， 算法 13.1 中确定搜索方向就是找到一个同时满足式 (13.1.4)和 (13.1.7)的非 零向量
的策略 .
算法 13.1 的下降方向一旦被确定，接下来就要沿着这个方向进行线搜索，不同于无约
束最优化问题的线搜索，这里的线搜索必须保证产生的新迭代点是可行点，即 精确线搜索策
略下的步长 k? 为一维约束最优化问题
min ( )s.t. 0 tf x td????
（ 13.1.8）
的最优解，其中 ? 由 (13.1.6)所确定 .
§13.2 Zoutendijk 可行方向法
§13.2.1 线性约束的情形
Zoutendijk 可行方向法 是由 G.zoutendijk 在 1960 年首先提出来的 . 对于线性 约束 最 优化
问题 （ 13.1.1） ， Zoutendijk 可行方向法是在满足 可行条件 (13.1.4)和 下降条件 (13.1.7)的可行方
向中 ， 寻找最速下降方向 ， 即 在点 x 处求解 线性规划子问题
1 , 1 , 2 ,
m in ( )
0 , ,
s.t.
,
0 , ( )
1 .
,
T
i
T
i
T
i
j
fx
a d i E
a d i I x
d
d j n
? ??
? ??
?
? ? ?
?
??
? ?
（ 13.2.1）
由于子问题 (13.2.1)的可行域是有界的，故子 问题 (13.2.1)总是有 最优 解的 .
定理 13.2.1 在 线性约束最优化问题（ 13.1.1） 中， 设 x 是可行点， 则 x 是其 K-K-T 点
的充分必要条件是 子问题 （ 13.2.1）的 目标函数最优值 为 0 .
证 必要性 . 设 x 是线性约束最优化问题（ 13.1.1）的 K-K-T 点，则存在乘子 ? 和 0?? ，
使得等式
§ 13.2 Zoutendijk 可行方向法
最优化理论与方法 [乌力吉 ] 229
()( ) 0i i i ii E i I xf ax a?????? ? ???
，
由此得
()( ) 0
T T Ti i i i
i E i I xa d a df x d ? ????? ? ???
.
另一方面， d?0 是子问题（ 13.2.1）的一个可行 解 ，从而必有 目标函数最优值 ( ) 0Tf x d??，
结合上述两式， 我们有 ( ) 0Tf x d??.
充分性 . 设子问题（ 13.2.1）的 目标函数最优值 为 0 ，即有 ( ) 0Tf x d??. 这意味着不
等式组
()0 , 0 , 0; 0 , ;T T Tii Tia d a d i E a d i fI xd? ? ? ? ? ???
无解，由 Farkas 引理可知，存在向量 1 0?? ， 2 0?? 和 0?? ，使得
1
( ( )
2
)()
T T T T T Ti i i i i i i i i i
i E i E i I x i E i I xf x d a d a d a d a d a d?? ???? ? ? ? ?? ? ?? ? ?? ? ? ? ?
，
其中 12i i i? ???? ， i E? ，由于 x 是可行点， 故 x 是 K-K-T 点 .
算法 13.1（ 线性约束情形的 Zoutendijk 可行方向法）
步 1： 给定初始可行点 0x D? ，置 0k? ；
步 2： 确定 迭代点 kx 处的有效约束指标集 k {( ) 0 }| TkiiI x i I a x b? ? ? ?；
步 3： 确定可行搜索方向，在 kx 处 求解线性规划子问题 (13.2.1)，得到最优解 kd ；
步 4： 如果 ( ) 0k T kf x d??，则算法结束，输出近似解 kx ；
步 5： 利用 (13.1.6)计算 可行 步长的上界 k? ，再利用 (13.1.8)计算最优步长 k? ；
步 6： 令 1k k kkdxx?? ?? ，置 1kk??，转步 2.
§13.2.2 非线性约束的情形
下面考察 不等式非线性约束优化问题
m in ( )s.t . ( ) 0 , {1 , 2 , , }
i iI
fxcx m? ? ? ? （ 13.2.2）
其中 (( )), )(i xfc ix I? 都是 连续 可微函数 .
为了在可行点 x 处确定可行下降方向，我们首先证明如下定理 .
定理 13.2.2 在非线性约束最优 化问题（ 13.2.2）中， 设 x 是可行点， 如果向量 d 满足
( ) 0Tf x d??， ( ) 0 , ( )Tic x d i I x? ? ?， （ 13.2.3）
则 d 必定 是可行下降方向 .
证 由于 ( ) 0Tf x d??，故 d 是目标函数 ()fx的下降方向 . 对于每个 i I? ， ()icx 在 x
处的一阶 Taylor 展开式为
第十三章 可行方向法
230 最优化理论与方法 [乌力吉 ]
( ) ( ) ( ) ( || ||)Ti i ix d x ccc x d o d? ? ?? ? ? ? ?.
当 ()i Ix? 时，有 ( ) 0 , ( ) 0Tiix c xc d? ? ?，当 \ ( )i I I x? 时，有 ( ) 0ic x ? ， 因此，必
定存在充分小的数 0?? ，满足对任意 [0, ]? ?? 和每个 i I? ，有
)(0i xcd???，
这表明 d 是可行方向，从而 d 是可行下降方向 .
对于非线性约束最优化问题（ 13.2.2），我们仍然寻找最速下降方向 . 依据定理 13.2.2 的
结论，为了确定可行下降方向 d ， 在点 x 处求解线性规划子问题 m in
( ) 0 ,
s. t. (
1 , 1 , 2 ,
) 0 , ( ) ,
1 ,.
T
T
i
j
z
fx
c x i
dz
dz
d
Ix
jn
? ?
? ?
??
??
?
?
?
?
? ? ?
? ?
（ 13.2.4）
由于 ,0dz??0 是 (13.2.4)的一个可行解，故在 (13.2.4)中，目标函数的最优值不会大于零 . 设
( , )dz 是 (13.2.4)的最优解，若 0z? ，则 d 是可行下降方向 ，否则有如下定理 .
定理 13.2.3 在非线性约束最优化问题（ 13.2.2）中， 设 x 是可行点， 则 x 是其 Fritz-John
点的充分必要条件是子问题（ 13.2.4）的 目标函数最优值 为 0 .
证 非 线性约束最优化问题（ 13.2.2） 的 目标函数最优值 为 0 的充分必要条件为不等式组
(13.2.3)无解，而由 Gordan 定理可知， 不等式组
( ) 0Tf x d??， ( ) 0 , ( )Tic x d i I x?? ? ?
无解的充分必要条件是 存在 0?? ，使得等式
0 ()( ()0)iii I x xf x c?? ? ?????
，
从而 x 是 Fritz-John 点 .
算法 13.2（非线性约束情形的 Zoutendijk 可行方向法）
步 1： 给定初始可行点 0x D? ，置 0k? ；
步 2： 确定 迭代点 kx 处的有效约束指标集 ( ) | ) 0{ ( }kkiI x i I c x? ? ?；
步 3： 确定可行搜索方向，在 kx 处 求解线性规划子问题 (13.2.4)，得到最优解 kd 和 kz ；
步 4： 如果 0kz ? ，则算法结束，输出近似解 kx ；
步 5： 确定可行步长的上界
{ | ( ) 0 , ( ) }s u p k k kik t c x td i I x? ? ? ?? ，
再通过求解一维搜索问题
min ( )s.t. 0 k
k
kf x td
t ????
§ 13.3 Rosen 梯度投影法
最优化理论与方法 [乌力吉 ] 231
得到最优步长 k? ；
步 6： 令 1k k kkdxx?? ?? ，置 1kk??，转步 2.
非线性约束情形下的 Zoutendijk 可行方向法 由于不能保证方向映射 ( ,)kkkxxd? 和一
维搜索映射 1,)( k k kx dx?? 是闭 映射 ， 故算法 产生的 迭代 序列可能不收敛于 K-K-T 点 . 另外，
Zoutendijk 可行方向法是基于无约束最优化问题的最速下降法，这样，最速下降法的缺点 “锯
齿现象 ”仍然会出现 .
为了避免这种 “锯齿现象 ”， Topkis 和 Veinott 对 Zoutendijk 可行方向法提出了改进策略，
把求可行下降方向的线性规划改写成 m in
( ) 0 ,
s . t. ( ) ( )
1 , 1 , 2 , , .
,,
1
T
T
ii
j
fx
cx
z
dz
dz
d j n
c x i I
? ?
? ??
??
??
?
?
?
?
? ? ?
? ?
（ 13.2.5）
经过修改， 积极约束 和不 积极约束 在确定下降可行方向 时 均起到作用，并且在接近不 积
极约束 边界时，不至发生方向突然改变 . 当然，该策略形成的算法所产生的序列仍然收敛到
原问题的 Fritz-John 点，而不是 K-K-T 点 .
§13.3 Rosen 梯度投影法
在本节中，我们继续 考察具有线性约束的最优化问题
{}
m in ( )
, 1 , 2 , ,. .
, { 1 , 2 , , }
T
i i e
T
i i e e
fx
a x b i mst
a x b i m m m
E
I
? ????
? ? ? ?
?
? ??
?
?
（ 13.3.1）
梯度投影法首先由 Rosen 在 1960 年提出，并由 Gordfarb 和 Lapidus 在 1968 年加以改进 .
投影梯度法的基本思想仍然是从可行点 x 出发，沿可行方向进行搜索 . 当迭代出发点 x 在可
行域内部时 ， 沿着负梯度 ()fx?? 方向搜索 ； 当迭代出发点 x 在 某些约束的边界上时， 首先
将该点处的 负梯度 ()fx?? 投影到以 积极约束 的梯度 的转置 为行构成的矩阵 ()E I xA? 的零空
间
(){ | }E I xx A x? ? 0
上 ， 然后 再沿此方向进行搜索 .
下面将要证明，这样的投影 方向是 线性约束最优化问题 (13.3.1)的 可行 下降方向，因此 ，
Rosen 梯度投影法也是可行方向法 .
设 可行点 kx 是当前迭代点， 显然， ()kfx?? 是 目标函数在 kx 处的 下降方向， 但当存
第十三章 可行方向法
232 最优化理论与方法 [乌力吉 ]
在 ()ki Ix? ，满足 ( ) 0Tki fxa ??时，在点 kx 处负梯度 方向不再是 问题 (13.3.1)的 可行方向，
而对于每个 i E? ，只要 ( ) 0Tki fxa ??，则负梯度方向就不是 问题 (13.3.1)的 可行方向 . 事实
上，我们知道一个方向 d 成为 可行方向必须满足 (13.1.4)式 .
为此，应对负梯度方向实施改造，一个直观的想法就是把它投影到约束它的那些超平面
的交集上 . 记 ()kkI E I x?? 为 kx 处的 积极约束 的指标集，设 d 为 ()kfx?? 在约束它的那
些超平面的交集上的投影，则 有
0Tiad? ， kiI? 或 kIAd?0 ，
这里
kIA
是以 Tia ( kiI? )为行向量的矩阵 . 根据 §11.3 中介绍的向量在线性算子的零空间上
投影 方法，我们有
()kd P f x?? ? ， （ 13.3.2）
其中 投影算子为
1()k k k kTTI I I IP I A A A A??? . （ 13.3.3）
由泛函分析中投影算子的性质可知， TPP? ， 2PP? ，从而 P 是半正定的 .
定理 13.3.1 设可行点 kx 为当前迭代点， 矩阵
kIA
行满秩， P 为相应的投影矩阵 .
（ 1） 若 ()kd P f x? ? ? ? 0，则 d 为 kx 处的一个可行下降方向 ；
（ 2）若 ()kP f x??0 ，令
1( ) ( )k k kTkI I Iu A A A f x ??? ??? ? ? ????，
其中 ? 是与等式约束对应的 em 维向量，而 ? 是与 不等式 积极 约束对应的向量 ，则当 0?? 时 ，
kx 为（ 13.3.1）的 K-K-T 点； 当 0?? 不成立 时 ，不妨设 0j?? ，令
1()k k k kTTI I I IP I A A A A??? ， ()kd P f x?? ? ，
其中
kIA
是从
kIA
中去掉 j? 对应的行后得到的矩阵，此时 d 是 kx 处的一个可行下降方向 .
证 （ 1）由于
( ) ( ) ( )k T k T kf x d f x P f x? ? ?? ?
2( ) ( ) ( ) 0k T T k kf x P P f x P f x? ? ? ? ? ? ? ?，
故 d 为 kx 处的一个下降方向 .
由 d 的定义，有
1( ( ) ) ( ) ( )k k k k k kT T k kI I I I I IA d A I A A A A f x f x?? ? ? ? ? ? ? ?O0，
这表明 0Tiad? ， kiI? ，由定理 13.1.1 知 d 为可行方向，从而 d 为可行下降方向 .
（ 2） 由 ( ) 0kP f x??，有
§ 13.3 Rosen 梯度投影法
最优化理论与方法 [乌力吉 ] 233
1( ( ) ) ( )k k k kT T kI I I II A A A A f x?? ? ?0
( )( ) ( )k k
k T k i i i iI
i i I xEf x A u f x a a??? ?? ? ? ? ? ? ???
，
由于 kx 是可行点，故当 0?? 时 ， kx 为原问题的一个 K-K-T 点 .
若 0?? 不成立， 我们 首先证明 ()kP f x??0 . 反证，设 ()kP f x??0 ，令
1( ) ( )k k kTkI I Iu A A A f x???，
则有
? ?1( ) ( ) ( ) ( )k k k k kk T T k k TI I I I IP f x I A A A A f x f x A u?? ? ? ? ? ? ? ? 0，
又由
? ? ? ?( ) k k kk T T T jjI I Ijj uf x A u A a A u a????? ? ? ? ?????，
因而有
?()kkT k T jjIIA u f x A u a?? ? ? ?，
故
? ?? 0kT jjIA u u a?? ? ?，
而 由 0j?? 知 上述齐次线性方程组有非零解 ， 但 这与
kIA
的 行 向量线性无关矛盾 .
再 证 d 是可行下降方向 . 由于 P 仍为投影矩阵，故 d 为下降方向的证明可仿情形 （ 1）
来完成 . 下面证明 d 为可行方向 . 在
k k
k TI II Tj j
A AdA d da ad??????????
?? ??
中， 类似于（ 1）的证明，
kIAd?0
显然 成立 . 再由 P 的半正定性及
kTIPA?O
， 有
? ??( ) 0kk T Tj j jT T Tj j j jjIa d a P f x a P A u w a w a P a? ? ? ? ? ? ? ? ?，
故 d 为可行方向 .
算法 13.3（ Rosen 梯度投影法）
步 1： 给定初始可行点 0x D? ，置 0k? ；
步 2： 确定 积极约束 指标集 k {( ) 0 }| TkiiI x i I a x b? ? ? ?，令 ()kkI E I x?? ；
步 3： 计算 ()kkkd P f x? ? ? ， 若 kd?0 ，则 转步 4，否则 令
1( ) ( )k k k kk kTkI I Iu A A A f x ??? ??? ? ? ????，
若 k??0 ，则算法结束，输出近似解 kx ， 否则 从 k? 中 确定 分量 0kj?? ， 并 从 矩
阵
kIA
中删去对应于 kj? 的 行 向量 得到矩阵
kIA
，再计算
1()
k k k kTTI I I IP I A A A A???
， ()kkd P f x?? ? ；
第十三章 可行方向法
234 最优化理论与方法 [乌力吉 ]
步 4： 首先通过 (13.1.6)确定 可行步长的上界 ， 再通过求解一维搜索问题
min ( )s.t. 0 k
k
kf x td
t ????
得到最优步长 k? ；
步 5： 令 1k k kkdxx?? ?? ，置 1kk??，转步 2.
对于 Rosen 梯度投影 法，我们有如下的收敛性结论 .
定理 13.3.2 设 ()fx在可行域上连续可微， 若 在任意可行点处 积极约束 的梯度 向量组
{ | ( )}kia i E I x?? 线性无关，则 Rosen 梯度投影法或者在有限步迭代后终止于 K-K-T 点；
或者产生 一个 无穷点列 {}kx ，该点列的每个 聚点 均为 K-K-T 点 .
§13.4 既约梯度法
§13.4.1 Wolf 既约梯度法
既约梯度法是由 Wolf 在 1963 年提出的一种可行方向法 .
考虑 如下 具有线性约束 的最优化 问题
min ( )
,. .
fx
Ax bst
x
???
?? 0
（ 13.4.1）
其中 目标函数 nf ?： ?? ? 连续可微， A 是 mn? 矩阵且行满秩 ， 即 ()R A m? ， b 是 m 维
向量 .
我们首先做一个非退化 假设 ：
（ 1）矩阵 A 的任意 m 个列均线性无关 ；
（ 2） 约束条件的每个基本可行解均有 m 个正分量，在此假设下，每个可行解至少有 m 个
正分量，至多有 nm? 个零分量 .
既约梯度法的基本思想 是将求解线性规划问题的单纯形法推广到求解非线性规划问题
上，即 把变量区分为 m 维 基变量 Bx 和 nm? 维 非基变量 Nx ， 通过等式约束条件把 基变量用
非基变量表示，并 将其代入目标函数，从而 从目标函数中消去基变量，得到以非基变量为自
变量的简化目标函数，进而利用此函数的负梯度构造 可行 下降方向 . 简化目标函数关于非基
变量的梯度称为目标函数的既约梯度 . 下面 给出 既约梯度法中 构造 可行下降方向的方法 .
任取矩阵 A 的 m 列 向量 构成的矩阵记为 B ，由非退化假设可知， B 是 m 阶可逆矩阵，
称为基矩阵，把 A 中剩余的列向量构成的矩阵记为 N ，称为非基矩阵， 并以 BJ 和 NJ 分别
§ 13.4 既约梯度法
最优化理论与方法 [乌力吉 ] 235
表示其列 向量 下标的指标集， 把 下标 对应于 BJ 和 NJ 的变量构成的向量分别记为 Bx 和 Nx ，
称为基变量和非基变量 . 这时，线性约束最优化问题 (13.4.1)可以写成
m in ( )
,. .
,
,
BN
BN
BN
fx
Bx Nx bs
x
xt x
????
??? 00
（ 13.4.2）
由于 B 为可逆矩阵，从约束条件 BNBx Nx b??中可解得
11BNB b xx BN???? ，
（ 13.4.3）
将其代入 (13.4.2)的目标函数，并记
11)( , )( N N Nf B bF Bx Nx x???? ，
（ 13.4.4）
则线性约束最优化问题 (13.4.2)可以写成简化形式
min ( ). . ,
B
N
Nx
F xxst ??00
（ 13.4.5）
其中 11BNB b xx BN???? . 利用复合函数求导法则， 可得
1( ) , )((( ) , )N BTN x B N x B NF x x Bf Nxx f x?? ? ? ? ?，
（ 13.4.6）
记 ()()NNrx Fx?? ， 并称其为既约梯度 . 由最速下降法可知， )( Nrx? 是最优化问题 (13.4.5)
中目标函数 )( NFx 的一个下降方向 .
下面讨论如 何利用既约梯度来构造一个可行下降方向 .
设 kd 是可行点 kx 处的一个可行下降方向，并以 ,kkBNdd分别对应基变量 kBx 和非基变
量 kBx . 根据可行性要求，我们 有
11( ) ,k k k k k kA Axx d b x x td???? ? ? ?? ? 0，
即
,k k kAd x td? ? ?00，
由此得
, , .NNk k k k k kB N B BN d x td x tdBd ? ? ? ? ? ?0 0 0
（ 13.4.7）
在简化形式 (13.4.5)中，自变量只有 Nx . 为使目标函数值下降， 一个简单的方法就是把
kNd 取成 负既约梯度方向 . 但是， 当某个 0( )kkjNxjJ?? 且 ( ) 0kjNrx? 时，沿负既约梯度方
向将导致
( ) 0kkj j Nx t r x? ? ?
对任 意 0t? 都成立，从而不满足可行性要求 (13.4.7).因此，我们定义
第十三章 可行方向法
236 最优化理论与方法 [乌力吉 ]
( ) , ( ) 0( ) , ( ) 0kkjjk
j k k kj j j
r x r xx r x r xd ? ???? ???
??
， Nj J? ，
（ 13.4.8）
由于 0( )kkjNjJx ??，故当 kNd ?0 时， 显然 有
22
( ) 0 ( ) 0 0( ) ( ) ( )kkjj
k T k k k kN N j j j
r x r xr x r x x r xd ??? ? ? ???
，
（ 13.4.9）
即 kNd 是 ()Fx在 kNx 处的下降方向 .
再根据可行性条件 (13.4.7)，取
1kkBNdBNd?? ，
（ 13.4.10）
这时， kk B
kN
dd d?????
??
满足
( ) ( ) ( ) ( )k T k k T k k T k k T kNBNNBNf x f x f x Fd d d dx? ? ? ?? ? ?，
（ 13.4.11）
故当 kNd ?0 时， kd 是 ()fx在 kx 处的下降方向 .
再由可行性条件 (13.4.7)可得，可行步长的上界
0 , { |m in { | 1 , 2 , , }, 1 , 2 ,0,
,
, } ,
k
j kk
jjk
jk
x d i i d ni
d n? ? ? ? ?
? ???
? ?
? ??
?
?
??
否 则 .
（ 13.4.12）
算法 13.4（ Wolf 既约梯度法）
步 1： 给定初始可行点 0x D? ，置 0k? ；
步 2： 从迭代点 kx 中选取 m 个大分量，其下标集记为 kBJ ， 再由 A 中下标对应于 kBJ 的
列向量构成基矩阵 B ，由其余列向量构成非基矩阵 N ，计算 )(krx ，利用式 (13.4.8)
和 (13.4.10)得到搜索方向 kd ；
步 3： 若 kd?0 ，则 算法结束，输出 K-K-T 点 kx ；
步 4： 首先通过 (13.4.12)确定可行步长的上界，再通过求解一维搜索问题
min ( )s.t. 0 k
k
kf x td
t ????
得到最优步长 k? ；
步 5： 令 1k k kkdxx?? ?? ，置 1kk??，转步 2.
定理 13.4.1 设 ()fx在 问题（ 13.4.1）的 可行域上连续可微，非退化假设 (1)和 (2)成立 . 则
在 算法 13.4 的任意迭代点 kx 处 ， 有
（ 1）当 kd?0 时 ， kd 是 ()fx在 kx 处的 可行 下降方向 ；
（ 2） kd?0 的充分必要条件为 kx 为 问题（ 13.4.1）的 K-K-T 点 .
证 （ 1）设 kd?0 ， 如果 kNd ?0 ，则由 (13.4.10)可知 kBd?0 ，与 kd?0 的假设矛盾 .
§ 13.4 既约梯度法
最优化理论与方法 [乌力吉 ] 237
故 kNd ?0 ， 这时 ， 等式 (13.4.9)和等式 (13.4.11)表明 kd 是 ()fx在 kx 处的下降方向 .
对于 kNj J? ，如果某个 0kjd? ，则由 kNd 的定义可知，必有 0kjx? ；而对于 每个 Bkj J? ，
由非退化假设 (2)及 算法 13.4 的构造可知 0kjx? ，从而保证 了 kd 是 问题（ 13.4.1）的可行 下
降 方向 .
（ 2） 充分性 . 设 kx 为 问题（ 13.4.1）的 K-K-T 点，则存在乘子 ? 和 B
N
?? ???????
??0
，满
足
)(
( )NB
k Tx B
k T Nx
fx B
fx N
?? ??? ?? ?? ??? ? ??? ?? ?? ??
????????
?
?
00，
（ 13.4.13）
, , 0k T kB B B Bx x??? ? ?00 ，
（ 13.4.14）
, , 0k kNTN N Nxx??? ? ?00 .
（ 13.4.15）
由于算法 13.4 总是保证 kBx?0 （在非退化假设下成立），故 B??0 ，从而由 (13.4.13)
可得
1 )( ) (BTkxB f x? ? ?? ，
（ 13.4.16）
( )N kTNx fx N?????
1) ) (( ( ) ( )BN k T T k kx x Nf x B f xN r x? ??? ?? ，
（ 13.4.17）
于是，由 (13.4.15)可知， 对每个 kNj J? ，有 () )(0j k kNjxrx ? ， ( ) 0kjr x ? . 故由 kNd 的定义
(13.4.8)可知 kNd ?0 ，再由 (13.4.10)可知 kBd?0 ，从而 kd?0 .
必要性 . 设 kd?0 ， 由 kNd 的定义 (13.4.8)看出，这时必有 )( kNrx?0 . 取
( )B kNNrx?? ?? ? ? ?? ? ?? ? ? ?? ? ? ?0 0
， （ 13.4.18）
由 kd?0 及 kNd 的定义，可得
(() 0)
N
T k T k T k k T k k kB B N N N N
j iNJ ix x r x x xx rx? ? ? ?? ? ? ? ??
.
（ 13.4.19）
再取 1 )( ) (
BTkxB f x? ? ??
，则有
)(
( )NB
k Tx B
k T Nx
fx B
fx N
?? ??? ?? ?? ??? ? ??? ?? ?? ??
????????
?
?
00， （ 13.4.20）
于是由式 (13.4.18),(13.4.19)以及 (13.4.20)，再结合 kx 是可行点，我们可以肯定 kx 为 问题
（ 13.4.1）的 K-K-T 点 .
§13.4.2 广义既约梯度法
Abadie 和 Carpentier 把 Wolfe 既约梯度法推广到具有非线性约束的情形 ， 给出广义既约
第十三章 可行方向法
238 最优化理论与方法 [乌力吉 ]
梯度法，简称为 GRG 算法，原来的既约梯度法则称为 RG 算法 .
考虑 变量 有界 的 等式约束 最优化 问题
( ) { 1 , 2 , , } ,
m in ( )
0,. .
, 1 , ,2,
j
iii
fx
cjst xE
l nu
m
xi
?????
??
?
???
?
?
（ 13.4.21）
其中 (( )), )(j xfc jx E?都是 连续可微函数， mn? ，变量的下界允许取 ?? ， 变量的 上界
允许取 ?? . （ 13.4.21）的可行域仍记为
| ( ) ,{}nD c x l x ux? ? ?? ?0? .
我们仍然 作出 非退化假设：对任意可行点 x D? ，存在 x 一个分解 B
N
xx x?????
??
，其中
mBx ?? ， nmNx ??? ，在 ()cx的 Jacobi 矩阵
BN
c c cx x x??? ? ?? ??? ? ???
中， m 阶子块
B
cx?? 非奇异 .
从上述假设看到，类似于既约梯度法，我们仍然把变量区分为基变量 Bx 和非基变量 Nx .
由于基变量和非基变量之间的关系 由隐函数 确定 ，因此试图解出基变量，再代入目标函数，
使目标函数只 含 非基变量一般并非可行 .
注意到一个函数的微分与自变量的微分之间的关系是线性的， 我们把目标函数 ()fx和
等式约束条件 ()cx?0 用它们的微分形式表示 .
目标函数 ()fx的微分为
))( () (B N Tx NTxBd f x df x f xx d x???? ，
（ 13.4.22）
其中 列向量
()B
B
x j
Jj
fxfx
?
???? ??
??? ?
, ()
N
N
x j
Jj
fxfx
?
???? ??
??? ?
， ()
BB j j Jdx dx ??
， ()
NN j j Jdx dx ??
.
等式约束条件 ()cx?0 的微分形式为
()() N
N
B B
NB N B
dxc x c c c cd c x d x d x d xdxx x x x x?? ??? ? ? ? ?? ? ? ? ??? ??? ? ? ? ?
????0
.
（ 13.4.23）
由于
B
cx?? 可逆，故从等式 (13.4.23)可以解出
1
NNB Bccdx dxxx
??????? ??
??
， （ 13.4.24）
将其代入 (13.4.22)，得
§ 13.4 既约梯度法
最优化理论与方法 [乌力吉 ] 239
1() ( ) ( )
BN NN
TTxx
B
ccdf x dxxf xx f x ??? ???????? ??
???? ??? ?
， （ 13.4.25）
由此得到既约梯度
1()
) ( ) ( )( N B
T
N x xNB N
ccrx
x
fx f x f x
x x
?????????
? ???????? ? ? ?? . （ 13.4.26）
下面给出 在可行点 kx 处 确定搜索方向 kd 的方法，记
) 0 }{ | , ( { | )0,( }k k k k k k kN N j j j N j j jJ j xJ l J ur x j x r x? ? ? ? ? ? ?? ，
对于每个 kNj J? ，定义
(0 , ,.),
kNk
j kkjN
Jx jd rj J??? ? ?? ?
??
（ 13.4.27）
由于 ()cx?0 是非线性方程组，故不能象线性约束那样直接求出 kBd 的表达式 . 为了保
证 kd 是可行下降方向，在得到 kNd 之后， 取适当的步长 t ，使得 kkN N Nx x td??满足可行条件
NNNl xu??， （ 13.4.28）
然后关于未知量 Bx 求解非线性方程组
)( ,0BNxcx ? ， （ 13.4.29）
得到解 Bx ，若 ( ,)BNx x 满足目标函数下降条 件
,( ) ( , )kkB N B Nx f x xfx ? ， （ 13.4.30）
以及可行条件
BBBl xu??， （ 13.4.31）
则取新的迭代点
11
1
k Bk B
k NN
xxx xx ??
?
?? ?????? ??
????
，
否则，减小步长 t ，并重复上述过程 .
算法 13.5（广义既约梯度法）
步 1： 给定初始可行点 0x D? ， 参数 (0,1)?? ， 容许误差 0?? ， 置 0k? ；
步 2： 将 迭代点 kx 选 分成基变量 kBx 和非基变量 kNx ，利用 (13.4.26)计算 )(krx ，再依据
(13.4.27)确定 kNd ；
步 3： 若 || ||kNd ?? ，则 算法结束，输出近似解 kx ；
步 4： 取试探步长 0t? ，令 kkN N Nx x td??，若 Nx 满足可行条件 (13.4.28)，则转步 5，
否则令 t t?? ， 转步 4；
第十三章 可行方向法
240 最优化理论与方法 [乌力吉 ]
步 5： 求解非线性方程组 (13.4.29) 得到解 Bx ， 若 ( ,)BNx x 满足 (13.4.30)和 (13.4.31)，则
转步 6，否则令 t t?? ，转步 4；
步 6： 取 11
1
k Bk B
k NN
xxx xx ??
?
?? ?????? ??
????
，置 1kk??，转步 2.
§13.5 Frank-Wolf 方法
Frank-Wolf 方法是由 Frank 和 Wolf 于 1956 年提出的求解线性约束问题的一种方法 ，其
基本思想是在每次迭代中 将目标函数 ()fx线性化，再通过求解线性规划问题得到可行下降
方向，进而沿此方向在可行域内作一维搜索 .
考察具有线性约束的最优化问题
min ( )
,. .
fx
Ax bst
x
???
?? 0
（ 13.5.1）
其中目标函数 nf ?： ?? ? 连续可微， A 是 mn? 矩阵且行满秩，即 ()R A m? ， b 是 m 维
向量 .
我们首先在可行点 kx 处将目标函数 ()fx按 Taylor 公式一阶展开，即
( ) ( ) ( ) ( ) ( )k k T k Lf x f x f x x x f x? ? ? ? ?， （ 13.5.2）
然后求解线性规划问题
min ( )
,. .
Lfx
Ax bst
x
???
?? 0
或 min ( ),
. .
kTf x x
Ax bst
x
???
??
?
0
（ 13.5.3）
假设线性规划问题 (13.5.3)存在有限最优解 ky ， 我们下面分两种情形进行讨论 .
（ 1）如果 ( ) ( ) 0k T k kf x y x? ? ?，则 kx 也是 线性规划问题 (13.5.3)的最优解，此时 kx 为
原问题的 K-K-T 点；
（ 2）如果 ( ) ( ) 0k T k kf x y x? ? ?，由于 ky 是 线性规划问题 (13.5.3)的最优解，故有
( ) ( )k k kTTkf x y f x x? ? ?，
即有
( ) ( ) 0Tk k kf x y x? ? ?，
这表明 kky x? 是 ()fx在点 kx 处的下降方向 .
由于 ,kkx yD? 且可行域 D 为凸集，故 对任意 [0,1]?? ，有
(1 ) kkxy D????? ，
§ 13.5 Frank-Wolf 方法
最优化理论与方法 [乌力吉 ] 241
这表明 kky x? 又是问题 (13.5.1)的可行方向 ，从而 kky x? 是问题 (13.5.1)的可行下降方向 .
算法 13.6（广义既约梯度法）
步 1： 给定初始可行点 0x D? ，容许误差 0?? ，置 0k? ；
步 2： 求解线性规划问题 (13.5.3)，得到最优解 ky D? ；
步 3： 若 || ( ) ( ) ||k T k kf x y x ?? ? ?，则 算法结束，输出近似解 kx ；
步 4： 进行一维搜索，求解
01m in ( ( ))k k kf x y x? ??? ??
，
得最优步长 k? ；
步 5： 令 1 ( )k k k kkx xxy?? ??? ，置 1kk??，转步 2.
定理 13.5.1 设非线性规划问题 (13.5.1)的最优解存在，且对算法 13.6 产生的点列 {}kx ，
线性规划子问题 (13.5.3)的最优解总是存在的，则有
（ 1） 如果在某个迭代步 k ，有 ( ) ( ) 0k T k kf x y x? ? ?，则 kx 是原问题 (13.5.1)的 K-K-T
点 ；
（ 2） 如果 ( ) ( ) 0k T k kf x y x? ? ?对任意 k 都不成立， 则 算法 13.6 产生的点列 {}kx 的任
意聚点都是原问题 (13.5.1)的 K-K-T 点 .
证 （ 1）设 ( ) ( ) 0k T k kf x y x? ? ?，则 kx 也是 线性规划问题 (13.5.3)的最优解，从而满
足 子 问题 (13.5.3)的 K-K-T 条件，即 存在乘子 ,mn??????，满足
,
( ) ,
0.,,
kT
k
k T k
f x A
A
x
bx
x
??
??
? ?
??
?
? ? ??
??
???
0
0
00
（ 13.5.4）
但 (13.5.4)恰恰是原问题 (13.5.1)的 K-K-T 条件，故上式表明 kx 是原问题 (13.5.1)的 K-K-T 点 .
（ 2） 由于点列 {}ky 都是多面体集可行域 D 的极点，而点列 {}kx 包含在 D 的极点的凸
组合中，故它们都是有界点列 . 而 { } [0,1]k? ? 当然是一个有界数列 .
因此，存在自然数指标集 {1, 2, , , }K k? ?? 的无穷子集 1K 以及 ,, 1], [0 ,x x y D ???? ，
满足
1
lim kkKk xx??? ? ，
1
1lim k
kKk xx
???
? ??
，
1
lim kkKk yy??? ? ，
1
lim kkKk ????? ? .
由于 ky 是线性规划子问题 )in (m kT
Dx fx x? ?
的最优解，故对任意 x D? ，有
( ) ( )k T k T kf x x f x y? ? ? ，
（ 13.5.5）
且 有
( ) ( )k T k k T kf x x f x y? ? ?，
（ 13.5.6）
第十三章 可行方向法
242 最优化理论与方法 [乌力吉 ]
再由精确线搜 索准则 ，有
( ( ) ) ( ( ) )k k k k k kkf x y x f x y x??? ? ? ? ?，
（ 13.5.7）
以 及 迭代公式，有
1 ( )k k k kkx xxy?? ??? .
（ 13.5.8）
在不等式 (13.5.5)-(13.5.7)以及等式 (13.5.8)中令 k?? ( 1k K? )，我们得到
,
()
( ( ) ) ( ( ) ) ,
(
( ) ( )
( ) 0 ,
),
TT
T
x x y
x y x
f x y x f x y x
x x y x
f x f
f
??
?
? ? ? ?
?
? ? ?
? ?
??
?
?
? ?
?
?
?
?
? ?
（ 13.5.9）
由此不难看出，不等式组 (13.5.9)等价于
[ 0 ,1 ]
m in ( ) ( )
(
,
()
m in ( ( ) ) ( ( ) ) ,
) 0 ,
( ) .
TT
xD
T
x x y
x y x
f
f x f
f
x y x f x y x
x x y x
?
??
?
?
?
? ??
?
? ? ?
?
?
???
? ??
? ? ?
?
?
? ?
（ 13.5.10）
如果 ()( ) 0Txyf x???，则由（ 1）可知 x 是原问题 (13.5.1)的 K-K-T 点 . 故只须证明
()( ) 0Txyf x???即可 .
反证 . 假设 ()( ) 0Txyf x???， 这时 yx? 是目标函数 ()fx在点 x 处的下降方向，故
对于充分小的数 0?? ，有
( ( )) ( )f x y x f x?? ? ?，
由此，得
[ 0 ,1 ]( ) ( ( ) ) m i n ( ( ) ) ( )f x f x y x f x y x f x????? ? ? ? ? ? ??
.
（ 13.5.11）
由于到 {)( }kfx 是单调下降的有界数列，故 l )im (
k kfx??
存在，从而
1
li m ( li) ) ( )m(kkkKkk fxf x f x? ? ? ????和
1
11l i m ( l i )(m))(kk
kKkkf x f fxx
??? ? ? ?
??? ?
同时成立，即有
( ) ( )f x f x? ? ，
这与不等式 (13.5.11)矛盾，矛盾表明假设 ()( ) 0Txyf x???不成立，从而有
()( ) 0Txyf x???.
|
|
