《数值最优化方法》课程教学课件（讲稿，打印版）共轭梯度法

数值最优化与Matlab程序设计 第四章共轭梯度法 Back Close

1/24 JJ II J I Back Close ÍäÅ`zÜ Matlab ßSO 1oŸ
›F›{

前面介绍的最速下降法和牛顿法都具有其自身的局限性.本章将 要介绍的共轭梯度法是介于最速下降法与牛顿法之间的一种无约束 优化算法，它具有超线性收敛速度，而且算法结构简单，容易编程实现 此外，跟最速下降法相类似，共轭梯度法只用到了目标函数及其梯度 值，避免了二阶导数(Hsse阵)的计算，从而降低了计算量和存储量， 因此它是求解无约束优化问题的一种比较有效而实用的算法， §4.1共轭方向法 共轭方向法的基本思想是在求解维正定二次目标函数极小点 时产生一组共轭方向作为搜索方向，在精确线搜索条件下算法至多迭 代步即能求得极小点.经过适当的修正后共轭方向法可以推广到 求解一般非二次目标函数情形.下面先介绍共轭方向的概念 定义4.1设G是n阶对称正定矩阵，若n维向量组d1,d2,·,dm Back Close

2/24 JJ II J I Back Close c°0ÅÑe¸{⁄⁄Ó{—‰kŸg¤Å5. ŸÚ á0
›F›{¥0uÅÑe¸{Ü⁄Ó{Émò´Ã `zé{, ߉káÇ5¬ÒÑ›, Öé{({¸, N¥?ߢy. d , ãÅÑe¸{Éaq,
›F›{ê^ 8IºÍ9ŸF› ä, ;ù Í (Hesse ) Oé, l ¸$ Oé˛⁄;˛, œdߥ¶)ÃÂ`zØKò´'k ¢^é{. §4.1
›êï{
›êï{ƒgé¥3¶) n ë½g8IºÍ4: û)ò|
›êïäè|¢êï, 3°(Ç|¢^áeé{ñıS ì n ⁄=U¶4:. ²L·?￾
›êï{å±Ì2 ¶)òÑög8IºÍú/. e°k0
›êïVg. ½¬ 4.1  G ¥ n È°½› , e n ëï˛| d1, d2, · · · , dm

(m≤n)满足 dGd=0,i≠j, 则称d1,d2,·,dm是G共轭的. 显然，向量组的共轭是正交的推广，即当G=I(单位阵)时，上述 定义变成向量组正交的定义.此外，不难证明，对称正定矩阵G的共 轭向量组必然是线性无关的， 下面我们考虑求解正定二次目标函数极小点的共轭方向法.设 min f()-gG+ (4.1) 其中G是n阶对称正定阵，b为n维常向量，c为常数.我们有下面的 算法 算法4.1（共轭方向法 Back Close

3/24 JJ II J I Back Close (m ≤ n) ˜v d T i Gdj = 0, i 6= j, K° d1, d2, · · · , dm ¥ G
›. w, ï˛|
›¥Ì2, = G = I(¸† ) û, ˛„ ½¬C§ï˛|½¬. d , ÿJy², È°½› G 
›ï˛|7,¥Ç5Ã'. e°·Çƒ¶)½g8IºÍ4:
›êï{.  min f(x) = 1 2 x TGx + b T x + c, (4.1) Ÿ• G ¥ n È°½ , b è n ë~ï˛, c è~Í. ·Çke° é{: é{ 4.1 (
›êï{)

步0给定迭代精度0≤e《1和初始点0.计算90=Vf(x0): 选取初始方向d使得d6g0<0.令k:=0. 步1若‖g≤e,停算，输出x*≈xk. 步2利用精确线搜索方法确定搜索步长Q。 步3令ck+1:=xk+Qkdk,并计算gk+1=7f(xk+1) 步4选取d+1满足下降性和共轭性条件： d+19k+1<0,dg+1Gd:=0,i=0,1,.,. 步5令k=k+1,转步1. 下面给出算法4.1的收敛性定理 定理4.1设目标函数f由(4.1)定义.{xk}是算法4.1产生的 迭代序列.则每一步迭代点xk+1都是f(x)在x0和方向d0,d1,·,d以 Back Close

4/24 JJ II J I Back Close ⁄ 0 â½Sì°› 0 ≤ ε  1 ⁄–©: x0. Oé g0 = ∇f(x0). ¿–©êï d0 ¶ d T 0 g0 < 0. - k := 0. ⁄ 1 e kgkk ≤ ε, é, —— x ∗ ≈ xk. ⁄ 2 |^°(Ç|¢ê{(½|¢⁄ αk. ⁄ 3 - xk+1 := xk + αkdk, øOé gk+1 = ∇f(xk+1). ⁄ 4 ¿ dk+1 ˜ve¸5⁄
›5^á: d T k+1gk+1 < 0, dT k+1Gdi = 0, i = 0, 1, · · · , k. ⁄ 5 - k := k + 1, =⁄ 1. e°â—é{ 4.1 ¬Ò5½n. ½n 4.1 8IºÍ f d (4.1) ½¬. {xk} ¥é{ 4.1 ) SìS. Kzò⁄Sì: xk+1 —¥ f(x) 3 x0 ⁄êï d0, d1, · · · , dk

所张成的线性流形 &={l=o+∑ada} 中的极小点.特别，xm=x*=-G-1b是问题(4.1)的唯一极小点。 证由算法4.1可知，d0,d山1，·，dn-1是G共轭的，因而是线性无 关的，故有Sm-1=R”.于是我们只需证明xk+1是f在线性流形Sk 中的极小点即可. 显然有 ck+1=k+a4d=.=0+a,d,∈Sk. i=0 另一方面，对任何x∈Sk,存在B:∈R,i=0,1,·,k,使得 k =x0十 3,d. Back i=0 Close

5/24 JJ II J I Back Close §‹§Ç56/ Sk =  x   x = x0 + X k i=0 αidi , ∀αi  •4:. AO, xn = x ∗ = −G−1 b ¥ØK (4.1) çò4:. y dé{ 4.1 å, d0, d1, · · · , dn−1 ¥ G
›, œ ¥Ç5à ', k Sn−1 = R n . u¥·ÇêIy² xk+1 ¥ f 3Ç56/ Sk •4:=å. w,k xk+1 = xk + αkdk = · · · = x0 + X k i=0 αidi ∈ Sk. ,òê°, È?¤ x ∈ Sk, 3 βi ∈ R, i = 0, 1, · · · , k, ¶ x = x0 + X k i=0 βidi .

记 k hk+1=x-xk+1=(8:-ad. i=0 利用泰勒展开公式，有 f(a)fCh ≥fk+1+9+1hk+1 = fk+1+∑(B-a)g+1d. =0 下面只需证明 g呢+1d=0,i=0,1,.,k (4.2) 即可.事实上，因 Back 9j+1-9j=G(xj+1-xj)=ajGdj, Close

6/24 JJ II J I Back Close P hk+1 = x − xk+1 = X k i=0 (βi − αi)di . |^V–m˙™, k f(x) = fk+1 + g T k+1hk+1 + 1 2 h T k+1Ghk+1 ≥ fk+1 + g T k+1hk+1 = fk+1 + X k i=0 (βi − αi)g T k+1di . e°êIy² g T k+1di = 0, ∀ i = 0, 1, · · · , k (4.2) =å. Ø¢˛, œ gj+1 − gj = G(xj+1 − xj) = αjGdj

故当iGd:=0, j=+1 其中上式的第一项与求和项为0分别由精确线搜索和共轭性得到.当 i=k直接由精确线搜索可得91d,=0.从而(4.2)式成立.至此，定 理的结论已经得到证明 注从定理41可知，在精确线搜索下，用算法4.1求解正定二次 目标函数极小化问题(41)，至多在步内即可求得其唯一的极小点 这种能在有限步内求得二次函数极小点的性质通常称为二次终止性， Back Close

7/24 JJ II J I Back Close  i < k ûk g T k+1di = g T i+1di + X k j=i+1 (gj+1 − gj) T di = g T i+1di + X k j=i+1 αjd T j Gdi = 0, Ÿ•˛™1òëܶ⁄ëè 0 ©Od°(Ç|¢⁄
›5.  i = k Üd°(Ç|¢å g T k+1dk = 0. l (4.2) ™§·. ñd, ½ n(ÿƲy². 5 l½n 4.1 å, 3°(Ç|¢e, ^é{ 4.1 ¶)½g 8IºÍ4zØK (4.1), ñı3 n ⁄S=嶟çò4:. ˘´U3kÅ⁄S¶gºÍ4:5üœ~°èg™é5.

§4.2共轭梯度法 共轭梯度法是在每一迭代步利用当前点处的最速下降方向来生 成关于凸二次函数f的Hesee阵G的共轭方向，并建立求f在Rm上 的极小点的方法.这一方法最早是由Hesteness和Stiefel于l952年为 求解对称正定线性方程组而提出来的，后经Fletcher等人研究并应用 于无约束优化问题取得了丰富的成果，共轭梯度法也因此成为当前求 解无约束优化问题的重要算法类 设函数f由(4.1)所定义，则f的梯度和Hesse阵分别为 g(x)=Vf(x)=Gx+b,G(x)=V2f(x)-G. (4.3) 下面我们来讨论算法4.1中共轭方向的构造.我们取初始方向d,为初 始点xo处的负梯度方向，即 do=-7f(co)=-90 Back (4.4 Close

8/24 JJ II J I Back Close §4.2
›F›{
›F›{¥3zòSì⁄|^c:?ÅÑe¸êï5) §'u‡gºÍ f  Hesee G 
›êï, øÔ·¶ f 3 R n ˛ 4:ê{. ˘òê{Å@¥d Hesteness ⁄ Stiefel u 1952 cè ¶)È°½Ç5êß| J—5, ￾² Fletcher <ÔƒøA^ uÃÂ`zØK ¥L§J,
›F›{èœd§èc¶ )ÃÂ`zØK­áé{a. ºÍ f d (4.1) §½¬, K f F›⁄ Hesse ©Oè g(x) = ∇f(x) = Gx + b, G(x) = ∇2 f(x) = G. (4.3) e°·Ç5?ÿé{ 4.1 •
›êïE. ·Ç–©êï d0 è– ©: x0 ?KF›êï, = d0 = −∇f(x0) = −g0. (4.4)

从xo出发沿d0方向进行精确线搜索得求步长ao,令 x1=c0+Q0d0, 其中Q0满足条件 Vf(x1)do gf do=0. (4.5) 在x1处，用f在1的负梯度方向一g1与d的组合来生成d,即 d1=-91+Bod0, (4.6) 然后选取系数B使d1与d,关于G共轭，即令 dfGdo=0 (4.7） 来确定B.将(4.6)代入(4.7)得 6= gGdo dGdo (4.8) Back Close

9/24 JJ II J I Back Close l x0 —u˜ d0 êï?1°(Ç|¢¶⁄ α0, - x1 = x0 + α0d0, Ÿ• α0 ˜v^á ∇f(x1) T d0 = g T 1 d0 = 0. (4.5) 3 x1 ?, ^ f 3 x1 KF›êï −g1 Ü d0 |‹5)§ d1, = d1 = −g1 + β0d0, (4.6) ,￾¿XÍ β0 ¶ d1 Ü d0 'u G
›, =- d T 1 Gd0 = 0 (4.7) 5(½ β0. Ú (4.6) ì\ (4.7)  β0 = g T 1 Gd0 d T 0 Gd0 . (4.8)

由(4.3)得 91-90=G(x1-x0）=a0Gdo. (4.9) 另外，由定理4.1可知g5d=0(i=0,1).故由(4.4)~(4.6)可得 g590=0,g5g1=0,d690=-g690,dg1=-99m. 现假设已得到相互共轭的搜索方向d0,d1,·,d-1,精确线搜索 得到的步长为Q0,a1,·,Q-1,且满足 d-1Gd=0,i=0,1,.,k-2, d9=-gg,i=0,1,.,k-1, (4.10) g9=0,gd=0,i=0,1,.,k-1. 现令 k-2 4=-+-d-1+∑99d, (4.11) Back i=0 Close

10/24 JJ II J I Back Close d (4.3)  g1 − g0 = G(x1 − x0) = α0Gd0. (4.9) , , d½n 4.1 å g T 2 di = 0 (i = 0, 1). d (4.4)∼(4.6) å g T 2 g0 = 0, gT 2 g1 = 0, dT 0 g0 = −g T 0 g0, dT 1 g1 = −g T 1 g1. ybÆÉp
›|¢êï d0, d1, · · · , dk−1, °(Ç|¢ ⁄è α0, α1, · · · , αk−1, Ö˜v    d T k−1Gdi = 0, i = 0, 1, · · · , k − 2, d T i gi = −g T i gi , i = 0, 1, · · · , k − 1, g T k gi = 0, gT k di = 0, i = 0, 1, · · · , k − 1. (4.10) y- dk = −gk + βk−1dk−1 + X k−2 i=0 β (i) k di , (4.11)