, k 1 ）
（1）
同样由前一节共轭方向的基本定理有：
T gk di 0
（ i 0,
, k 1 ），（2）
T 再由 g i 与 d i 的关系得： gk gi 0 （ i
0,
i 0,
, k 1 ）
(3)
将（2）与（3）代入（1）得：当 而
i 0 , k 2 时，
第 2次迭代：
5 2 8 T ( 8 , 4 )T ( , ) 18 9 9
g1 (
8 2 16 2 ) ( ) || g1 || 9 9 4 . 0 || g 0 ||2 82 4 2 81
2
8 16 T , ) . ||g1 || 9 9
解：
4 1 f ( x) ( x1 , x2 ) 2 0
0 x1 , 2 x2
4 0 G . 0 2
f ( x) ( 4 x1 , 2 x2 )T .
第1 次迭代：
令
而
d (0) g0 f ( x(0) ) ( 8 , 4 )T ,

一、共轭梯度的构造 （算法设计针对凸二次函数） 设
f ( x)
1 T x Gx bT x c 2
其中 G 为 n n 正定矩阵，则
g ( x) Gx b
对二次函数总有 1）设
gk 1 gk G xk 1 xk k Gdk
，令 x1 x0 0 d0 （ 0 为精确步长因子）
dk 1 f ( xk 1 ) dk
|| f ( xk 1 ) ||2 || f ( xk ) ||2

令k=k+1;返回4.
例 用FR算法求解下述问题：
min
2 2 f ( x) 2x1 x2
初始点取为x(0) ( 2 , 2 )T , 0.001 。
1、选取初始数据，选取初始点
x0
，给定允许误差 0 ；
f ( x0 )
2、检查是否满足终止准则，计算
，若 || f ( x0 ) || ,迭代终
止，x 0为近似最优解，否则转向3；

3、 构造初始搜索方向，计算 d0 f ( x0 ), k 0 ； 4、进行一维搜索，求出 k 和 xk 1 ，使得
|| g k ||
，则停止计算，否则转步5；
T 2 5、检验下列条件是否成立： | gk 1gk | 0.2 || gk ||
k, t n -1
若两个条件都不成立，则转步7，否则转步6；
6、置t=k-1;
7、按以下公式计算
dk
：
dk gk k 1dk 1 k 1dt
T 在FR梯度法的步骤上增加一步即可，即：如果 dk 1 g k 1 0 ，令 x 0 x k
并转步1，否则转步3.
Beale三项共轭梯度法
算法思想:在再开始的时候，负梯度方向不一定最好，特别是频繁地采用 负梯度方向再开始时，算法效率会降低，而沿着原来的方向搜索往往效
果较好，所以，当需要在
4.2.27表示的是方向向量和梯度向量之间的惯性，这些子空间通常被 称作Krylow子空间。
再开始FR共轭梯度法

由于对于一般非二次函数，n步以后共轭梯度法产生的搜索方向 d k 不 再共轭，因此n步之后我们宜于周期性地采用最速下降方向作为搜索方 向，即令
这种开始的方法叫做再开始共轭梯度法。采用这种方法，所产生的 xk 1 总比 x 0 更加靠近 x * ，尤其当迭代从一个非二次区域进入 f ( x) ，可由 二次函数很好的近似的解的领域时，再开始方法能迅速收敛。 再开始共轭梯度法允许近似线性搜索过程，只是在采用近似线性搜索的 同时，要采取一定的检查措施，以保证所得到的搜索方向是下降方向。 事实上，由于

其中
T gk (g g ) k 1 T k k 1 d k 1 ( g k g k 1 )
0 T k 1 g k ( g t 1 g t ) d T (g g ) t t 1 t
（Crowder-Wolfe公式）
（4.2.19）
2)
（Fletcher-Reeves公式）
（4.2.20）
3）
T gk 1 ( g k 1 g k )（Polak-Ribiere-Polyak 公式） k T gk gk T gk 1 g k 1 k T dk gk
（4.2.21）
4） 一般地，在第 k 次迭代中，令
d k g k i di
适当选取
k 1 i 0
i ，使 d Gdi 0 （ i 0, , k 1）， 可得到
T k
T T gk Gdi gk (g g ) i T T i 1 i （ i 0, di Gdi di ( gi 1 gi )
§4.2 共轭梯度法
提纲

