第四章無約束優(yōu)化方法

1、190工程優(yōu)化士生290第四章無約束最優(yōu)化不失一般性，考慮如下的優(yōu)化min f (x)（1）xÎRn， max f (x) = - min- f (x)若為極大化無約束最優(yōu)化1）基本分為兩類：，即使用目標(biāo)函數(shù)的導(dǎo)數(shù)信息（一階或二階導(dǎo)數(shù)信息）如最速下降法，法。，共梯度法和變尺度2）直接：不使用導(dǎo)數(shù)的。390本章主要：以下幾種利用導(dǎo)數(shù)信息的最優(yōu)化 最速下降法 共軛方向法和共軛梯度法 變尺度法（DFP和BFGS）490無約束優(yōu)化的最優(yōu)性條件定理(一階必要條件)為f (x)Ne (x*)設(shè)，若x*的局部極小點(diǎn)，且在f : Rn ®RÑf (x*) = 0.內(nèi)連續(xù)可微，則定

2、理（必要條件）x*為 f (x) 的局部極小點(diǎn)，且在 Ne (x*)內(nèi)f (x)若二次連續(xù)可微，則定理(半正定。Ñf (x*) = 0,Ñ2 f (x*)充分條件)f : Rn ®R，若在N (x*) 內(nèi) f (x) 二次連續(xù)可微，且設(shè)e正定，則 x*Ñf (x*) = 0,Ñ2 fx*為 f (x) 的嚴(yán)格局部極小點(diǎn)。590若目標(biāo)函數(shù)為凸函數(shù)，有如下的定理定理(一階充要條件)x*x*f : Rn ®R設(shè)是凸函數(shù)且在處連續(xù)可微，則為f (x)的全局極小點(diǎn)的充要條件是 Ñf (x*) = 0.定理(一階必要條件)f : Rn

3、®Rx*設(shè)是嚴(yán)格凸函數(shù)且在處連續(xù)可微，若Ñf (x*) = 0, 則x*為f (x)的唯一全局極小點(diǎn)。690§1 最速下降法最速下降法是 1847 年由法國的 Cauchy 提出的求。后來，Curry 等人解多元函數(shù)極值的最早的數(shù)值作了進(jìn)一步的研究?，F(xiàn)在最速下降法已成為眾所周知的一種基本的算法，值得說明的是，一些更有效的方法都是在對它進(jìn)行改進(jìn)或在其啟發(fā)下獲得的。該的優(yōu)點(diǎn)是直觀、簡單、實(shí)用，但收斂速度慢.790一、基本思想（1），為了求解，假定我們已經(jīng)迭代了k 次，獲得了第k 個(gè)迭代點(diǎn)xk 。從 xk 出發(fā)，繼續(xù)沿該點(diǎn)處的下降方向行進(jìn)，而沿方向= -Ñf

4、(xk ) 是函數(shù)值下降最快的方向，故d k沿此方向進(jìn)行直線搜索得到第 k1 個(gè)迭代點(diǎn) xk +1 ，即= xk - l Ñxk +1kf (x )（1.1）k其中步長因子lk 滿足f (xk - l Ñf (x ) = min f (x - lÑf (xk )kk（1.2）kl ³0890二、算法步驟及框圖（P68）算法（最速下降法）誤差e > 0 ，置k = 0 ；Î Rn給定初始點(diǎn) x01)，|£ e ，則停止計(jì)算；否則，轉(zhuǎn) 3）；若| gk2)3)-計(jì)算搜索方向dkf (xk ) ；從 xk出發(fā)，進(jìn)行一維搜索，求lk沿d

