共轭方向法

&3共轭方向法 引言

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

若两个向量n R X ∈，n R Y ∈，满足如下关系： 0=AY X T (3-6-1)

其中，A 为n n ?的对称正定阵，则称X 和Y 是关于A 共轭的，X 和Y 称之为共轭方向。注意：若0=Y X T ，则称X 与Y 正交。实际上，共轭是正交的推广。

例1： 有两个二维向量=111S ，?? -=112S ，?? =2112

A ，判断1S 与2S 是否关于A 共轭，是否正交？ 解： []011211211 21=??

-=AS S T

，因此，1S 与2S 关于A 共轭。 []01111 2 1=?? -?=S S T

，因此，1S 与2S 正交。 3.6.2 共轭向量的概念

如果有m 个n 维向量m S S S S ,...,,,321，满足

正定且A j i AS S j i AS S j T i j T i ,) (0 )

(0=≠≠= (3-6-2) 则称这m 个向量是A 的共轭向量。如果A 维单位阵，则称这m 个为正交向量。

3.6.3 共轭向量的几何意义 设目标函数为

C X B AX X X f T T ++=2 1 )( (3-6-3)

其中，A 为n n ?阶的对称正定阵。)(X f 的梯度为： B AX X F +=?)( (3-6-4)

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

0)()(0101=+=?P B AX P X F T T (3-6-5) 设从某点'

0X 出发，仍沿0P 方向进行搜索得到)(X f 的极小点2X ，则有 0)()(0202=+=?P B AX P X F T T (3-6-6) 式(3-6-6)减(3-6-5)，可得： 0)(012=-AP X X T (3-6-7)

这说明)(12X X -与0P 是关于A 共轭的。 3.6.4 共轭方向法的原理

考虑m 个n 维向量m S S S ,...,,21，满足正定且A j i AS S j i AS S j T

i j T i ,) (0 ) (0

=≠≠=，则这m 个向量一定是线性无关的。用反证法。

假设m S S S ,...,,21线性相关，则一定存在一组不全为0的一组数m ααα,...,,21，满足

0...2211=+++m m S S S ααα (3-6-8) 则有

...)...(22112211=+++= +++m

T i m T i T i m m T i AS S AS S AS S S S S A S αααααα (3-6-8) 其中，m i ,...,2,1=。因此有：0=i T i AS S ，但这与原假设不符。因此，一定可以得出m S S S ,...,,21线性无关的结论。

注意：在n 维空间中的任意向量，均可以用n 个线性无关的n 维向量表示，也可以说，n 维是由n 个线性无关的n 维向量张成的（此处还差一步：正交化）。那么，设目标函数)(X f 的极小点为*X ，初始点为0X ，120,...,,-n S S S 为关于A 的n 个共轭向量，则有：

1111000*...--+++=-n n S S S X X ααα (3-6-9) 将式(3-6-9)写成差分格式： += +=+= +=---+0 00111121

111S X X S X X S X X S X X k k k k k k k k αααα (3-6-10) 式中，1,...,1,0-=n k ，表示经过1+k 次迭代后，*1X X k →+。该式表明，1

+k X 为目标函数沿k S 方向的一个极小点，则有： 0)()(1=+?=?+k T k k k k T k S S X F S X F α (3-6-11) 即

)()(])([=+?=++= ++k T k k k T

k k T k k k T

k k T k k k AS S S X F AS S S B AX S B S X A ααα (3-6-12) 即可推导出： AS S S X F T k k

T k k )(?-=α (3-6-13) 式(3-6-13)表明，如果能够构造出一系列共轭向量)1,...,2,1(-=n k S k ，则可以求出k α，那么经过k 步迭代，可以求得1+k X 。对于二次函数，n k =。

例2 求解 2

22125)(min x x X f += 解：

首先，构造二次型： []005000221 2

1)(2121+?+?? =++=

X x x x x C X B AX X x f T T 即?? =50002 A ，0= B ，0= C 。 取[]T

X 2,20=，取第0个搜索方向为： =+-=-?=)()(000B AX X F S ??

-=-10042250002，则根据式(3-6-13)，有： 500032 10016 100450002

100410041004)(000 00= -

-???? ????????-?? -=?-=T T T

T AS S S X F α -+

=+=100450003210016

220001S X X α 由于1S 与0S 关于A 共轭，则有01004500 02 10 1=?? -- =

T T S AS S 上式与无穷多解，我们任取?

-=16251S ，则

--

--??????-????

-=?-

=1625500021625162550002)(111111T

T

T T X AS S S X F α =???? ???????

-+=+=001625111112ααX S X X *2X X → 3.6.5 构造共轭方向的一般方法

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

i e i ,...,2,1]0,...,0,1,...,0,0[== 则n 个共轭方向可以这样确定： 1

12112211]0,...,0,0,1[e e S e S e S T ββ+=+=== (3-6-14) 其中，1β为待定系数。

由于，2S 和1S 关于A 共轭，因此012 =AS S T

，即 0)()(11121112=+=+AS S e AS S e T T T ββ (3-6-15) 可得 1

1121AS S AS e T T -=β (3-6-16) 继续，可以构造

221133S S e S ββ++= (3-6-17) 考虑023=AS S T ，即

0)(222113=++AS S S e T ββ (3-6-18) 由于021=AS S T ，式(3-6-19)化简为： 0)(2223=+AS S e T β (3-6-19) 即可推出： 2

22

32AS S AS e T T -=β (3-6-20) 同时考虑013 =AS S T

，即 0)(122113=++AS S S e T ββ (3-6-21) 同理，由于021 =AS S T

，式(3-6-21)化简为： 0)(1113=+AS S e T β (3-6-22) 因此有 1

1131AS S AS e T T -=β (3-6-23)

特别注意：由于3S 不仅与2S 关于A 共轭，同时也与1S 关于A 共轭，所以1

β的表达式和在2S 时的表达式(3-6-16)是不同的。由此可以类推，可得：

n k AS S AS e S e S S S e S i T i i T k k i k i i

i k k k k k ,...,3,21 1112211=

-=+=++++=∑-=--βββββ (3-6-24) 例题，见Matlab 程序 3.6.6 共轭梯度法

共轭梯度法是一种构造共轭方向的方法。任取一个初始点，经过n 次迭代，得到n 个点，利用这n 个点的梯度方向可以构造一组共轭方

向。具体做法为：设有一个n 维函数)(X f ，用梯度法经过1-n 次迭代，即可以得到这n 个迭代点

1210,,,-n X X X X ，这些点所对应的函数的梯度为1210,,-n g g g g 。即可以构造一

组共轭方向：

-==∑+-=-=-=1 ,,2,1,

,1000n k AS S AS g S g S g S i T i i T

k i k i i i k k ββ (3-6-25)

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

-=+=+k T k k T k k k k k k AS

S S g S X X αα1 (3-6-26) 如果)(X f 是二次函数，那么经过n 次迭代后必然可以收敛到极小点。 如果按这样的算法计算，则一定需要求得函数的海赛矩阵A ，在实用性上存

在困难，并且加大了计算负担，因此我们需要想法避免在计算过程中出现A 。现在我们对以上公式作一些适当的简化。

设有一个二次函数C X B AX X X f T T ++=2 1

)(，在进行极小化过程中，迭代 公式为：

-=+=++k k k k k

k k k X X S S X X 11αα (3-6-27) 设k g 为迭代点k X 的梯度，并且令：

k k k g g y -=+1 (3-6-28)

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

k k k k k k k k AS S A X X A B

AX B AX y αα==-=--+=++)(11 (3-6-29)

对n 个共轭方向n S S S ,,,21 ，有：n k j k j AS S k T j ,,2,1,)(0 =≠= 故

0===k T

j k k T j k T j k y S AS S AS S αα (3-6-30)

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

的。即

===+--00 0121j T j j T k j T k S y S y S y

(3-6-31) 设j k >，则： i

T j j T j j T k j T k j T j j T j T j j T k T k j T k T k j

T j j T j j T k j T k j T k j T k j T k j T k j T k S g S y S y S y S g S g g S g g S g g S g S g S g S g S g S g S g S g S g 11211122111122211)()()()(++--+++-+-++-----++++=+-++-+-=+--++-+-= (3-6-32)

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

k S g S g 1+= (3-6-33)

在此式中，1+j g 是迭代点1+j X 处的梯度，而1+j X 是沿j S 方向搜索新得之点。在梯度法中我们已经证明了点1+j X 处的梯度方向与求得1+j X 点时的搜索方向是正交的，所以有：

01=+j T j S g (3-6-34) 则有：

1,,2,1,0-==k j S g j T k (3-6-35)

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

我们再回到构造n 个共轭方向的问题上来。 已知式(3-6-25)：

+-=+-=-=∑-=1 000110

0k j j j k k S g S S g S g S ββ

那么，对于第r 次迭代（其中r k >），则有 ∑-=+-=1

0r j j j r r S g S β (3-6-36) 所以 j r j r

j j j j r r S S S g ∑∑-===+-=1 ββ (3-6-37) 此处1-=r β。

将上式等号两边同时左乘T k g ，得到 ∑==r j j j T r k r T k

S g g g 0

)(β (3-6-38) 又因为r j ,,2,1,0 =，而r k >，所以在上面和式中每一项均为零，即

00 =∑=j r j j T k S g β (3-6-39) 所以

0=r T k g g (3-6-40)

根据式(3-6-28)，已知：j j j j j AS g g y α=-=+1，所以 )(1 1j j j j g g AS -= +α (3-6-41)

将式(3-6-41)等号两边同时左乘T k g ，得： )(1 1j T k j T k j j T

k g g g g AS g -= +α (3-6-42)

考虑当2,,2,1,0-=k j 时，有==+0 1j T k j T k g g g g 所以

0=j T k AS g (3-6-43)

根据式(3-6-25)， j k j j k k S g S ∑-=+-=1 β，且j T j

j T

k j AS S AS g = β

所以当1-≠k j 时，均有：0=j β，仅当时1-=k j ，01≠-k β。 所以有：

11--+-=k k k k S g S β (3-6-44) 再对此式作进一步的简化：

-=+-=+-=+-=--------0 00

01133222211g S S

g S S g S S g S k k k k k k k k βββ (3-6-45)

代入上面(3-6-25)式，可得： () 0021332

122111)()()(g g g g g S k k k k k k k k k k k k k βββββββββ ---------------= (3-6-46)

将式(3-6-46)两边分别左乘T k k T k k g g AS )()(111----=α得： 10100121 212211

1111111)(g g g g g g g g g g g g g g g g S AS T k k T k k k T k k k k T k k k k T

k k k T k k k T k k T k k

T k k ------------------+--+-+-+-=ββββββββββα (3-6-47)

因为1-k S 和k S 是A 共轭方向 所以 0)(1111==----k T

k k k T k k AS S S AS αα 由前已知1,,2,1,0-==k r g g r T k 所以式(3-6-47)右边各项中除两项） 和（－111)(---k T

k k k T k g g g g β不等于零外，其余均等于零，于是有： 0111=+----k T

k k k T k g g g g β (3-6-48) 由此即可得到求1-k β的公式如下： 1 11

---=k T k k T k k g g g

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

从以上分析，我们得出了共轭梯度法的计算步骤及迭代公式如下： 1) 任选初始点0X ，则：

+=+=+=+k

k k k S X X S X X S X X ααα11 1100001 (3-6-50) 2) 计算：

+-=+-=-=---1 110 0110

0k k k k S g S S g S g S ββ (3-6-51) 其中， 1,2,1,1

11-==---n k g g g g k T k k T

k k β。则可构造n 个共轭方向120,,-n S S S 。 3) 对于每个迭代点及每个共轭方向，求k α，使min )(→+k k k S X f α。 4）按收敛判断准则判断1+k X 是否为极小点，若是，则可以停机，输出结果；若不是，则应继续进行，直到满足精度要求，求出极小值点为止。

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