共軛梯度法(2學(xué)時(shí))(OK課件

1、n4.1 非線性規(guī)劃數(shù)學(xué)模型非線性規(guī)劃數(shù)學(xué)模型n4.2 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃n4.3 一維搜索一維搜索n4.4 無約束優(yōu)化問題的解法無約束優(yōu)化問題的解法第四章第四章 無約束最優(yōu)化問題無約束最優(yōu)化問題第四節(jié)第四節(jié) 無約束優(yōu)化問題的解法無約束優(yōu)化問題的解法n最速下降法最速下降法nNewton法法n擬擬Newton法法n共軛梯度法共軛梯度法 第四章第四章 無約束最優(yōu)化問題無約束最優(yōu)化問題四四. .共軛梯度法共軛梯度法n共軛方向及其性質(zhì)共軛方向及其性質(zhì)n二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理n二次函數(shù)共軛梯度法的迭代步驟二次函數(shù)共軛梯度法的迭代步驟n一般函數(shù)的共軛梯度法一般函

2、數(shù)的共軛梯度法nPRP算法的迭代步驟算法的迭代步驟n共軛梯度法的注釋共軛梯度法的注釋 )(minXfnRX )(NP無約束問題無約束問題4-4則向量組則向量組 正交。正交。1.1.共軛方向及其性質(zhì)共軛方向及其性質(zhì)定義定義4-134-13 jijiQppjTi00)()()(, 2 , 1,nmmji (424) (1)(2)(),mnpppR 設(shè)設(shè)Q是是n階對稱正定矩陣，若向量組階對稱正定矩陣，若向量組滿足：滿足：則稱該向量組則稱該向量組Q共軛共軛(Q正交正交)。當(dāng)當(dāng) Q = E ,(4-24)就是通常的正交條件就是通常的正交條件:( )()00i Tjijppij ,1,2,i jm (1)

3、(2)(),mppp無約束問題無約束問題4-4解解 。經(jīng)經(jīng)n次一維搜索收斂于次一維搜索收斂于 的最優(yōu)的最優(yōu)任意一點(diǎn)任意一點(diǎn)X(1)出發(fā)出發(fā), ,依次以依次以 為搜索方向的為搜索方向的1.1.共軛方向及其性質(zhì)共軛方向及其性質(zhì)定理定理4-144-14)()(min)()()()(0kkkkkpXfpXf )()()1(kkkkpXX cXbQXXXfTTRXn 21)(min分析：分析：)1(p)2(p)3(p)(np)1(X)2(X)3(X)(nX )1(nX X共軛方向法具有共軛方向法具有二次終止性二次終止性.設(shè)設(shè) 對于對稱正定矩陣對于對稱正定矩陣Q共軛，則從共軛，則從(1)(2)(),npp

4、p(1)(2)( ),nppp X下述算法：下述算法：結(jié)論：結(jié)論：1k 2k kn 無約束問題無約束問題4-4解解 。經(jīng)經(jīng)n次一維搜索收斂于次一維搜索收斂于 的最優(yōu)的最優(yōu)任意一點(diǎn)任意一點(diǎn)X(1)出發(fā)出發(fā), ,依次以依次以 為搜索方向的為搜索方向的1.1.共軛方向及其性質(zhì)共軛方向及其性質(zhì)定理定理4-144-14)()(min)()()()(0kkkkkpXfpXf )()()1(kkkkpXX cXbQXXXfTTRXn 21)(min)1(p)2(p)3(p)1(X)2(X)3(X設(shè)設(shè) 對于對稱正定矩陣對于對稱正定矩陣Q共軛，則從共軛，則從(1)(2)(),nppp(1)(2)( ),nppp

5、 X下述算法：下述算法：推論：推論：)1( kX)1( kg)(kp)(kX則則 g g(k+1)與與 的任意線性組合都正交。的任意線性組合都正交。(1)(2)(),kppp無約束問題無約束問題4-4)()2(2)1(1kkppp 四四. .共軛梯度法共軛梯度法n共軛方向及其性質(zhì)共軛方向及其性質(zhì)n二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理n二次函數(shù)共軛梯度法的迭代步驟二次函數(shù)共軛梯度法的迭代步驟n一般函數(shù)的共軛梯度法一般函數(shù)的共軛梯度法nPRP算法的迭代步驟算法的迭代步驟n共軛梯度法的注釋共軛梯度法的注釋 )(minXfnRX )(NP無約束問題無約束問題4-42.2.二次函數(shù)共

6、軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理)1(X) 1 () 1 (gp )1(1)1()2(pXX )2(X) 1 (1) 2() 2(pgp :1 確確定定)1()1(1)1()2()1()2(QppQpgQppTTT 0 )1()1()1()2(1QppQpgTT )1()1()1()2(1QppQpgTT )2(2)2()3(pXX 求求 的最優(yōu)解的最優(yōu)解X *。Q是對稱正定矩陣。是對稱正定矩陣。 1min ()2nTTX Rf XX QXb Xc 無約束問題無約束問題4-42.2.二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理)1(X) 1 () 1 (gp )1(1

7、)1()2(pXX )2(X) 1 (1) 2() 2(pgp )1()1()1()2(1QppQpgTT )2(2)2()3(pXX )3(X) 2(2) 3() 3(pgp :2 確確定定)2()2(2)2()3()2()3(QppQpgQppTTT 0 )2()2()2()3(2QppQpgTT 求求 的最優(yōu)解的最優(yōu)解X *。Q是對稱正定矩陣。是對稱正定矩陣。 1min ()2nTTX Rf XX QXb Xc 無約束問題無約束問題4-42.2.二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理)1(X) 1 () 1 (gp )1(1)1()2(pXX )2(X) 1 (1) 2

