最优化理论与算法(第四章)

第四章 共轭梯度法

§ 共轭方向法

共轭方向法是无约束最优化问题的一类重要算法。它一方面克服了最速下降法中，迭代点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共轭方向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。

一、共轭方向

定义 设G是nn对称正定矩阵，d1，d2是n维非零向量，若

d1TGd20 （）

则称d1，d2是G－共轭的。类似地，设d1,,dm是Rn中一组非零向量。若

diTGdj0(ij) （）

则称向量组d1,,dm是G－共轭的。

注：(1) 当GI时，共轭性就变为正交性，故共轭是正交概念的推广。

(2) 若d1,

二、共轭方向法

共轭方向法就是按照一组彼此共轭方向依次搜索。 模式算法：

T1）给出初始点x0，计算g0g(x0)，计算d0，使d0g00，k:0 （初始共轭方向）；

,dmG－共轭，则它们必线性无关。

2）计算k和xk1，使得f(xkkdk)minf(xkdk)，令xk1xkkdk；

03）计算dk1，使dk1Gdj0，j0,1,

三、共轭方向法的基本定理

T,k，令k:k1，转2）。

共轭方向法最重要的性质就是：当算法用于正定二次函数时，可以在有限多次迭代后终止，得到最优解（当然要执行精确一维搜索）。 1

-

定理 对于正定二次函数，共轭方向法至多经过n步精确搜索终止；且对每个xi1，都是f(x)在线

i性流形xxx0jdj,j中的极小点。

j0证明：首先证明对所有的in1，都有

giT1dj0，j0,1,,i（即每个迭代点处的梯度与以前的搜索方向均正交）

事实上，由于目标函数是二次函数，因而有

gk1gkGxk1xkkGdk

1）当ji时， gdjgTi1Tj1djkj1igkik1gkdj

T gTj1djkj1dTkGdj0

2）当ji时，由精确搜索性质知：

giT1dj0

综上所述，有 gi1dj0 (j0,1,T,i)。

再证算法的有限终止结论。若有某个gi10（in1），则结论已知。若不然，那么由上面已证则必有： gndj0 (j0,而由于d0,T,n1)。

,dn1是Rn的一组基，由此可得gn0。故至多经过n次精确一维搜索即可获得最优解。

下面证明定理的后半部分。由于

f(x)1TxGxbTxc 2是正定二次函数，那么可以证明

(t0,,ti)f(x0tjdj)

j0i是线性流形上的凸函数。事实上，

(t0,,ti)f(x0tjdj)j0iiii1(x0tjdj)TG(x0tjdj)bT(x0tjdj)c2j0j0j0

2

-

i1i2T1TTtj(djGdj)[x0GdjbTdj]tj(x0Gx0bTx0c) 2j02j0由dTjGdj0(j0,,i)知(t0,min,ti)为t0,,ti的凸函数。因而

(t0,,ti)Ri1(t0,i,ti)0 (j0,tj,i)

f(x0注意到：当tjj，(j0,itdjj0j)Tdj0 (j0,,i)

,i)时，

ix0tjdjx0jdjxi1。

j0j0而由定理前部分证明，在xi1处有

f(xi1)TdjgiT1dj0(j0,故在(t0,,i)，

,ti)(0,,i)处，(t0,,ti)取得极小，即

xi1x0dij0ij是f(x)在线性流形上的极小点。

§ 共轭梯度法

上节一般地讨论了共轭方向法，在那里n个共轭方向是预先给定的，而如何获得这些共轭方向并为提及。本节讨论一种重要的共轭方向法——共轭梯度法。这种方法在迭代过程中通过对负梯度方向进行适当校正获得共轭方向，故而称之为共轭梯度法。

一、共轭梯度的构造 （算法设计针对凸二次函数）

设 f(x)其中G为nn正定矩阵，则

1TxGxbTxc 2g(x)Gxb。

对二次函数总有 gk1gkGxk1xkkGdk 3

-

1）设x0为初始点。首先取d0g0，令x1x00d0 （0为精确步长因子）

T则有：g1d00（精确一维搜索性质）。

T2）令d1g10d0，适当选择0，使d1Gd00，

TTTg1Gd0g1(g1g0)g1g得 0TTT1 （从而得到d1）

d0Gd0d0(g1g0)g0g0由前一节共轭方向法的基本定理有：

TTg2d10，g2d00，

再由d0与d1的构造，还可得：

TTg2g10，g2g00

