最優(yōu)化理論與算法第五章

1、第五章 擬牛頓法5.1 擬牛頓法牛頓法具有收斂速度快的優(yōu)點，但需要計算hesse矩陣的逆，計算量大。本章介紹的擬牛頓法將用較簡單的方式得到hesse矩陣或其逆的近似，一方面計算量不大，另一方面具有較快的收斂速度，這類算法是無約束最優(yōu)化問題最重要的求解方法。一、擬牛頓條件設(shè)在上二次可微，為了獲得hesse矩陣在處的近似，先研究如下問題?？紤]在附近的二次近似：.兩邊求導(dǎo)，有 令，有 再令 ，則有 或 .因此，我們要求構(gòu)造出的hesse矩陣的近似或hesse矩陣逆的近似應(yīng)分別滿足： 或 （5.1）它們均稱之為擬牛頓條件。二、一般擬牛頓算法1） 給出初始點，.2） 若，停止；否則，計算（擬牛頓方向）.

2、3） 沿方向進(jìn)行線性搜索，（可以是精確，也可非精確）.令.4） 校正產(chǎn)生，使擬牛頓條件滿足.5） ， 轉(zhuǎn)2）擬牛頓法較之牛頓法有下述優(yōu)點：1） 僅需梯度（牛頓法需hesse矩陣）；2） 保持正定，因而方向具有下降性質(zhì)（而牛頓法中可能不定）；3） 每次迭代需次運算，而牛頓法需次運算。注： 正如牛頓法中牛頓方向是在橢球范數(shù)下的最速下降方向一樣，也可看成是在橢球范數(shù)下的最速下降方向，也就是在空間某種特定度量（尺度）意義下的最速下降方向。由于每次迭代都在變化，因而度量（尺度）也在變化。正因為如此，常稱擬牛頓算法為變尺度法。從這個意義上講，牛頓法本身也是變尺度法。三、對稱秩一校正公式（sri校正）設(shè)是第

3、次迭代的hesse逆的近似，希望對校正得到，即若設(shè)是一個秩一矩陣，則 . （5.2）由擬牛頓條件： 得 （取，使） （5.3）將（5.3）代入（5.2）得 （5.4） 稱之為一般broyden秩一校正公式特別地，取時，稱為broyden秩一校正公式。一般地，上述不對稱，由于hesse矩陣是對稱的，故希望也對稱，因而取從而得 （5.5）稱之為對稱秩一校正。對稱秩一校正法在用于正定二次函數(shù)時，不需要進(jìn)行一維搜索，具有有限終止性質(zhì)。定理5.1 設(shè)線性無關(guān)，那么對于正定二次函數(shù)，對稱秩一校正方法至多步終止，即。證明：首先用歸納法證明擬牛頓條件的遺傳性質(zhì)，即 。當(dāng)時，直接由（5.5）可知結(jié)論成立。若假定

4、結(jié)論對成立，現(xiàn)考慮情形，此時1）當(dāng)時，由歸納法假設(shè)，有故當(dāng)時， 。2）當(dāng)時，直接由（5.5）可得。再根據(jù)以上所得遺傳性質(zhì)，有 ，（） 由線性無關(guān)，故有，即。注：1）證明中對除了要求線性無關(guān)外，沒有其他條件，因而簡單取也是可以的。這樣完全不用一維搜索，并且由，得到最優(yōu)解。2）sri校正的缺點是不能保證的正定性，除非始終保持。當(dāng)用于一般函數(shù)時，由算出的搜索方向不能保證是下降方向，這在一定程度上妨礙了它的應(yīng)用。四、dfp校正考慮對稱秩二校正 由 得 取 ， 即有 ， ，得校正公式： （5.6）稱之為dfp公式（由davidon,fletcher,powell提出）。dfp公式是最重要的擬牛頓校正公式

5、，有很多重要性質(zhì)。對于正定二次函數(shù)（若采用精確一維搜索） 1） 具有有限終止性；2） 擬牛頓條件具有遺傳性質(zhì)；3） 當(dāng)時，產(chǎn)生共軛方向和共軛梯度。對于一般函數(shù)4）校正保持正定性，因而算法具有下降性質(zhì)；5）方法具有超線性收斂速度；6）當(dāng)采用精確一維搜索時，對于凸函數(shù)，算法具有總體收斂性。定理5.2 當(dāng)且僅當(dāng)時，dfp校正公式保持正定性。證明：用歸納法。由初始選擇，顯然正定。設(shè)結(jié)論對成立，即正定，并記的cholesky分解為。下面考慮時的情形，設(shè)則 由cauchy不等式知： （*）又由題設(shè)，故有由于，而（*）中等式成立當(dāng)且僅當(dāng)與平行，亦即當(dāng)且僅當(dāng)與平行。而當(dāng)與平行時，便有。此時因而，對任何，均有，

