共轭方向法

&3.6 共轭方向法

引言

本节之后的方法大多属于共轭方向法。

3.6.1 共轭方向的概念

若两个向量XRn，YRn，满足如下关系：

XTAY0 (3-6-1)

其中，A为nn的对称正定阵，则称X和Y是关于A共轭的，X和Y称之为共轭方向。

T注意：若XY0，则称X与Y正交。实际上，共轭是正交的推广。

211AS1S2111，，例1： 有两个二维向量12，判断S1与S2是否关于A共轭，

是否正交？

解：

TS1AS2121111021，因此，S1与S2关于A共轭。

S1TS211101，因此，S1与S2正交。

3.6.2 共轭向量的概念

如果有m个n维向量S1,S2,S3,...,Sm，满足

TSiASj0TSiASj0(ij),且A正定(ij) (3-6-2)

则称这m个向量是A的共轭向量。如果A维单位阵，则称这m个为正交向量。

3.6.3 共轭向量的几何意义

设目标函数为

1TXAXBTXC2 (3-6-3)

f(X)其中，A为nn阶的对称正定阵。f(X)的梯度为：

F(X)AXB (3-6-4)

设从某点X0出发，沿P0方向进行搜索得到f(X)的极小点X1，则有

F(X1)TP0(AX1B)TP00 (3-6-5)

'X0设从某点出发，仍沿P0方向进行搜索得到f(X)的极小点X2，则有

F(X2)TP0(AX2B)TP00 (3-6-6)

式(3-6-6)减(3-6-5)，可得：

(X2X1)TAP00 (3-6-7)

这说明(X2X1)与P0是关于A共轭的。

3.6.4 共轭方向法的原理

TSiASj0TSAS0考虑m个n维向量S1,S2,...,Sm，满足ij(ij),且A正定(ij)，则这m个向量一定

是线性无关的。用反证法。

假设S1,S2,...,Sm线性相关，则一定存在一组不全为0的一组数1,2,...,m，满足

1S12S2...mSm0 (3-6-8)

则有

SiTA(1S12S2...mSm)1SiTAS12SiTAS2...mSiTASm0 (3-6-8)

TSi1,2,...,mi其中，。因此有：ASi0，但这与原假设不符。因此，一定可以得出S1,S2,...,Sm线性无关的结论。

注意：在n维空间中的任意向量，均可以用n个线性无关的n维向量表示，也可以说，

n维是由n个线性无关的n维向量张成的（此处还差一步：正交化）。那么，设目标函数f(X)的极小点为X*，初始点为X0，S0,S2,...,Sn1为关于A的n个共轭向量，则有：

X*X00S01S1...n1Sn1 (3-6-9)

将式(3-6-9)写成差分格式：

Xk1XkX2X1XkkSkXk1k1Sk1X11S1X00S0 (3-6-10)

*XXk0,1,...,n1k1k1式中，，表示经过次迭代后，。该式表明，Xk1为目标函数

沿Sk方向的一个极小点，则有：

F(Xk1)TSkF(XkkSk)TSk0 (3-6-11)

即

[A(XkkSk)B]TSkTT(AXkB)TSkkSkASkF(Xk)TSkkSkASk0 (3-6-12)

即可推导出：

F(Xk)TSkkTSkAS (3-6-13)

式(3-6-13)表明，如果能够构造出一系列共轭向量Sk(k1,2,...,n1)，则可以求出k，那么经过k步迭代，可以求得Xk1。对于二次函数，kn。

22minf(X)x125x2

例2 求解

解：

首先，构造二次型：

f(x)1TXAXBTXC220x11x1x20X02050x2

2A0即050，B0，C0。

取X02,2，取第0个搜索方向为：

T2024100S0F(X0)(AX0B)0502，则根据式(3-6-13)，有：

F(X0)TS00TTS0AS04210004100T4100045010010016500032

2100164X1X00S02500032100

由于S1与S0关于A共轭，则有