5、 kf (xk + lmin f (x + ldk )d ) =kk使4)kl >0= xk + l dxk +1kkk1令，置，轉(zhuǎn)步 2）。k990- 2x2min f (x ,例 用最速下降法求解21= (1,1)T ,e =0.5.取 x0- 2x2 - 4 ö ,æ解：函數(shù)的梯度為f÷x2ø第一次迭代：-4æö,d 0 = - Ñf (x0 ) = æ4 ö ,()Ñfx=5 > 0.50|d 0|=2ç 2 ÷ç -2 ÷è

6、øèøx0 +l d 0 = æ 1+4l ö，ç1 - 2l ÷èøf (l )=f ( x0 +l d 0 )=f (1+4l ,1 - 2l )= (1+4l )2 + 2 (1 - 2l )2 - 2 (1+4l )(1 - 2l ) - 4 (1+4l )=40l 2 - 20l - 3得 l0 =1/4,令0=j ' (l) = 80l - 20,1090d 0 = æ4 ö ,- 2x2- 4 öl =1/4,æç -2 ÷

7、0f÷ ,èø2øæ1öæöæöÑf (x1 ) = æ -1ö,42x =x +l0 d = ç ÷ +1/4 ç100÷ = ç÷，ç -2 ÷è -2 øèøè1øè1/2 ø第二次迭代：2+lx1 +l d 1 = æö，d1= - Ñf (x1 ) = æ 1

8、 ö ,| d1 | = 5 > 0.5,ç1/2+2l ÷ç 2 ÷èøèøf (l )=f ( x1 +l d 1 )=f (2+l ,1/ 2+2l )= (2+l )2 + 2 (1/2+2l )2 - 2 (2+l )(1/2+2l ) - 4 (2+l ),=5l 2 - 5l - 11/ 20=j ' (l) = 10l - 5l =1/2,得令1æöæ 1 öæ 5/2 ö-22æö()x =x

9、+l1d = çÑfx=2211,÷ +1/2 ç÷ = ç÷，ç÷1èøè1/2 øè 2 øè 3/2 ø1190æö5/2-2æö()2Ñfx=x =2，,ç÷ç÷1è 3/2 øèø第三次迭代：x2 +l d 2 = æ 5/2+2l ö- Ñf (x2 ) =

10、 æ 2 ö ,= 5 >ç 3/2 - l ÷d 2d 2. ,ç -1÷èøèøf (l )=f ( x2 +l d 2 )=f (5/2+2l ,3/2 - l )= (5/2+2l )2 + 2 (3/2 - l )2=10l 2 - 5l - 27/ 4- 2 (5/2+2l )(3/2 - l ) - 4 (5/2+2l )0=j ' (l) = 20l - 5,l =1/4,得令2-1/2-1æ 5/2 öæ2 öæ3

11、öæö()x =x +l2 d = çÑfx=3322,÷ +1/4 ç÷ = ç÷，ç÷è -1øè 5/4 øèøè 3/2 ø繼續(xù)迭代可得到函數(shù)的近似最優(yōu)解。1290練習(xí)： 用最速下降求解min f (2x2ö= æ1ö誤差e = 0.1。1x0其中÷ ，初始點(diǎn)ç1÷ ，2 øè ø三、收斂性分析定理

12、1（收斂性定理）f (x)設(shè)一階連續(xù)可微，水平集G = x | f (x) £f (x0 )有界，則最速下降法或在有01390限步迭代后停止；或者得點(diǎn)列xk ，它的任何極限點(diǎn)均為 f (x) 的駐點(diǎn)。證明：P68。推論 1：在定理 1 的假設(shè)下，若 f (x) 為凸函數(shù)，則應(yīng)用最速下降法，或在有限步迭代后達(dá)到最小點(diǎn)，或者xk 的任何極限點(diǎn)都是總體極小點(diǎn)。算法的收斂速度最速下降法產(chǎn)生的序列是線性收斂的，收斂的性質(zhì)與極小點(diǎn)處的矩陣的特征值有關(guān)。1490四、最速下降法用于二次函數(shù)的情形定理 2 考慮二次函數(shù)f (x) = 1 xT Qx2其中Q 是n ´ n 階對稱正定矩陣，l1

13、, ln 分別是它的最小和最大特征值。從任意 x0 出發(fā)，對此二次函數(shù)用最速下降法，得到序列xk ，那么對于k ³ 0 有ö2æ l- lf (xk +1 ) £ ç n1f (xk )÷è ln+ l1ø1590且對于k ³ 0 有öklæ l- l| xk |£| x0 | n ç n1÷l1è ln+ l1ø因?yàn)?a = ln- l1< 1 ， 所以有 xk ® 0 。而二次函數(shù)ln + l11f (x) =x2T

14、Qx 的極小點(diǎn)正是 x* = 0 。這就證明了最速下降法對二次函數(shù)關(guān)于任意初始點(diǎn)都是收斂的。1690以下解釋最速下降法收斂特性的幾何意義。Q = æ l10 ö2 ø考慮具有對稱正定矩陣÷ 的二元二次函ç 0lèf (x) = 1T2x2)數(shù)其中l(wèi)22³ l1> 0 。顯然， l1, l2 是Q 的兩個(gè)特征值。這個(gè)函數(shù)的等值線為 f (x1 , x2 ) = c（常數(shù)c > 0 ），把22xx 1+2= 122c ö22c öæçæç它改寫成÷

