数值最优化与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 .