8、() 2(pgp )1()1()1()2(1QppQpgTT )2(2)2()3(pXX )3(X) 2(2) 3() 3(pgp )2()2()2()3(2QppQpgTT )3(3)3()4(pXX 求求 的最優(yōu)解的最優(yōu)解X *。Q是對稱正定矩陣。是對稱正定矩陣。 1min ()2nTTX Rf XX QXb Xc 已知已知 p(3)與與p(2), p(2)與與p(1)都都Q共軛共軛, , p(3)與與p(1)是否是否Q共軛共軛? ?無約束問題無約束問題4-42.2.二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理) 1 () 1 (gp )2(2)3()3(pgp )1(1)2(

9、)2(pgp )1()2(2)1()3()1()3(QppQpgQppTTT )1()3(QpgT 證明：證明： p(3)與與p(1)是否是否Q共軛共軛無約束問題無約束問題4-42.2.二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理cXbQXXXfTT 21)()()g Xf XQXb bQXgkk )()(bQXgkk )1()1(bpXQkkk )()()( )()(kkkQpg )(1)()1()(kkkkggQp )(1)1()2(1)1(ggQp 無約束問題無約束問題4-42.2.二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理) 1() 1(gp )2(2)3()

10、3(pgp ) 1 (1) 2() 2(pgp )1()2(2)1()3()1()3(QppQpgQppTTT )1()3(QpgT )(1)1()2()3(1gggT )(1)1()2(1)1(ggQp )(1)1()3()2()3(1ggggTT 證明：證明： p(3)與與p(1)是否是否Q共軛共軛因?yàn)橐驗(yàn)間(1)與與g(2)都是都是p(1), ,p(2)的線性組合的線性組合, ,由定理由定理4-14推論，推論，無約束問題無約束問題4-4解解 。經(jīng)經(jīng)n次一維搜索收斂于次一維搜索收斂于 的最優(yōu)的最優(yōu)任意一點(diǎn)任意一點(diǎn)X(1)出發(fā)出發(fā), ,依次以依次以 為搜索方向的為搜索方向的線性規(guī)劃3-41.

11、1.共軛方向及其性質(zhì)共軛方向及其性質(zhì)定理定理4-144-14)()(min)()()()(0kkkkkpXfpXf )()()1(kkkkpXX cXbQXXXfTTRXn 21)(min)1(p)2(p)3(p)1(X)2(X)3(X設(shè)設(shè) 對于對稱正定矩陣對于對稱正定矩陣Q共軛，則從共軛，則從(1)(2)(),nppp(1)(2)( ),nppp X下述算法：下述算法：推論：推論：)1( kX)1( kg)(kp)(kX)()2(2)1(1kkppp 則則 g g(k+1)與與 的任意線性組合都正交。的任意線性組合都正交。(1)(2)(),kppp) 1 (1) 2() 2(pgp ) 1(

12、) 1(gp )3(g0) 1()3( ggT0)2()3( ggT2.2.二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理) 1() 1(gp )2(2)3()3(pgp ) 1 (1) 2() 2(pgp )1()2(2)1()3()1()3(QppQpgQppTTT )1()3(QpgT )(1)1()2()3(1gggT )(1)1()2(1)1(ggQp )(1)1()3()2()3(1ggggTT 證明：證明： p(3)與與p(1)是否是否Q共軛共軛因?yàn)橐驗(yàn)間(1)與與g(2)都是都是p(1), ,p(2)的線性組合的線性組合, ,由定理由定理3-14推論，推論，0 00