TS1AS0TS12004050100

625S11，则 上式与无穷多解，我们任取

F(X1)TS11TTS1AS16252062510501

20625050X11T6250X2X11S1X1110 X2X*

3.6.5 构造共轭方向的一般方法

在n维空间中，已知有n个单位向量：

第i个分量为

ei[0,0,...,1,0,...,0]i1,2,...,n

则n个共轭方向可以这样确定：

S1e1[1,0,0,...,0]TS2e21S1e21e1 (3-6-14)

其中，1为待定系数。

由于，S2和S1关于A共轭，因此ST2AS10，即

(e21S1)TAS1(eT21S1T)AS10 可得

eT12AS1S1TAS1 继续，可以构造

S3e31S12S2 考虑S3TAS20，即

(e31S12S2)TAS20 由于S1TAS20，式(3-6-19)化简为：

(3-6-15)

(3-6-16)

(3-6-17)

(3-6-18)

(e32S2)TAS20 (3-6-19)

即可推出：

Te3AS22TS2AS2 (3-6-20)

TS3同时考虑AS10，即

(e31S12S2)TAS10 (3-6-21)

TS1同理，由于AS20，式(3-6-21)化简为：

(e31S1)TAS10 (3-6-22)

因此有

Te3AS1T1S1AS1 (3-6-23)

特别注意：由于S3不仅与S2关于A共轭，同时也与S1关于A共轭，所以1的表达式和在S2时的表达式(3-6-16)是不同的。由此可以类推，可得：

k1Skek1S12S2k1Sk1ekiSii1TeASikkiSiTASik2,3,...,n (3-6-24)

例题，见Matlab程序

3.6.6 共轭梯度法

共轭梯度法是一种构造共轭方向的方法。任取一个初始点，经过n次迭代，得到n个点，利用这n个点的梯度方向可以构造一组共轭方向。具体做法为：设有一个n维函数f(X)，用梯度法经过n1次迭代，即可以得到这n个迭代点X0,X1,X2,Xn1，这些点所对应的函数的梯度为g0,g1,g2gn1。即可以构造一组共轭方向：

S0g0k1SgiSi,kki0TgkASiTi,SiASik1,2,,n1 (3-6-25)

可以证明，按照式(3-6-25)构造的n个方向S0,S1,S2,Sn1是关于A共轭的。然后，即可按下式计算：

Xk1XkkSkTgkSkkSTASkk (3-6-26)

如果f(X)是二次函数，那么经过n次迭代后必然可以收敛到极小点。

如果按这样的算法计算，则一定需要求得函数的海赛矩阵A，在实用性上存在困难，并且加大了计算负担，因此我们需要想法避免在计算过程中出现A。现在我们对以上公式作一些适当的简化。

设有一个二次函数

f(X)1TXAXBTXC2，在进行极小化过程中，迭代公式为：

Xk1XkkSkkSkXk1Xk (3-6-27)

设gk为迭代点Xk的梯度，并且令：

ykgk1gk (3-6-28)

这是前后两相邻迭代点的梯度之差。则有：

ykAXk1BAXkBA(Xk1Xk)AkSkkASk (3-6-29)

对n个共轭方向

S1,S2,,Sn，有：

ST,2,,njASk0(jk)j,k1

故

TTkSTjASkSjkASkSjyk0 (3-6-30)

可见在迭代过程中，前后两次迭代点的梯度之差与其他任一共轭方向是正交的。即

Tyk1Sj0Tyk2Sj0yTS0j1j (3-6-31)

设kj，则：

TTTTTTTTTgkSjgkSjgk1Sjgk1Sjgk2Sjgk2Sjgk2Sjgj1Sjgj1SjTTTTTTT(gkgk1)Sj(gk1gk2)Sj(gj2gj1)Sj(gj1Sj)TTTTyk1Sjyk2Sjyj1Sjgj1Si(3-6-32)

又因为式(3-6-31)，故有