15、÷llèøèø121790ln2 時(shí)，等值線變?yōu)閳A（見左圖）。與時(shí)a =- l1當(dāng)l = l= 0 ，（1）ln + l11只需一次迭代就得到了極小點(diǎn)。當(dāng)l1 < l2 時(shí)，等值線為橢圓。對于一般的初始點(diǎn)，將產(chǎn)生鋸齒現(xiàn)象。（2）l1 = l2（3）當(dāng)a時(shí)，等值線是很扁的橢圓。與此同時(shí)， (- l1 ) / (lnl1 ) 將接近于 1，此時(shí)對于一般的初始點(diǎn)n收斂速度可能十分緩慢，鋸齒現(xiàn)象嚴(yán)重（見右圖）。1890優(yōu)缺點(diǎn)優(yōu)點(diǎn):簡單，計(jì)算量及量?。怀跏键c(diǎn)選是線性收斂的.取任意.全局收斂，可證明該缺點(diǎn):1在極小點(diǎn)附近收斂的很慢，從表面上看，似乎與

16、“最速下降”，其實(shí)不然，因梯度是函數(shù)的局部性質(zhì)，從局部看在一點(diǎn)附近下降得快，但從總體上看可能走許多彎路。1990= -Ñf (xk ) 用一維搜索得+ ldk ) 的極小點(diǎn)，則事實(shí)上，若 xk +1 是沿方向dk即lj(l) = f (xk到的，k 為dj = Ñf (xk + ld ) d= 0kTkdlkÑf (xk+1)T Ñf (xk ) = 0即這說明最速下降法中，相鄰兩次的搜索方向是正交的。因此，在極小點(diǎn)附近，梯度法產(chǎn)生的點(diǎn)列逼近極小點(diǎn)的速度越來越慢。2090平行切線法（見書 P73）= xk- xk -2負(fù)梯度方向和dk結(jié)合.Shah 等人

17、于 1964 年提出了一種“平行切線法”（簡記為 PARTAN 法），又稱梯度法。由于最速下降法在極小點(diǎn)附近成“鋸齒”狀，因此下降= xk- xk -2d k過程中的搜索方向可取下兩步繼續(xù)用最速下降方向即負(fù)梯度方向。這兩種方向交替使用，效用要比最速下降法好的多。2190§2若目標(biāo)函數(shù) f (x) 在 Rn 有連續(xù)的導(dǎo)數(shù)，其海Ñ2f (x)森 矩 陣G(x) = Ñ2正 定 （ 為 方 便 起 見 ， 記f (x) ），此時(shí)可以使用下述的 Newton 法。是一維情況時(shí) Newton 切線法的推廣。此一、基本思想及迭代公式設(shè) xk是 f (x) 的極小值點(diǎn)的一個(gè)估計(jì)

18、，將 f (x) 在 xk處作Taylor 展開，并略去高于二次的項(xiàng)，則得1 (x - xk )T 2f (x) » j(x) = f (xk ) + Ñfk )2k )f2290為求j(x) 的極小點(diǎn)，可令Ñj(x) = 0 ，即Ñf (xk ) + Ñ2 fk ) = 0（2.1）f (xk ) 正定，且處的 Hessen 矩陣Ñ2f (x) 在點(diǎn) xk若Ñ2f (xk ) 可逆，則由上式解出的平穩(wěn)點(diǎn)就是j(x) 的極小點(diǎn)，以它作為 f (x) 的極小點(diǎn)的第k +1 次近似，記為 xk +1 ，由（2.1）可得的迭代公式

19、xk +1= xk -Ñ2 f (xk )-1Ñf (xk )（2.2）方向，搜= -Ñ2 f (xk )-1Ñf (xk ) 稱為這里dk2390索步長lk為 1。的算法步驟如下：1）給定初始點(diǎn) x0 ，結(jié)束精度e > 0 ， k = 0 ；2） 檢驗(yàn)是否滿足終止準(zhǔn)則。計(jì)算 Ñf (xk ) ，若| Ñf (xk ) |< e ，迭代終止， xk否則，轉(zhuǎn) 3）；為 f (x) 的近似最優(yōu)解；方向。計(jì)算Ñ2 f (xk )-1 ，取搜索方向(xk )-1Ñ (xk ) ；3）構(gòu)造= -Ñ2d

20、k4）求下一個(gè)迭代點(diǎn)。令 xk +1回 2）。= xk + d k ， k = k +1 返2490具有二次終止性：設(shè)正定二次函數(shù) f (x) = 1 xT Gx + bT x + c ，對該函2迭代，從任一點(diǎn) x0Î Rn數(shù)用出發(fā)，可得= x0 - G-1Ñf (x0 ) = x0 - G-1(Gx0 + b) = -G-1b = x*x1即一次迭代就可得到全局極小點(diǎn)。+ 25x2122，初f例始點(diǎn) x0用= (1,1)T求解誤差e = 0.1 。，2590Ñf (x0 ) = æ 2ö ,f (x0 ) = æ 20 ö