6、定理于是證畢。注：上面定理中，條件是可以滿足的。事實上，由 ，有 （正定）而 。當(dāng)采用精確一維搜索時，有，從而。而當(dāng)采用非精確一維搜索（如wolfe-powell準(zhǔn)則）時，只要適當(dāng)提高搜索精度，就可使小到所要求的程度，從而有。定理5.3 （dfp方法的二次終止性）設(shè)是二次正定函數(shù)，若采用精確一維搜索，那么dfp方法具有遺傳性質(zhì)和方向共軛性質(zhì)，即對于，有， （遺傳性質(zhì)） ， （方向共軛性質(zhì)）方法在步迭代后終止。若，則。證明： 對兩組式子同時用歸納法證明。當(dāng)時，結(jié)論顯然成立。設(shè)結(jié)論對成立，現(xiàn)證明時結(jié)論亦成立。注意到，由精確一維搜索及歸納法假設(shè)，對于，有由及，得這就證明了定理中的第一組式子。下證第二

7、組式子，即，。由dfp公式立即可得而對于，由有 定理證畢。由此定理可知，dfp擬牛頓法是共軛方向法。若取，則初始方向為負(fù)梯度方向，此時方法變成共軛梯度法。dfp算法是一個在理論分析和實際應(yīng)用中都起重要作用的算法。五、bfgs校正和psb校正我們知道擬牛頓條件有兩個： （hesse逆近似） （hesse近似）在上一段中，得到了關(guān)于的dfp校正公式： （5.7）若在上式中實行代換：，即可得到關(guān)于的校正公式 （5.8）稱之為的bfgs（broyden,flecther,goldforb,shanno）校正公式。對上式應(yīng)用秩一校正的求逆公式，又得到的bfgs校正公式： （5.9a） (5.9b) (5

8、.9c)再將上式中，得的dfp公式 （5.10a） (5.10b) (5.10c) 以上討論告訴我們，對一個給定的擬牛頓校正公式，通過交換，可得到關(guān)于的對偶校正，再利用秩一求逆公式，又得（對偶校正）。而對再實施上述對偶操作，還可恢復(fù)到原來的。從這種觀點看是的對偶校正公式。對sri校正公式 （5.11）進(jìn)行交換后得： （5.12）再利用秩一求逆公式，得的對偶仍為其自身，因而sri校正是自對偶的。bfgs校正是迄今為止最好的擬牛頓公式，它不僅具有dfp校正所擁有的各種性質(zhì)，而且當(dāng)采用非精確一維搜索時，對于一般函數(shù)也具有總體收斂性，但這一結(jié)論對dfp校正尚未獲得證明。powell對一般的broyde

9、n秩一校正公式采用對稱化改造，得到了psb公式。其基本思想是：在一般broyden秩一校正公式的基礎(chǔ)上，構(gòu)造一個不斷滿足對稱性和擬牛頓條件的矩陣序列，然后求出這個矩陣序列的極限，則該極限矩陣是一個滿足對稱性和擬牛頓條件的矩陣，從而產(chǎn)生出一個校正公式。設(shè)是對稱矩陣，令 ，一般地， 不一定對稱，因而將其對稱化，令雖然對稱，卻不一定滿足擬牛頓條件。因而重復(fù)以上過程，產(chǎn)生序列： 可證明這個矩陣序列是收斂的，其極限為加上下標(biāo)，則得到一類秩二校正公式 （5.13）這個校正類包括了很多的校正公式，在（5.13）式中，若令則得到關(guān)于的對稱秩一校正公式（sr1公式）；若令，則得到關(guān)于的dfp校正公式；若令 其中