1、共轭梯度法---F-R共轭梯度法 2、共轭梯度法性质定理及例题 3、再开始FR共轭梯度法 4、Beale三项共轭梯度法 5、预条件共轭梯度法（了解）
共轭梯度法

在上一节中讨论了共轭方向法，其中n个共轭方向是预先设定好的。但是如何 让获取这些共轭方向并为提及。本节讨论一种重要的共轭方向法——共轭梯 度法。这种方法是将共轭性和最速下降方向相结合，利用已知迭代点处的梯 度方向构造一组共轭方向，并沿此方向进行搜索，求出函数的极小点。因在 迭代过程中通过对负梯度方向进行适当校正获得共轭方向，故而称之为共轭 梯度法。 共轭方向法基本原理告诉我们，共轭性和精确线性搜索产生二次终止性，共 轭梯度法实施的最速下降方向具有共轭性，从而提高算法的有效性和可靠性。
T T gk ( gk gk 1 ) gk gk k 1 T T dk 1 ( gk gk 1 ) gk 1 gk 1
共轭梯度法的迭代公式为：
k 为最佳步长因子） xk 1 xk k dk （ dk 为共轭方向，
对二次函数
T gk d k T k d k Gd k
m n
步迭代后终止。且对1 i
T
m
，下列关系式成立：
（4.2.23） （4.2.24） （4.2.25）
1）di
Gd j 0 （
2）gi
T
gj 0
（
j 0,1, , i 1） j 0,1, , i 1）
T T d g g i gi 3） i i
4） [ g0 , g1 ,
(
d (1) g1 0 d (0)
8 16 T 4 ( , ) ( 8 , 4 )T 9 9 81
40 ( 1, 4 )T 81
1
T g1 d (1)
d
(1) T
Gd (1)
9 20
40 8 16 1 ( , ) 81 9 9 4 4 0 1 40 2 ( ) ( 1, 4 ) 4 81 0 2

xk a j d k 处的计算值，其中
{a j } 是由步长算法产生的实验步长序列，如果
g k 1 d k 1 || g k 1 ||2 || d k 1 ||2
T




其中 是一个小正数，则步长因子 j 作为 k 。如果在任何试验中，
上述式子都不满足，则需要精确线性搜索产生步长因子 k 。 再开始FR共轭梯度法
x( 2) x(1) 1 d (1)
( 2 8 T 9 40 , ) ( 1, 4 )T 9 9 20 81
( 0 , 0 )T
g 2 ( 0 , 0 )T
x( 2)即为所求极小点。
定理4.3 对于正定二次函数，采用基于精确一维搜索的共轭梯度算法，必定经过
x0 为初始点。首先取 d0 g0
T d0 0 （精确一维搜索性质，见定理4.1.3）。 则有：g1
T 2）令 d1 g1 0 d0 ，适当选择 0 ，使 d1 Gd0 0 ，
T T T g1 Gd0 g1 ( g1 g0 ) g1 g1 得 0 T T T d0 Gd0 d0 ( g1 g0 ) g0 g0
T T gk k 1 gk dk 1可能大于0，这时 d k 将不是一个下降方向，我 的，并且 gk
们需要重置
d k 为 gk
。但是，如果频繁地利用最速下降方向作为搜索
方向，将大大削弱共轭梯度法的效率，而使得算法的形态变得更像最速 下降法。下面的检查措施可以克服这个困难。 设 g k 1 , d k 1 , k 分别表示 g k 1 , d k 1 , k 在点
, gi ] [ g0 , Gg0 , , di ] [ g0 , Gg0 ,
, Gi g0 ] , Gi g0 ]
（4.2.26 ） （4.2.27）
5） [d0 , d1 ,
其中，m是G的相异特征值的个数，4.2.23表示的是搜索方向的共轭性，
4.2.24表示的是梯度的直交性，4.2.25表示的是下降条件，4.2.26和
（从而得到 d1 ）
1 ，使得 3）再令 d2 g2 0d0 1d1 ，适当选择 0 ，
T d2 Gdi 0 （ i 0,1），
由此得：
T T g2 ( g2 g1 ) g2 g2 0 0 ， 1 T d1T ( g2 g1 ) g1 g1
而对非二次函数，则采用精确一维搜索得到 k
。
共轭方向的修正公式为：dk 1
k
gk 1 k dk
（4.2.18）
其中， 由下面诸式之一计算：