21、Ñ2ç 50 ÷ç 050 ÷ ，解因?yàn)?#232;øèøæ 1ö÷0ç=2Ñ2 f (x0 )-1ç÷故 1 ÷ ，ç 0è50 øæ 1ç 2ö0÷æ 2ö = æ -1ö= -Ñ2 f (x0 )-1Ñf (x0 )= -çd 0÷ç 50 ÷ç -1&

22、#247;1÷èøèøç 0è50 øæ 0 ö= x+ d= ç 0 ÷ ，又100因此 x| Ñf (x1) |= 0 < 0.1，迭代èø結(jié)束，得 x1 為的最優(yōu)解。2690特點(diǎn)：收斂，局部收斂。（當(dāng) xk 充分接近 x* 時(shí),局部函數(shù)可用正定二次函數(shù)很好地近似，故收斂很快）主要缺點(diǎn)：1）局部收斂,初始點(diǎn)選取不當(dāng)時(shí)，算法有可能不收Hessen 陣，且要求正定，不正定；3）需計(jì)算Hessen 陣逆或解n 階斂；2）用到時(shí)，算法出現(xiàn)量大；

23、4）步長因子總線性方程組，計(jì)算量、取 1 并不是合適的.2790定理（收斂性定理）設(shè) f (x) 有連續(xù)導(dǎo)數(shù)，Ñ2f (x) 為正定陣，水平集x | f (x) £ f (x0 ) 有界，得到的點(diǎn)列xk 有如下的性質(zhì)：則由阻尼（1） f (xk )為嚴(yán)格單調(diào)下降數(shù)列；（2） 點(diǎn)列xk 的任意極限點(diǎn)必為 f (x) 的駐點(diǎn).P70 定理 4.3 。證明見對一般的非二次函數(shù)，當(dāng)目標(biāo)函數(shù)滿足一定條件，選取的初始點(diǎn)比較靠近極小點(diǎn)時(shí)，可證明的收斂速度是的.2890二、1阻尼阻尼的正= xk + l dxk +1k的迭代公式是k方向， lk 是由= -Ñ2 f (xk )-1

24、Ñf (x ) 為其中dk一維搜索產(chǎn)生的步長因子，即滿足f (xk + ld ) = min f (x+ ldk )kkkl ³0算法步驟與類似。2990例 用阻尼求解下列x - x2 )2min f21)T= (0, 0)T02，取初始點(diǎn) x誤差e = 0.1。，x其中練習(xí)：用阻尼min f (求解下列無約束優(yōu)化= (1,1)T ,e = 0.1.- 222x0,1的缺點(diǎn)：Ñ2 f (xk ) 可能奇異；即使Ñ2f (xk ) 非阻尼奇異，也未必正定。策略：克服Ñ2f (xk ) 不正定30902Levenberg-Marguardt-M法）

25、f (xk ) + e IÑ2 f (xk )k代替= Ñ2基本思想：用Mk陣，ek 是一個(gè)適當(dāng)?shù)恼龜?shù)，只要ek其中I 是n 階選得合適，就可使Ñ2 f (xk ) + e Ik正定，從而解方程組Mk d= -Ñf (x )kk得到在點(diǎn) xk 處的下降方向-1k= -MkÑf (x )d k3190§3 共軛梯度法最速下降法：計(jì)算步驟簡單，但收斂速度較慢；和阻尼儲(chǔ)量大（每次需計(jì)算：收斂度快，但計(jì)算量及存陣及其逆陣）；希望找到，它兼有這兩種的優(yōu)點(diǎn)又能克服它們?nèi)秉c(diǎn)。共軛方向法就是這樣的一類，且具有二次終止性。最典型的共軛方向法是共軛梯度法

26、。3290一、共軛方向法及其性質(zhì)定義 3.1 設(shè) A 為n 階對稱陣，d1 , d 2 為n 維非零(d1)T Ad 2 = 0（3.1）列則稱，若d1 , d 2 為 A - 正交，或關(guān)于 A - 共軛。若 A = In ，則（3.1）即為(d ) d= 0 ，這就是通常1 T2意義下的正交性，故 A - 正交，或 A - 共軛是正交概念的推廣。d 1, d 2 ,L, d m是Rn 中的一組非零向定義 3.2 設(shè)量，如果3390Ad= 0(i ¹ j)i, j = 1, 2,L, m(d i )T則這組方向。j是 A 共軛的，或稱它們是一組 A 共軛A = æ 21&#

27、246;ç12 ÷ ，取èø= æ1= æ1ö, d 2öd1ç1÷ç -1÷ ， A 共軛，且是正交的；è øèø= æ1 ö , d 4= æ1öd 3ç 0 ÷ç -2 ÷ ， A 共軛，但不正交；èøèø3490= æ1 ö , d 6= æ 0 öd 5ç 0