13、00 0所以所以 p(3)與與p(1) Q共軛。共軛。無約束問題無約束問題4-4線性規(guī)劃3-42.2.二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理)1(X) 1 () 1 (gp )1(1)1()2(pXX )2(X) 1 (1) 2() 2(pgp )1()1()1()2(1QppQpgTT )2(2)2()3(pXX )3(X) 2(2) 3() 3(pgp )2()2()2()3(2QppQpgTT )3(3)3()4(pXX )(kX) 1(1)()( kkkkpgp )1()1()1()(1 kTkkTkkQppQpg )()() 1(kkkkpXX 求求 的最優(yōu)解的最優(yōu)

14、解X *。Q是對稱正定矩陣。是對稱正定矩陣。 1min ()2nTTX Rf XX QXb Xc ( )nX( )( )(1)1nnnnpgp ( )(1)1(1)(1)n TnnnTngQppQp (1)( )( )nnnnXXp ,)1(p,)2(p(3),p)(,np兩兩兩兩Q共軛共軛.(1)(414)nXX Th 共軛梯度法是共軛方向法，具有二次終止性。共軛梯度法是共軛方向法，具有二次終止性。四四. .共軛梯度法共軛梯度法n共軛方向及其性質(zhì)共軛方向及其性質(zhì)n二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理n二次函數(shù)共軛梯度法的迭代步驟二次函數(shù)共軛梯度法的迭代步驟n一般函數(shù)的共軛

15、梯度法一般函數(shù)的共軛梯度法nPRP算法的迭代步驟算法的迭代步驟n共軛梯度法的注釋共軛梯度法的注釋 )(minXfnRX )(NP無約束問題無約束問題4-4無約束問題無約束問題4-43.3.二次函數(shù)共軛梯度法的迭代步驟二次函數(shù)共軛梯度法的迭代步驟, 0,1)1(0 容容許許誤誤差差給給定定初初始始點(diǎn)點(diǎn)X?3)1(0 kg檢檢驗(yàn)驗(yàn))()(min:2)()()()(00kkkkkpXfpXf 一一維維搜搜索索)()()1(kkkkpXX )1(, kXX取取迭迭代代終終止止若若滿滿足足002, 1:5轉(zhuǎn)轉(zhuǎn)令令 kk1: k)()()()(kTkkTkkQppgg 或或04,轉(zhuǎn)轉(zhuǎn)否否則則計(jì)計(jì)算算：04

16、，計(jì)計(jì)算算)1()1(gp )()()()1(kTkkTkkQppQpg )()1()1(kkkkpgp )(二二次次函函數(shù)數(shù)3.3.二次函數(shù)共軛梯度法的迭代步驟二次函數(shù)共軛梯度法的迭代步驟( )( )( )( )k Tkkk TkggpQp )()()()(kTkkTkkQpppg )()()1(1)()()(kTkkkkTkQpppgg )()()1()(1)()(kTkkTkkkTkQpppggg (411) 證明：證明：無約束問題無約束問題4-40)()(04,?3否否則則轉(zhuǎn)轉(zhuǎn)取取若若是是迭迭代代終終止止檢檢驗(yàn)驗(yàn)kkXXp 0:, 0)(,1)0(0 kX令令精精度度容容許許誤誤差差取

17、取初初始始點(diǎn)點(diǎn) 一一. .最速下降法最速下降法3.3.迭代步驟迭代步驟)(2)()(0kkXfp 計(jì)計(jì)算算)()(min,4)()()()(00一一維維搜搜索索求求最最優(yōu)優(yōu)步步長長kkkkkkpXfpXf 0)()()1(02, 1:,5轉(zhuǎn)轉(zhuǎn)令令令令 kkpXXkkkk 注釋：注釋：結(jié)結(jié)論論：02)()(min)()()()(0kkkkkpXfpXf )( )(k )()()()()(kTkkppXf 且且)(0k )() 1()(kTkpXf (4 11) k )(kp)1( kX)(kX)() 1( kXf一維搜索最優(yōu)解的梯度一維搜索最優(yōu)解的梯度 與搜索方向與搜索方向 正交正交(1)()k

18、f X ( )kp無約束問題無約束問題4-43.3.二次函數(shù)共軛梯度法的迭代步驟二次函數(shù)共軛梯度法的迭代步驟( )( )( )( )k Tkkk TkggpQp )()()()(kTkkTkkQpppg )()()1(1)()()(kTkkkkTkQpppgg )()()1()(1)()(kTkkTkkkTkQpppggg (411) 證明：證明：0 0)()()()(kTkkTkQppgg 無約束問題無約束問題4-43.3.二次函數(shù)共軛梯度法的迭代步驟二次函數(shù)共軛梯度法的迭代步驟, 0,1)1(0 容容許許誤誤差差給給定定初初始始點(diǎn)點(diǎn)X?3)1(0 kg檢檢驗(yàn)驗(yàn))()(min:2)()()(

19、)(00kkkkkpXfpXf 一一維維搜搜索索)()()1(kkkkpXX )1(, kXX取取迭迭代代終終止止若若滿滿足足002, 1:5轉(zhuǎn)轉(zhuǎn)令令 kk1: k)()()()(kTkkTkkQppgg 或或04,轉(zhuǎn)轉(zhuǎn)否否則則計(jì)計(jì)算算：04，計(jì)計(jì)算算)1()1(gp )()()()1(kTkkTkkQppQpg )()1()1(kkkkpgp )(二二次次函函數(shù)數(shù)無約束問題無約束問題4-4線性規(guī)劃3-4例例4-124-12 求解求解 取取2212min()4f Xxx (1)(1,1) ,0.01TX 解：解： 8002Q 2182)(xxXg(1)(1)28pg (1)(1)00?,43k

20、kgXX 若若是是否否則則 轉(zhuǎn)轉(zhuǎn)( )( )( )( )00min (2)()kkkkkf Xpf Xp )()()1(kkkkpXX 00:1,25kk 令令轉(zhuǎn)轉(zhuǎn)()()()()k Tkkk TkggpQp (1)10( ): 11 pgk ，(1)()(1)(1)()()()04kTkkkkkkk TkgQppgppQp ，13.0)1()1()1()1(1 QppggTT 04. 073. 0) 1(1) 1()2(pXX 1 k太太大大52. 1)2( g 36. 047. 1)2(g03. 0)1()1()1()2(1 QppQpgTT 09. 054. 1)1(1)2()2(pgp

21、 2k 12TX QX 線性規(guī)劃3-4例例4-124-12 求解求解 取取2212min()4f Xxx (1)(1,1) ,0.01TX 解：解：(1)(1)00?,43kkgXX 若若是是否否則則 轉(zhuǎn)轉(zhuǎn)( )( )( )( )00min (2)()kkkkkf Xpf Xp )()()1(kkkkpXX 00:1,25kk 令令轉(zhuǎn)轉(zhuǎn)()()()()k Tkkk TkggpQp (1)10( ): 11 pgk ，(1)()(1)(1)()()()04kTkkkkkkk TkgQppgppQp ，47.0)2()2()2()2(2 QppggTT 00. 000. 0)2(2)2()3(pX

22、X 00)3(g)3(,XX 取取迭迭代代終終止止(3)0g 共軛梯度法具有二次終止性共軛梯度法具有二次終止性.2k 8002Q 2182)(xxXg(1)(1)28pg 36. 047. 1)2(g 09. 054. 1)1(1)2()2(pgp 04. 073. 0) 1(1) 1()2(pXX 四四. .共軛梯度法共軛梯度法n共軛方向及其性質(zhì)共軛方向及其性質(zhì)n二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理n二次函數(shù)共軛梯度法的迭代步驟二次函數(shù)共軛梯度法的迭代步驟n一般函數(shù)的共軛梯度法一般函數(shù)的共軛梯度法nPRP算法的迭代步驟算法的迭代步驟n共軛梯度法的注釋共軛梯度法的注釋 )(

23、minXfnRX )(NP無約束問題無約束問題4-44.4.一般函數(shù)的共軛梯度法一般函數(shù)的共軛梯度法?3)1(0 kg檢檢驗(yàn)驗(yàn))()(min:2)()()()(00kkkkkpXfpXf 一一維維搜搜索索)()()1(kkkkpXX )1(, kXX取取迭迭代代終終止止若若滿滿足足)()()()(kTkkTkkQppgg 或或04,轉(zhuǎn)轉(zhuǎn)否否則則計(jì)計(jì)算算：04)()()()1(kTkkTkkQppQpg )() 1() 1(kkkkpgp 求求 的最優(yōu)解的最優(yōu)解.X 1min ()2nTTX Rf XX QXb Xc 一維搜索一維搜索無約束問題無約束問題4-4下面推導(dǎo)下面推導(dǎo) 的三種形式，它們分

24、別對應(yīng)三種不同的的三種形式，它們分別對應(yīng)三種不同的共軛梯度法。共軛梯度法。)()()() 1()()() 1() 1(kkTkkkTkggpggg )()()()1()1()(kTkkkTkgpggg )()()()1(kTkkTkkQppQpg k 4.4.一般函數(shù)的共軛梯度法一般函數(shù)的共軛梯度法無約束問題無約束問題4-4)()()()1()1()(kTkkkTkgpggg )()()()1(kTkkTkkQppQpg )() 1(0kTkpg )1()1(1)()1( kTkkkTkpggg )() 1(1)() 1( kkkTkpgg 4.4.一般函數(shù)的共軛梯度法一般函數(shù)的共軛梯度法定理

25、定理4-14推論推論無約束問題無約束問題4-4無約束問題無約束問題4-4經(jīng)經(jīng)n次一維搜索收斂于次一維搜索收斂于 的最優(yōu)的最優(yōu)解解 。則從任意一點(diǎn)則從任意一點(diǎn)X(1)出發(fā)出發(fā), ,依次以依次以 為搜索方為搜索方向的下述算法：向的下述算法：1.1.共軛方向及其性質(zhì)共軛方向及其性質(zhì)定理定理4-144-14)()(min)()()()(0kkkkkpXfpXf )()()1(kkkkpXX cXbQXXXfTTRXn 21)(min設(shè)設(shè) 對于對稱正定矩陣對于對稱正定矩陣Q共軛，共軛，(1)(2)( ),nppp(1)(2)( ),nppp X推論：推論：)1( kX)1( kg)1(p)2(p)3(p

26、)(kp)1(X)2(X)3(X)(kX)()2(2)1(1kkppp 則則 g g(k+1)與與 的任意線性組合都正交。的任意線性組合都正交。(1)(2)(),kppp)()()()1()1()(kTkkkTkgpggg )()()()1(kTkkTkkQppQpg )() 1(0kTkpg )1()1(1)()1( kTkkkTkpggg )() 1(1)() 1( kkkTkpgg )()1(kTkgg )()(kTkpg)()1(1)()( kkkTkpgg )1()(1)()( kTkkkTkpggg )()(kTkgg 4.4.一般函數(shù)的共軛梯度法一般函數(shù)的共軛梯度法定理定理4-1

27、4推論推論無約束問題無約束問題4-4)()()()1()1()(kTkkkTkgpggg )()()()1(kTkkTkkQppQpg (1)(1)( )( )01kTkkk Tkgggg (1)(1(0)( )2kTkkk Tkggpg )()()()1()1()(kTkkkTkggggg 03k 這三個(gè)公式對應(yīng)的共軛梯度法分別稱為這三個(gè)公式對應(yīng)的共軛梯度法分別稱為FR, DM 和和 PRP算法算法.4.4.一般函數(shù)的共軛梯度法一般函數(shù)的共軛梯度法(4-32) 稱為稱為FR公式公式(4-33) 稱為稱為DM公式公式(4-34) 稱為稱為PRP公式公式無約束問題無約束問題4-4四四. .共軛梯

28、度法共軛梯度法n共軛方向及其性質(zhì)共軛方向及其性質(zhì)n二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理n二次函數(shù)共軛梯度法的迭代步驟二次函數(shù)共軛梯度法的迭代步驟n一般函數(shù)的共軛梯度法一般函數(shù)的共軛梯度法nPRP算法的迭代步驟算法的迭代步驟n共軛梯度法的注釋共軛梯度法的注釋 )(minXfnRX )(NP無約束問題無約束問題4-45.PRP5.PRP算法的迭代步驟算法的迭代步驟0,1)1(0 容容許許誤誤差差給給定定初初始始點(diǎn)點(diǎn) X?5)1(0 kg)()(min4)()()()(00kkkkkpXfpXf )()()1(kkkkpXX )1(, kXX取取迭迭代代終終止止若若滿滿足足04,

29、 1:轉(zhuǎn)轉(zhuǎn)令令 kk1: k置置06,轉(zhuǎn)轉(zhuǎn)否否則則,60nk 若若)()1()1(,kkkkpgp ?2)1(0 g)1(,XX 取取迭迭代代終終止止若若滿滿足足03,轉(zhuǎn)轉(zhuǎn)否否則則，令令)1()1(gp 03,nk 若若0)1()1(3:轉(zhuǎn)轉(zhuǎn)則則令令 kXX)()()()1()1()(kTkkkTkggggg k 計(jì)計(jì)算算)()()()1()1()(kTkkkTkggggg k 03公公式式PRP無約束問題無約束問題4-4在在PRP算法中算法中,每每n次迭代中的第一步取負(fù)梯度方次迭代中的第一步取負(fù)梯度方向?yàn)槠渌阉鞣较蛳驗(yàn)槠渌阉鞣较?這種做法簡稱為這種做法簡稱為“n步重新開始步重新開始”.這是為

30、了減少舍入誤差的影響這是為了減少舍入誤差的影響,加快收斂速度。加快收斂速度。(1)(1)pg )1(1)1()2(pXX 1: k3 n10()()?5kg X ( )( )( )( )00min (4)()kkkkkf Xpf Xp (1)()()kkkkXXp (1),XX 若若是是03否否則則轉(zhuǎn)轉(zhuǎn)(1)0)?2(g X (1),kXX 若若是是,)1(X,)2(X31 nk)2(2)2()3(pXX :12kk 04轉(zhuǎn)轉(zhuǎn),)3(X32 nk)3(3)3()4(pXX 31: kk04轉(zhuǎn)轉(zhuǎn),)4(X33 nk0)4()1(3:轉(zhuǎn)轉(zhuǎn)XX (1)(1)pg : 1k 1: k置置，令令)1()