T3）再令d2g20d01d1，适当选择0，1，使得d2Gdi0 （i0,1），由此得：

TTg2(g2g1)g2g00，1TT2

d1(g2g1)g1g1k1i04） 一般地，在第k次迭代中，令dkgkdiiT 适当选取i，使dkGdi0 （i0,， ,k1）

TTgkGdigk(gg)可得到 iTTi1i（i0,diGdidi(gi1gi),k1） （）

同样由前一节共轭方向的基本定理有：

Tgkdi0（i0,,k1）， （）

再由gi与di的关系得：

Tgkgi0 （i0,,k1） （）

将（）与（）代入（）得：当i0,,k2时，i0，

TTgk(gkgk1)gkg而 k1TTk。

dk1(gkgk1)gk1gk1共轭梯度法的迭代公式为：

xk1xkkdk（dk为共轭方向，k为最佳步长因子）

对二次函数 4

-

TgkdkTk；

dkGdk而对非二次函数，则采用精确一维搜索得到k。

共轭方向的修正公式为： dk1gk1kdk （） 其中，k由下面诸式之一计算：

Tgk1(gk1gk)1） kT （Crowder-Wolfe公式） （） dk(gk1gk)Tgk1gk12) kT （Fletcher-Reeves公式） （）

gkgkTgk(gk1gk)3） k1T （Polak-Ribiere-Polyak 公式） （）

gkgkTgk1gk14） kT （Dixon公式） （）

dkgk注： 对二次函数而言，上述四个公式都是等价的。而且求得的搜索方向均为共轭方向；若对非二次函数，则将导出互不相同的算法，而且据此求出的搜索方向不再保证是共轭的。（事实上，此时不存在一个常值正定矩阵G，共轭的提法都已无意义）。

二、共轭梯度法的性质

定理 对于正定二次函数，采用基于精确一维搜索的共轭梯度算法，必定经过mn步迭代后终止。且对1im，下列关系式成立：

1）diGdj0 （j0,1,2）gigj0 （j0,1,TT,i1） （） ,i1） （）

TT3）digigigi （）

4）[g0,g1,5）[d0,d1,,gi][g0,Gg0,,di][g0,Gg0,,Gig0] （） ,Gig0] （）

证明：先用归纳法证明（）～（）。对于i1，容易验证（），（），）成立。现假设这些关系式对某个im成立，下面证明对于i1，这些关系式仍然成立。事实上，对于二次函数，显然有 5

-

gi1giG(xi1xi)giiGdi （）

对上式左乘di，并注意到i是精确步长因子，得

TgiTdigiTgi iT0 （）

diGdidiTGdi利用（），（），得

giT1gjgiTgjidiTGgjgiTgjidiTG(djj1dj1) （）

当ji时，（）成为

giTgiTggjggiTdiGdi0

diGdiTi1Ti当ji时，由归纳法假设可知

giT1gjgiTgjidiTG(djj1dj1)0

于是（）得证。

再由共轭梯度法的迭代公式及（），有

diT1GdjgiT1GdjidiTGdjgiT1当ji时，由（），（）及（），（）成为

gjgj1jidiTGdj （）

giT1gi1TgiT1gi1TdGdiTdiGdiTdiGdi0

gigigigiTi1当ji时，直接由归纳法假设知（）为零，于是（）得证。

TTTT又由于 di1gi1gi1gi1idigi1gi1gi1

于是（）得证。

下面利用归纳法证明（）与（）。当i1时，由d0g0及g1g00Gd0g00Gg0，容易看出： [g0,g1][g0,Gg0]

再由 d0g0 及 d1g10d0g10g0，易见：

[d0,d1][g0,g1][g0,Gg0]。

故当i1时，（）与（）成立。假定（）与（）对i成立。下证结论对i1也成立。

6

-

由于 gi1giiGdi， 而从归纳法假设知 gi,di[g0,Gg0,故有 gi1[g0,Gg0,还可证明： gi1[g0,Gg0,否则由 gi1[d0,d1,,Gig0] ,Gi1g0] ,Gig0][d0,d1,,di]

,di]及giT1dj0 (j0,,i)（共轭方向法基本定理）

则必有 gi10（与算法结束前，不会出现gi10矛盾） 因此 [g0,g1,,gi1][g0,Gg0,,Gi1g0]