28、 ÷ç1 ÷ ，不是 A 共軛，但是正交的èøèø注：正交不一定共軛，共軛也不一定正交.n定 理 3.1設(shè)A是階 對 稱 正 定 陣 ，d1, d 2 ,L, dm是m 個(gè) A 共軛的非零，則該組線性無關(guān)。一組數(shù)a1,a2 ,L,am ，使證：設(shè)måi=1ad + a+L + aa=d=01d 2dmi12mi3590則對于"j Î1, 2,L, m ，有mmå(dåad ) =aAdi =a (dAd= 0j )Tij )Tj )TjA(diiii=1i=1jd又是 正 定

29、 陣 ，為 非 零， 所 以為線性無關(guān)a j的= 0( j = 1, 2,L, m) 。所以d1, d 2 ,L, dm組。設(shè) p Î Rn ， d1, d 2 ,L, d n 是 Rn定理 3.2中線性組。如果 p 與每個(gè)di 都正交，則 p = 0 。無關(guān)的證明見 P77 引理 4.6證。3690n定 理3.3設(shè)A為階 對 稱 正 定 陣 ，f (x) = 1 xT Ax + bT x + c ，若d 1 , d 2 ,L, d n 為任一組 A -2共軛的非零，則由任意初始點(diǎn) x1 出發(fā)，按下列迭代格式min f (xk + ldk ) =f (xk + l d )kkl &g

30、t;0= xk + l d kkxk +1k = 1, 2,L, n至多迭代n 次必達(dá)到最優(yōu)點(diǎn)（稱為二次收斂）.3790= Ñf (xk ) = Axk+ b ，則有證明：記 gk+ b = A(xk + l d k ) + bkgk +1 = Axk +1+ lk Adk=k = 1, 2,L, ngk¹ 0(i = 1, 2,L, n),gi若反復(fù)用上述遞推公式得+ l+ l+ l Adn = Lgn+1=Adn=n-1Adn-1gnnn1n+ l+ l= gk +1Adk +1Adk +2+Lk +1k +2+k = 1, 2,L, n+ ldk ) 的最優(yōu)解，故nn

31、 Adk由于lmin f (xk 是l >00 = Ñf (xk + lk = (gk +1 )T d kk = 1, 2,L, nkTd ) dk3890 gn+1T d k= gk +1T d k+ ld k +1T Ad k+ ld k +2T Adkk +1k +2（1）+L+ lndAdnTk= 0k = 1, 2,L, n - 1(gn+1 )T d n= 0在上式中令k = n 得（2）(gn+1 )T d k= 0k = 1, 2,L, n .綜合（1）、（2）兩式有由定理 3.1 知d 1 , d 2 ,L, d n 線性無關(guān)，再由定理3.2= xn + l

32、d= 0 即 xn+1及上式知 gn+1n為最優(yōu)解.n共軛方向法：把從初始點(diǎn) x1 出發(fā)，依次沿某組共軛方向進(jìn)行一維搜索求解無約束優(yōu)化的稱為共軛方向法（Conjugate direction method）3990共軛方向法的基本步驟：1.選取初始點(diǎn) x1 ，計(jì)算Ñf (x1 ) ，使Ñf (x1 )T d 1< 0 ，誤差e > 0 ，令k = 1 ；給定f ( xk + l d k ) = min f ( xk + ld k ) ；k2.求lk ，使得l >0= xkl d3.令 xk +1k；k4.若| Ñf ( xk +1 ) |<

33、 e ，停機(jī)；否則，轉(zhuǎn) 5；5.選取搜索方向dk +1 ，使(d k +1 )TAd= 0( j = 1, 2,L, k) ， k = k + 1 ，轉(zhuǎn) 2.j4090二. 共軛梯度法（Conjugate gradient method）共軛梯度法是最著名的共軛方向法， 它首先由Hestenes 和Stiefel(1952)提出來作為.由于性方程組的性方程組等價(jià)于極小一個(gè)正定二次函數(shù)，故 1964年 Fletcher和Reeves 提出了無約束極小化的共軛梯度法.4190共軛梯度法的基本思想：把共軛與最速下降法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向， 并沿著組方向進(jìn)行搜索，求出目標(biāo)函數(shù)的極

34、小點(diǎn).據(jù)共軛方向法的基本性質(zhì)，這種止性.具有二次終以下二次函數(shù)情形討論共軛梯度法。設(shè)f (x) = 1 xT Ax + bT x + c2其中 A 是n 階對稱正定陣， b Î Rn , c Î R .4290g (x) = Ñf (x) = Ax + b取 x1 為初始點(diǎn)，且Ñf (x1 ) ¹ 0,= -Ñf (x1 ) = -g1 ，以下由d 1 出發(fā)，逐步構(gòu)造令d 1d 1, d 2 ,L, d n , 使之為 A 共軛組.在 x1 處沿d 1 作一維精確搜索求l1 ，即+ ld 1 ) =f (x1 + l d )min f