TgkSjgTj1Sj (3-6-33)

在此式中，

gj1是迭代点

Xj1处的梯度，而

Xj1是沿

Sj方向搜索新得之点。在梯度法中

我们已经证明了点

Xj1处的梯度方向与求得

Xj1点时的搜索方向是正交的，所以有：

gTj1Sj0 (3-6-34)

则有：

TgkSj0,j1,2,,k1 (3-6-35)

这就是说，某迭代点的梯度方向与此点以前各点的搜索方向均是正交的。

我们再回到构造n个共轭方向的问题上来。

S0g0S1g10S0k1已知式(3-6-25)：SkgkjSjj0

那么，对于第r次迭代（其中kr），则有

r1SrgrjSjj0 所以

r1rgrSrjSj0jSjjj0 此处r1。

将上式等号两边同时左乘gTk，得到

gTrkgrTr(gk)jSjj0 又因为j0,1,2,,r，而kr，所以在上面和式中每一项均为零，即rgTkjSj0j0 (3-6-36)

(3-6-37)

(3-6-38)

(3-6-39)

所以

Tgkgr0 (3-6-40)

根据式(3-6-28)，已知：

yjgj1gjjASj，所以

1

ASj(gj1gj)j 将式(3-6-41)等号两边同时左乘

gTk，得：

gT1kASj(gTgTkj1gkgj)j gTkgj10j0,1,2,,k2考虑当时，有gTkgj0

所以

gTkASj0 k1j根据式(3-6-25)，

SkgkjSjgTkASj0，且

jSTjASj

所以当jk1时，均有：

j0，仅当jk1时，k10。

(3-6-41)

(3-6-42)

(3-6-43)

所以有：

Skgkk1Sk1 (3-6-44)

再对此式作进一步的简化：

Sk1gk1k2Sk2Sk2gk2k3Sk3S1g10S0S0g0 代入上面(3-6-25)式，可得：

Skgk(k1gk1)(k1k2gk2)(k1k2k3gk3)k1k20g0 将式(3-6-46)两边分别左乘

(k1ASk1)T(gkgk1)T得：

(Tk1ASk1)SkgTgTTTkkgk1gkk1gkgk1k1gk1gk1TTk1k2gkgk2k1k2gk1gk2TTk10gkg0k10gk1g0 因为Sk1和Sk是A共轭方向

所以 (Tk1ASk1)TSkk1Sk1ASk0

(3-6-45)

(3-6-46)

(3-6-47)

Tgkgr0,r1,2,,k1由前已知

所以式(3-6-47)右边各项中除两项于是有：

TT(gkgk)和（k1gk－1gk1）不等于零外，其余均等于零，

TTgkgkk1gk1gk10 (3-6-48)

由此即可得到求k1的公式如下：

k1TgkgTkgk1gk1 (3-6-49)

此式中不含海塞矩阵A，因而免去了许多繁琐的计算，而且不用担心A的正定及非奇异问题，对初始点的选择无任何限值了。

从以上分析，我们得出了共轭梯度法的计算步骤及迭代公式如下：

1) 任选初始点X0，则：

X1X00S0XXS0111Xk1XkkSk (3-6-50)

2) 计算：

S0g0SgS1100Skgk1k1Sk1 (3-6-51)

其中，

k1TgkgTk,k1,2,n1gk1gk1。则可构造n个共轭方向S0,S2,Sn1。

3) 对于每个迭代点及每个共轭方向，求k，使f(XkkSk)min。

4）按收敛判断准则判断Xk1是否为极小点，若是，则可以停机，输出结果；若不是，则应继续进行，直到满足精度要求，求出极小值点为止。

对于n维二次函数，只用迭代n次，一定可以收敛到极小值点。若为非二次函数，则在迭代n次，得到Xn点后，不一定就是极小值点。若经过判断不是，就应令X0Xn,k0重新构造n个共轭方向，重复以上迭代过程。