31、1(gp 0306,轉(zhuǎn)轉(zhuǎn)否否則則04, 1:轉(zhuǎn)轉(zhuǎn)令令 kk06,kn )()1()1(,kkkkpgp ,nk 若若0)1()1(3:轉(zhuǎn)轉(zhuǎn)則令則令 kXX)()()()1()1()(kTkkkTkggggg k 計(jì)計(jì)算算無約束問題無約束問題4-4(2)(2)(1)1(1)(1)()TTggggg (2)(2)(1)1pgp (3)(3)(2)2(2)(2)()TTggggg (3)(3)(2)2pgp 5.PRP5.PRP算法的迭代步驟算法的迭代步驟?5)1(0 kg)()(min4)()()()(00kkkkkpXfpXf )()()1(kkkkpXX )1(, kXX取取迭迭代代終終止止若

32、若滿滿足足04, 1:轉(zhuǎn)轉(zhuǎn)令令 kk1: k置置06,轉(zhuǎn)轉(zhuǎn)否否則則,60nk 若若)()1()1(,kkkkpgp ?2)1(0 g)1(,XX 取取迭迭代代終終止止若若滿滿足足03,轉(zhuǎn)轉(zhuǎn)否否則則，令令)1()1(gp 03,nk 若若0)1()1(3:轉(zhuǎn)轉(zhuǎn)則則令令 kXX)()()()1()1()(kTkkkTkggggg k 計(jì)計(jì)算算,)1(X(1)(1)pg (2),X(3),X(4),X(5),X(6),X(2)(2)(1)1pgp (3)(3)(2)2pgp (4)(4)pg (5)(5)(4)4pgp (6)(6)(5)5pgp 無約束問題無約束問題4-43 n四四. .共軛梯度法共軛梯度法n共軛方向及其性質(zhì)共軛方向及其性質(zhì)n二次函數(shù)共軛梯度法的迭代原理二次函數(shù)共軛梯度法的迭代原理n二次函數(shù)共軛梯度法的迭代步驟二次函數(shù)共軛梯度法的迭代步驟n一般函數(shù)的共軛梯度法一般函數(shù)的共軛梯度法nPRP算法的迭代步驟算法的迭代步驟n共軛梯度法的注釋共軛梯度法的注釋 )(minXfnRX )(NP無約束問題無約束問題4-46.6.共軛梯度法的注釋共軛梯度法的注釋)()1(1)()( kkkTkpgg )(