35、 (x111l ³0= x1 + l d ,令 x21= 01 T g 2(d )則14390(d 1 )T ( Ax2 + b) = (d 1 )T A(x1 + ld ) + b11= (d 1 )T ( Ax1 + b) + l Ad 11+ l (d ) Ad 1 = 0= (d 1 )Tg11 T1(d 1 )Tg1l = -1(d 1 )T Ad 1一般地，若已知 xk 和搜索方向dk ，從 xk沿方向dk 作一維搜索得，出發(fā)，xk +1= xk + l d kk4490k ) Tk( dgl= -其中kk ) Tk( dA d計(jì)算 f (x) 在 xk +1 處的梯度，

36、 gk +1= Ñf (xk+1) ，若| Ñf (xk+1) |= 0 ，則停止計(jì)算；+ ak dk否則，令dk +1于 A 共軛。= -gk +1，并使dk +1 和dk關(guān)于是(d k )T+ ak (d ) Ad= 0k Tkk = 1, 2,L, n - 1.Adk +1= -(dk )TAgk +1Agk +1(d k )Tak =,(d k )T Adk4590于是得到的n 個(gè)搜索方向d 1 , d 2 ,L, d n 如下：ìï d=- Ñ f ( x 11)ï dk + 1- gk + 1kdíïk

37、k + 1k ) T( dA gï a=k = 1 , 2 , L , n - 1ïîkkTk( d)A d可以證明： 由上述構(gòu)造的搜索方向是一組 A 共軛方向； g1 , g 2 ,L, gn 是一d 1, d 2 ,L, d n組兩兩正交的方向.4690定理 3.4上述構(gòu)造的d 1 ,L, dn 是一組 A -共軛方向， g1 ,L, gn 是兩兩正交的.用數(shù)學(xué)歸納法證明.具體證明見 P79.設(shè) f (x) = 1 xT Ax + bT x + c ，其中 A定理 3.52是 n階正定陣。由上述產(chǎn)生的點(diǎn)列為xn， 產(chǎn) 生 的 一 組A- 共 軛 方 向 為=

38、Axk + b(k = 1, 2,L, n) ，則必有以d 1, d 2 ,L, d n，gk下幾種等價(jià)的計(jì)算公式：4790(gk+1)T Adk(1)ak =k =1,2,L,n-1(Daniel,1967),(dk )T Adk(gk+1)T (gk+1 - gk )(dk )T (gk+1 - gk )(2) k =k =1,2,L,n-1(Sorenson-Wolfe,1972),-(gk+1)T gk+1(3)k =k =1,2,L,n-1(Myers,1972),(dk )T gk| gk+1 |2(4)k =k =1,2,L,n-1(Flecher -Reeves,1964),|

39、 gk |2(gk+1)T (gk+1 - gk )(5)k =k =1,2,L,n-1(Polyak - Polak - Ribiere,1969),(gk )T gk4890三 FR共軛梯度法的計(jì)算步驟步驟1. 選定初始點(diǎn)x1 。£ e= x1 ，否則轉(zhuǎn)步驟3。，算法停止，x*g1步驟2. 如果步驟3. 取 d1= - g1,k =1.步驟4. 精確一維搜索找最佳步長xk+1 = xk+dkl，令kk£ e ，算法停止，x* = xk +1 , 否則轉(zhuǎn)步驟6。gk +1步驟5. 如果步驟6. 如果k=n, 令 x1 =xk +1 ,d1 = - gk +1 , 算法停止

40、,k=1 ，轉(zhuǎn)步驟4;否則轉(zhuǎn)步驟7。2gk +1步驟7. 計(jì)算a= -g+a=, dk +1k +d , k = k +1,1k轉(zhuǎn)步驟4。kk2gk4990注：第 6重新開始操作，由于計(jì)算誤差的影響，使得算法不能有限步終止，故需重新開始.幾點(diǎn)說明：1.d1 必須取作-g1 ；，難于精確計(jì)算ak , lk ，故2. 由于計(jì)算誤差的不能保證算法有限步終止，故有時(shí)需迭代n 次后，重新賦 xn+1= x1 ，再重新進(jìn)行迭代；. 前述的ak 的計(jì)算公式對正定二次函數(shù)而言是等價(jià)的，對其他的函數(shù)效果卻是不相同的，經(jīng)驗(yàn)上，PRP公式效果較好；5090例用FR共軛梯度法求下列min f ( x) =x1 - 2

41、x1 x2，已知初始點(diǎn)(1,1)T迭代精度e = 0.001。解：1）第一次迭代：沿負(fù)梯度方向搜尋計(jì)算初始點(diǎn)處的梯度- 2x - 4 ö2-g = Ñf (x0 ) = æ 2x1æö4= æ4 ö ,=,p = -gç 2 ÷0ç -2 ÷0èø0èø4 ö = æ1 + 4l ö= æ1ö + l æ+ l p0x0ç1÷ç -2 ÷ç

42、;1 - 2l ÷è øèøèø5190= æ1 + 4l ö+ l p0x0ç1÷2èø精確一維搜索求最佳步長，f l令=f (x0 + l p0 )=f (1+ 4l 1- 2l)=40l 2 - 20l - 30=f'(l )=80l - 20,l = 0.25得0g = Ñf (x1 ) = æ -1ö ,= æö ,2= x0 + lx1p0ç -2 ÷1èø

43、00.5èø不滿足精度，繼續(xù)迭代：5290= æ -4 ö ,= æ -1ö ,ggç 2 ÷ç -2 ÷10èøèø2）第二次迭代：æ4 öæö2p = ç -2 ÷, x= ç 0.5÷,012g5èøèøa= 0.25 10220g0= æ2.ö ,= -g + ap1p0ç÷10è

44、ø2 + 2l= æö + l æö = æö ,22+ l p1x1ç 0.5÷ç1.5÷ç 0.5 +1.5l ÷èøèøèø精確一維搜索求最佳步長，f (l )= (x1 + l1 )= (2 + 2l,0.5+1.5l=(2 + 2l)2 + 2(0.5 +1.5l)2 - 2(2 + 2l)(0.5 +1.5l) - 4(2 + 2l)5390fl=(2 + 2l)2+ 2(0.5 +1.5l)2

45、- 2(22l)(0.51.5l) - 4(22l)2 + 2l+ l p1 = æöx1ç 0.5 + 1.5l ÷èø0=f' l ,令l = 1,得1= æ 4 ö ,g= Ñf (x2 ) = æ 0 ö ,l px =x +211ç 2 ÷ç 0 ÷21èøèø= æ 4 ö .= 0 < eg= x2得到最優(yōu)解:x*因ç 2 ÷2è

46、ø2x2min f (練習(xí)： 用FR共軛梯度法求解下列，結(jié)束精度e = 0.001 。= (5, 5)T初始點(diǎn)x15490四. 用于一般函數(shù)的共軛梯度法1.步長因子不能再用公式計(jì)算，而須改用其他的一維搜索確定；2. 凡是用到矩陣 A 之處， 需要改用現(xiàn)行點(diǎn)處的Hessian 陣Ñ2f (xk ) 代替；3用此法求一般函數(shù)的極小點(diǎn)，一般來說，用有限步迭代是辦不到的，故需采取一些策略；4對一般函數(shù)，前述的計(jì)算ak得到的搜索方向，一般用 FR 方是不同的，經(jīng)驗(yàn)對于二次凸法，對一般函數(shù)用PRP.5590五.共軛梯度法的收斂性定理 3.6 設(shè) f (x) 是連續(xù)可微凸函數(shù)，水平集L

47、= x | f (x) £f (x1 )有界，則由共軛梯度法產(chǎn)生的點(diǎn)列xk 有下列性質(zhì)：klim f (x )k f (x )(1)是嚴(yán)格單調(diào)下降數(shù)列，從而；k ®¥(2) xk 的任一極限點(diǎn)都是min f (x) 的最優(yōu)解.證明見 P86 定理 4.10.5690Crowder 和 Wolfe 證明：共軛梯度法的收斂速度不壞于最速下降法；他們還證明了，初始方向不取負(fù)梯度方向時(shí)，共軛梯度法的收斂速度是線性收斂的.算法特點(diǎn)：1.對凸函數(shù)全局收斂（下降算法）；線性收斂；2.每步迭代只需若干（適用于大規(guī)模問題）；3.有二次終止性。5790§4變尺度法-DFP

48、法和 BFGS 法一.變尺度法的基本思路變尺度法是由 Davidon 于 1959 年首先提出的，1963 年為 Fletcher 和 Powell 所發(fā)展，形成為著名的 DFP 變尺度算法.1. 變尺度算法的基本思想最速下降法：計(jì)算簡便，收斂速度慢；及阻尼斂速度快；：計(jì)算量、量大，收5890設(shè)想：能否設(shè)計(jì)一種算法，它既有快速收斂的特點(diǎn)，又能避免計(jì)算導(dǎo)數(shù)矩陣及其逆陣，就可構(gòu)造出每次迭代的搜索方向d k ?最速下降法：計(jì)算步驟簡單，但收斂速度較慢和阻尼：收斂度快，但計(jì)算量及量大（每次需計(jì)算陣及其逆陣）；5990最速下降法和阻尼的統(tǒng)一迭代格式：xk +1（= xk - l H Ñf (x

49、k )kk（1）法的迭若 H= I陣），最速下；k= Ñ2 f (xk )-1 ，得阻尼若Hk的迭代公式；的迭代公式.特別的，取lk= 1 ，得的優(yōu)點(diǎn)，希望Hk基本思想：為了保持能近似的等于Ñ2f (xk )-1 ，且Hk能在迭代計(jì)算中逐次生成。2.擬方程60902k-1 近似，且易于計(jì)算，為使Hk 確實(shí)與Ñ f (x )必須對Hk附加某些條件：1)為保證算法具有下降性質(zhì)，要求 Hk 中的每一矩陣都是對稱正定的；2) Hk +1 由Hk 經(jīng)簡單形式而得，且希望Hk在計(jì)算中逐次生成，即Hk +1 = Hk + Ck（2）其中Ck 稱為矩陣或校正矩陣，（2）稱為公式或

50、校正公式。61903) Hk 滿足擬程）。設(shè)迭代過程已進(jìn)行到k + 1 步，x k +1 , Hk方程（下邊將推導(dǎo)此方已求出，以下推導(dǎo)Hk 必須滿足的條件.先n 元二次函數(shù)f (x) = 1 xT Gx + bT x + c2x Î Rn , b Î Rn , c Î R ， G 為n 階對稱正定陣，6290令g(x) = Ñf (x) = Gx + b, gk = g(xk )= Gxk + b，g k+1= Gxk +1+ b則gk所以gk +1- gk = G(xk+1xk- xk )ïìí（3）令k +1gkgk&#