再由 di1gi1idi 立即有： [d0,定理证毕。

注：1）上面定理中出现的这些生成子空间通称为Krylov子空间；

2）在共轭梯度法中，dk1gk1kdk，若采用精确一维搜索，则k不论采用哪种公式计

TTTT算，都有gk1dk1gk1gk1kgk1dkgk1gk10，即dk1总是下降方向，若不采用

,di1][g0,g1,,gi1][g0,Gg0,,Gi1g0] 。

精确一维搜索，则就不一定了；

TT3）对Dixon公式，使用不精确搜索准则 gk1dkgkdk，(0,1)，能保证搜索方向总是

下降的。事实上，由

Tgk1gk1dk1gk1Tdk

dkgkTgk1dkggk11T，

gkdkTk1有 gTk1k1dTgkT1dkdk0）而 gdgdkgdgdkT， 1（由gkgkdkTk1kTkTk1kTkT由此即得 gk1dk10

故dk1为下降方向；

4）Fletcher－Reeves公式最为简洁，使用得最多； 7

-

5）共轭梯度算法用于非二次函数时，没有有限终止性质，一般经过n次搜索后，就取一次负梯度方向，称再开始。Polak-Ribiere-Polyak具有自动再开始的特点，事实上，当算法改进不大时，会出现gk1gk，这时用Polak-Ribiere-Polyak公式计算出的k0，从而导致dk1gk1。

§4. 3 共轭梯度法的收敛性

由前面的讨论已经知道，当共轭梯度算法用于正定二次函数时必定有限终止。本节研究将其用于一般非二次函数时的收敛性问题。

一、共轭梯度法的总体收敛性

定理 设水平集Lxf(x)f(x0)有界，f是Rn上具有一阶连续偏导数的凸函数。{xk}是由Fletcher-Reeves共轭梯度算法产生的迭代点列。则

1）{f(xk)} 为严格单调下降序列，且limf(xk)存在。

k2）{xk}的任意聚点都是最优解，于是：limf(xk)minf(x)。 nkxR证明：在算法迭代过程中，由于每隔n次采用一次再开始措施。因而搜索方向要么是共轭梯度方向，要么是最速下降方向。但不管是哪种情形都有：

Tgkdkgk20 （采用严格一维搜索）

*因而{f(xk)}单调下降，又由L有界，故{f(xk)}也有下界，因此limf(xk)存在，记为f。又由

k{f(xk)}单调下降，知{xk}L，故{xk}是有界序列。

设{xk}K1是{xk}中的这样的一个子列：从xk出发按最速下降方向gk得到xk1。由{xk}K1有界，故存在收敛子列{xk}K2，使limxkx。

kkK2*又{xk1}K2也是有界点列，故存在子列{xk1}K3，使limxk1x，且

kkK3f(x*)f(x)limf(xk)f* （*）

k下面用反证法证明f(x)0。若不然，设f(x)0，则对充分小的，有

**f(x*f(x*))f(x*)

注意当kK3时， f(xk1)f(xkkdk)f(xkkgk)f(xkgk) 0 8

-

令k，则有 f(x)f(xg)f(x)

*与（*）式矛盾，故必有f(x)0。再由f(x)是凸函数，即知x是最优解。因而有