10、，則得到關(guān)于的bfgs校正；若令，則得到psb校正： （5.14）這個校正在理論研究和實際計算中是十分重要的，其缺點是不能保證校正矩陣的正定性。值得指出的是，通過交換，可得到關(guān)于的類似校正公式。前面介紹了一些擬牛頓校正公式，以及派生新的擬牛頓法校正公式的方法（如對偶方法，對稱技術(shù)等）。有時候，還可利用一些特殊的附加條件推出校正公式。1）bfgs校正是由dfp校正公式經(jīng)過替換與秩一矩陣求逆得到的校正公式。事實上對其它校正公式也可采用類似方法獲得新的校正公式，這些新的派生公式稱為原公式的對偶，對偶方法是產(chǎn)生新校正公式的一種重要方法。若一個校正公式的對偶還等于其自身，則稱之為自對偶。2）將一般的br

11、oyden秩一校正公式反復(fù)采用對稱化、應(yīng)用秩一校正使其滿足擬牛頓條件，生成一迭代序列，其極限構(gòu)成一類新的秩一校正公式，而且很多常見的校正公式都含在這個類中，特別地得到psb校正公式。3）有時我們得到的校正公式是一類，在這一類中通常需附加上另外的條件而得到具體的校正公式。這種附加條件有各種提法，若讓（或）最靠近（對應(yīng)地），由此種條件導(dǎo)出的校正公式稱為最小改變割線校正，一些重要的校正公式在適當(dāng)選取的范數(shù)下均具有這種性質(zhì)。5.2 broyden族上節(jié)討論的dfp校正和bfgs校正都是對稱秩二校正，且都是通過，來獲得校正矩陣。下面考慮dfp與bfgs的加權(quán)組合： （是參數(shù)）顯然，這樣得到的校正公式必滿

12、足擬牛頓條件。這就得到以為參數(shù)的一大類校正公式，稱之為broyden族校正公式。，容易看到 （5.15）其中。當(dāng)時，得dfp校正；時，得bfgs校正；時，得sri校正；而時，得hoshino校正。類似地，有關(guān)于的broyden族校正： （5.16）其中。注：由于和，也可以直接驗證broyden族校正對任意的和都滿足擬牛頓條件。broyden族的二次終止性和正定性定理5.4 （broyden族校正二次終止性定理）設(shè)是正定二次函數(shù)，是其hesse矩陣，那么當(dāng)采用精確線性搜索時，broyden族校正具有遺傳性質(zhì)和方向共軛性質(zhì)，即對于，有： ， （遺傳性質(zhì)） ， （方向共軛性質(zhì)）方法在步迭代后終止。若

13、，則。證明：證明與定理5.3類似，略。定理5.5 （broyden族校正的正定性）設(shè)參數(shù)，當(dāng)且僅當(dāng)時，broyden族校正公式保持正定性。 5.3 huang族huang族是比broyden族更廣泛的一類校正公式。在broyden族中，是對稱的且滿足擬牛頓條件 。 但在huang族中取消了對對稱的限制，并將擬牛頓條件進(jìn)一步放松為 （5.17）稱之為廣義擬牛頓條件，其中是一個參數(shù)。為了使huang族擬牛頓法用于二次正定函數(shù)時，所產(chǎn)生的搜索方向共軛，進(jìn)而具有二次終止性。設(shè)huang族校正公式的形式為（詳細(xì)分析可參見徐成賢等著近代優(yōu)化方法或袁亞湘等著最優(yōu)化理論與方法）：其中,滿足： ，在上面的方程組

14、中，含有三個自由參數(shù)。特別地，令,，則只含一個自由參數(shù)，若取為自由參數(shù)，則有： （5.18）其中，正好蛻變?yōu)閎royden族校正公式，這表明broyden族是huang族的子族。一般地，huang族中含有三個自由參數(shù)，可產(chǎn)生豐富的校正公式。注：1）若采用精確一維搜索，對于正定二次函數(shù)，所有huang族變尺度算法產(chǎn)生相同的迭代點列；對一般函數(shù)產(chǎn)生的點列只依賴于。2) 另外，當(dāng)極小化正定二次函數(shù)時，若取，則huang族校正公式產(chǎn)生的搜索方向與f-r共軛梯度法相同，因而也是共軛方向法。5.4 擬牛頓法的局部收斂速度一、一般擬牛頓算法超線性收斂的特征假設(shè)1：1）設(shè)在開凸集中二階連續(xù)可微；2）存在一個嚴(yán)