51、239;îgDgk = GDxkDxk = G-1Dgk（4）則（5）或?qū)σ话愕膎 元非二次函數(shù)，設(shè) f (x) 有連續(xù)的二6390階偏導(dǎo)數(shù)，將 f (x) 在點(diǎn)xk +1 進(jìn)行 Taylor 展開，取前三項(xiàng)可得，( x k + 1 )x k + 1 )f ( x ) »f+-f12( x -x k + 1 ) T( x -x k + 1 )Gk + 1f (xk+1 ) ，f (x) »f (xk+1 )G(x - xk+1 )=2其中Gk +1k +1或g » gk +1+ G(x - xk+1 ) ，令x = xk ，得到k +1gk »

52、 gk +1+ G(x - xk+1 )k +1GDxk » Dg k（4）（5）即或k +1-1Dgk» DxkGk +16490-1k +1，應(yīng)要求Hk +1 滿足為使Hk +1 較好的近似GHk +1Dg= Dxkk（6）（7）BDxk = Dgk或k +1-1這里B= H.稱（6）和（7）式稱為擬k +1k +1方程。由擬方程確定的是一族算法，稱之.其主要步驟如下：擬1）選取初始點(diǎn)x0 , 初始矩陣H （通常取為0誤差e , k = 0;陣），65902）如果| gk |< e , 則停機(jī)，否則計(jì)算= -Hkkk3）沿方向d k 作線性搜索求lk ，使f (x

53、k + ld ) = min f (x + ldk )kkkl ³04）校正Hk 產(chǎn)生Hk +1 ，使得擬方程成立；5） k = k + 1, 轉(zhuǎn)步 2）。6690與相比，擬的優(yōu)點(diǎn)：1） 僅需一階導(dǎo)數(shù)；2） Hk 保持正定，使得算法具有下降性質(zhì)；3）每次迭代需O(n2 ) 次乘法；4）在一定條件下，具有超線性斂速；5）對嚴(yán)格凸函數(shù)，用精確一維搜索，有全局收斂性。6）二次終止性6790二.對稱秩 1 校正公式= Hk + CkHk +1若要求Ck 是秩為 1 的對稱矩陣，則可設(shè)C = a uuT（8）的 待 定 常kkak其 中為 不 等 于0數(shù) ，u = (u1 , u2 ,L, u

54、n )¹ 0T= Hk + akuuTHk +1所以，將其代入（6）得Hk Dg+a uu Dg= DxkTkkk6890又ak , u DgTk為數(shù)量，所以u 與Dxk- Hk Dgk成正比，不妨設(shè)u = Dxk - H Dgkk11a=故kuT DgkDgkT (Dxk - Hgk )k其中(Dgk )T (Dxk - H Dgk ) ¹ 0k，于是(Dxk - H Dgk )(Dxk - H Dgk )T= H+ kkH（9）k +1k(Dgk )T (Dxk - H Dgk )k6990（9）成為對稱秩 1 校正公式，由對稱秩 1 校正公式確定的變尺度法稱為對稱秩 1 變尺度法對稱秩 1 校正特點(diǎn)：算法操作簡單；在一定條件下是收斂的，且具有二次終止性；缺點(diǎn):