*****minf(x)f(x)limf(xk) nxRkˆ。 ˆ，必存在{xk}的子列{xk}K0，使得limxkx进一步地，对点列{xk}的任一极限点xkkK0ˆ)f(limxk)limf(xk)f(x) 进而有 f(xkkK0k*ˆ也是问题的最优解。 这表明：x注：由这个定理的证明过程易见：上述收敛定理对其它几种共轭梯度算法也是成立的。

定理 假设水平集Lxf(x)f(x0)是有界集，f(x)在其上Lipschitz连续，则采用精确一维搜索的Crowder-Wolfe再开始共轭梯度法产生的点列{xk}至少存在一个聚点是驻点。 证明: 与前一定理的证明类似，略。

定理 （Polak-Ribbiere-Polyak算法的总体收敛性）设f(x)二阶连续可微，水平集

Lxf(x)f(x0)有界。又设存在常数m0，使得对xL，有：

myyT2f(x)y yRn

则采用精确一维搜索的P-R-P共轭梯度算法产生的点列{xk}收敛于f(x)的唯一极小点。

TgkdkT证明：只要证明cosk，即gkdkgkdk即可。事实上，若

gkdkTgkdkcosk （0）

gkdk2成立。由第二章的定理知，必有f(xk)0，若x是{xk}的极限点，由f(x)的连续性，则有

*f(x*)0，由f(x)的凸性，即知x*是极小点。

ˆ是{xk}的另一极限点，则再由f(x)在水平集L上一致凸，知{xk}的极限点必唯一。否则设xˆ)0。因此， 也有f(xˆ)T(f(x*)f(xˆ))(x*xˆ)T2f()(x*xˆ) 0(x*x这与一致凸的假设矛盾，所以{xk}只有唯一极限点。 9

-

可证：有界点列{xk}若只有唯一极限点x，则必有limxkx。故{xk}收敛于f(x)的唯一极小点。

k**T下证： gkdkgkdk （1）

由于采用了精确一维搜索，故有

Tgkdkgk

2因而（1）式等价于

gk （2） dkT由 gkdk1gk1dk1k1T10Tdk1G(xk1tk1dk1)dk1dt

Tgk1gkd得： k1T1k1T （3）

dk1Gk1dk1dk1Gk1dk12其中 Gk1G(x01k1tk1dk1)dt。

再注意到， gkgk1f(xk)f(xk1)G(x01k1tk1dk1)k1dk1dtk1Gk1dk1

TTgk(gkgk1)gkGk1dk1有 k1， k12Tgkggk11k1TgkGk1dk1Tdk1Gk1dk1由（3）得 k1gkGk1dk1mdk12

n又由L有界，故存在常数M0，使得 G(x)yMy，xL，yR 故 k1gkMdk1mdk12Mgk

mdk1因而 dkgk即

k1dk1gkMMgk(1)gk mmgkM(1)1 dkm由前述分析，定理得证。

上述总体收敛性定理均建立在精确一维搜索基础之上。Al-Baali（1985）研究了采用不精确一维搜索的Fletcher-Reeves共轭梯度法。发现若采用Wolfe-Powell不精确一维搜索准则，也有总体收敛性。

10

-

定理 若k由不精确一维搜索的Wolfe-Powell准则产生，那么Fletcher-Reeves共轭梯度算法具体下

T降性质：gkdk0。

证明：先用归纳法证明：

jj0kTgkdkgk22j （*）

j0k其中(0,)是W-P准则中的。

当k0时，（*）成为等式，故结论成立。假设对任何k0，（*）式成立，现考虑k1情形。 由

Tgk1dk112gk112Tgk1(gk1kdk)gk12221kTgk1dkTgk1dkgk12

TTgk1gk1gk1dkgkgk11gk2

TT及 gk1dkgkdk

TgkdkTgk1dk1Tgkdk有 1再由归纳法假设，有

gk2gk121gk2

11jjj0j0k1kTgkdkgkk2

k1j0Tgk1dk1gk1j21Tgkdkgk212j

jj0k1j0即 j0k1Tgk1dk1gk122j。

利用已经证明的（*）式，并注意到

jjj0j0kk1 11120 11有 2j2j0T最后得 gkdk0，证毕。

11

-

定理 设f(x)二阶连续可微，水平集LxRnf(x)f(x0)有界。设k由Wolfe-Powell准则确定，那么Fletcher-Reeves共轭梯度算法产生的点列总体收敛，即有

liminfgk0. （1）

k证明：由Wolfe-Powell准则，及定理中（*）式得

TTgkdk1gk1dk12gk1 122Tgkgkg又由 dkgkk1dk1， k1Tkgk1gk1gk1

得 dk2gk2T2k1gkdk1k21dk1

22gk递推可得 dk22gk112k21dk1()gk142k21dk1

221()gk1(gjj0k2) （2）

下面用反证法证明（1）成立。若不然，则存在常数0，使得对充分大的k，都有gk0。 由gk在水平集L上有界，从（2）即有

dk2c1k （c1为常数）

TTkgkgkdkgkdkgk12gkj(2)()由 cosk 2gkdkdk1dkgkdkj0gk1222cos()k1dkkk故级数

2212221()c2

1kc1kkkcosk2k发散。若设M为G(x)在L上的上界，

TT2则 gk1dkgkdkkMdk再由Wolfe-Powell准则

gk1dkgkdk （1）

TTT即 gkdkgk1dkgkdk

TT故有

TTT gkdkgk1dkgkdkkMdk212

-

因而有

k1Mdk2Tgkdk。

又由Wolfe-Powell准则

Tfk1fkkgkdk （2）

Tdk(1)gk fk1fk2Mdk(1)(1)222fkgkcos2kfkcosk MM2由（2）知{f(xk)}单调下降且有下界，故limf(xk)存在。再由

(1)M由此又推得

20 及

(1)M2cos2kfkfk1

cosk2k收敛，矛盾。从而定理结论成立。

13