15、格局部極小點，且正定；3）存在的一個鄰域，使得。定理5.6 （不帶步長因子的擬牛頓算法超線性收斂的充要條件）設(shè)滿足假設(shè)1中的1）與2），又設(shè)為一非奇異矩陣序列。假定對某，迭代序列恒在中且，又設(shè)該序列收斂于。則當(dāng)且僅當(dāng)時，序列超線性收斂到。定理5.7 （帶步長因子的擬牛頓算法超線性收斂的充要條件）設(shè)滿足定理5.6中的假設(shè)，又設(shè)為一非奇異矩陣序列。假定對某，迭代序列恒在中且，又設(shè)該序列收斂于。如果成立，那么序列超線性收斂到且的充要條件是收斂到1。注：1）要使算法超線性收斂，步長因子必趨近于1；2）擬牛頓算法超線性收斂的幾何特征是：其位移在長度與方向上都必趨近于牛頓方向。定理5.8 （基于精確搜索的

16、擬牛頓法的超線性收斂性）設(shè)滿足假設(shè)1中的1）與2），又設(shè)為一非奇異矩陣序列。假定對某，迭代序列恒在中且，又設(shè)該序列收斂于。由精確線性搜索產(chǎn)生，則當(dāng)成立時，一定有和，從而序列超線性收斂到。定理5.9 （基于wolfe-powell準(zhǔn)則的擬牛頓法的超線性收斂條件）設(shè)滿足假設(shè)1中的1）與2），又設(shè)為一非奇異矩陣序列。假定對某，迭代序列恒在中且，又設(shè)該序列收斂于。由不精確線性搜索的wolfe-powell準(zhǔn)則產(chǎn)生，則當(dāng)成立時，一定有和，從而序列超線性收斂到。二、broyden秩一校正的局部超線性收斂性 定理5.10 （關(guān)于hesse近似）設(shè)滿足假設(shè)1，又設(shè)存在正常數(shù)，使得 和 則由broyden秩一方

17、法 產(chǎn)生的迭代序列是有定義的，且超線性收斂到。定理5.11（關(guān)于hesse逆近似）設(shè)滿足假設(shè)1，又設(shè)存在正常數(shù)，使得 和 則由hesse逆broyden秩一方法 產(chǎn)生的迭代序列是有定義的，且超線性收斂到。三、dfp和bfgs算法的局部超線性收斂性定理5.12 設(shè)滿足假設(shè)1，又設(shè)在的一個鄰域內(nèi)， 其中， 。于是，存在和 ，使得對于 和，dfp方法 產(chǎn)生的迭代序列是有定義的，且超線性收斂到。類似于hesse近似形式的dfp方法，可以建立對hesse擬近似的bfgs方法的局部收斂性定理。定理5.13 設(shè)滿足假設(shè)1，又設(shè)在的一個鄰域內(nèi)， 其中， 。于是，存在和 ，使得對于 和，bfgs方法 有定義，產(chǎn)

18、生的序列線性收斂。如果，那么序列超線性收斂到。byrd，nocedal，yuan于證明了broyden族的超線性收斂性。定理5.14 設(shè)在開凸集上二階連續(xù)可微且一致凸，又存在的一個鄰域，使得 成立。則對于任何正定矩陣，當(dāng)線性搜索滿足wolfe-powell準(zhǔn)則時，broyden族算法（，即不包含dfp算法）所產(chǎn)生的極小化序列，超線性收斂到。定理5.15 設(shè)在開凸集上二階連續(xù)可微且一致凸，又存在的一個鄰域，使得 成立。則對于任何正定矩陣，當(dāng)采用精確線性搜索時，broyden族算法所產(chǎn)生的極小化序列超線性收斂到。5.5 擬牛頓法的總體收斂性一、精確搜索條件的總體收斂性powell于1971年證明了當(dāng)目標(biāo)函數(shù)是二階連續(xù)可微且一致凸函數(shù)時，采用精確搜索的dfp方法的全局收斂性及滿足lipschitz條件時的超線性收斂性。1976年，證明了為凸函數(shù)時，采用wolfe-powell準(zhǔn)則的bfgs方法的全局收斂性和超線性收斂性。1987年byrd，nocedal，yuan將powell的結(jié)果推廣到除dfp以外的所有限制broyden族算法（即），證明了全局收斂性及超線性收斂性。定理5.