ch05常用無約束最優(yōu)化方法

1、第5章 常用無約束最優(yōu)化方法 15.1 無約束問題的最優(yōu)性條件 考察最優(yōu)化問題 (5.1) 其中f(x)是定義在Rn中的實函數(shù), 最優(yōu)化問題(5.1)是求函數(shù)f(x)在Rn中的極小值點。稱之為無約束最優(yōu)化問題(Unconstrained Optimization)。當n=1時, (5.1)就是一元函數(shù)的極小值問題； 當n1時, (5.1)就是多元函數(shù)的極小值問題。 2定理5.1 設f(x)可微，若向量p在x(k)處滿足則p是f(x)在x(k)處的下降方向。 3定理5.2(一階必要條件) 設f(x)在x*的某個鄰域內(nèi)具有連續(xù)的偏導數(shù), 則x*是f(x)的局部極小值點(Local minimum)

2、的必要條件是 定理5.3(二階必要條件) 設f(x)在x*的某個鄰域內(nèi)具有連續(xù)的二階偏導數(shù), 則x*是f(x) 的局部極小值點的必要條件是 且 半正定 定理5.4(二階充分條件) 設f(x)在x*的某個鄰域內(nèi)具有連續(xù)的二階偏導數(shù), 若 且 正定, 則x*是f(x)的嚴格局部極小點(Isolated local minimum)。 4定理5.5 設f(x)在x*的某個鄰域 內(nèi)具有連續(xù)的二階偏導數(shù), 若 且 半正定, 則x*是f(x)的局部極小點。定理5.6 設f(x)是Rn上的凸函數(shù)且f(x)具有連續(xù)的偏導數(shù), 則x*是f(x)的全局極小點(Global minimum)的充分必要條件是 例5.

3、1 利用一階和二階條件求解 解： 由 有 又由 有 由定理5.1和定理5.3知x(2)是局部極小點。 5求解問題(5.1)具體做法為： 給定初值x(0), 按照某一個規(guī)則構造迭代序列 使 由于x(k)是向量序列, 令向量pk和數(shù) 滿足： 即 使即向量序列x(k) 使目標函數(shù)值f(x(k)是單調減小的, 具有這種性質的算法稱為下降算法。 65.2 最速下降法 考察無約束最優(yōu)化問題 其中f(x)具有連續(xù)偏導數(shù)。 對該問題的求解采用下降算法, 設x(k)是f(x)的極小點x*的一個近似值, 尋找下一個x(k+1)近似值滿足 將f(x)在x(k)處作一階Taylor展開有： 為使x充分接近于x(k)時

4、有f(x)0, 令k=012求出 , 取搜索方向3若f(x(k+1)f(x(k), 則x*=x(k), 停止計算, 否則轉4。 4 轉2。 9例5.2 取步長 , 初值 , 求解 解： , 該問題的準確解為2 0.001598082-0.040008249 0.953703372-0.0463493622 1.920063924-0.079503257 0.078970629-0.075736864 0 1 2 3 4迭代次數(shù) 10計算結果見下表 5.2.2 最速下降法 1847年Cauchy給出了最速下降法。 即 的取值由f(x)從x(k)出發(fā)沿方向 的整體極小點來確定。 1944年Curr

5、y對該方法進行了改正, 取 k為f(x)從x(k)沿方向 的第一個極小值點作為x(k+1), 這樣施行起來比Cauchy方法容易得多。 11算法5.2.2(最速下降法) 給出初始點x(0)及誤差精度0。 12求 , 若 , 停止計算并輸出x*=x(k)3一維搜索求最優(yōu)步長 取 4若 得最優(yōu)解x*=x(k+1) , 停止計算, 否 則令 轉2。 12例5.3 取 。用最速下降法求解 解： , 在算法的第三步使用一維搜索方法求步長 , 計算結果如下表: 迭代次數(shù)x1(k)x2(k)kf(x(k)0220.0200307210411.919877-0.307178510-20.481538703.6

6、8614420.708869110-1 0.708873810-10.020030720.13065030.680470810-1-0.108875310-30.481538500.4630710-240.251250710-2-0.385905110-50.020030720.1641310-350.241185310-2-0.385905110-50.481537600.5817410-560.890569110-40.890548810-40.020030720.2062010-670.854891610-4-0.136784410-60.480768700.7308410-880.32

7、8812510-50.3151298910-50.020.2482710-990.315660010-500.50.9964110-11100000 使用最速下降法計算時, 在開始幾步迭代計算中, 步長比較大, 而且自變量的改變和函數(shù)值的下降幅度也較大, 但當接近收斂時, 步長很小, 自變量的改變量也很小, 所以目標函數(shù)值下降得很慢, 也即在最優(yōu)解附近迭代點是以鋸齒形狀在前進。其理論依據(jù)為: 迭代公式中的步長 是函數(shù) 的極小點, 所以有 由復合函數(shù)的求導公式有 14即相鄰兩個迭代點處函數(shù)f(x)的梯度向量是正交的, 這就使得迭代過程是沿鋸齒狀行進的而且越接近收斂, 步長就越小, 迭代點的移動越

8、慢。梯度是函數(shù)的局部性質, 從局部看在x(k) 處函數(shù)值下降得最快, 但從整體上看是走了很多彎路。 實用中為了避免出現(xiàn)鋸齒行進的情況, 常采用兩種避免方法。第一, 選擇較好的初始點。第二, 迭代到一定的步數(shù)后采用非精確的一維搜索, 即用一維搜索求出最優(yōu)步長 后取 這樣可避免相鄰兩個迭代點的梯度向量正交的情況。 155.3 Newton法 Newton法的基本思想是用二次函數(shù)來逼近f(x), 并求出二次函數(shù)的極小值點作為f(x)的近似最優(yōu)解。 假設f(x)二階連續(xù)可微, 在第k次近似解x(k)處進行二階Taylor展開有 在 是非奇異的情況下, 略去高階無窮小就有近似公式： 165.3.1 Ne

9、wton法 Newton法的迭代公式為： 算法5.3.1(Newton法) 給出初始點x(0)及誤差精度0。 1 2求 , 若 , 停止計算并輸出x*=x(k)3計算4迭代計算 5若 則停止計算, 輸出 否則令 轉2。 17 18 前面介紹的最速下降法本質上是用線性函數(shù)去逼近f(x), 而Newton法是用二次函數(shù)去逼近f(x), 所以Newton法的收斂速度比最速下降法快。理論上已經(jīng)證明最速下降法具有線性收斂性, 而Newton法卻具有二階收斂性。特別當f(x)是二次函數(shù)時, Newton法具有整體收斂性。即對任一初值x(0), 用Newton法迭代一次就可得到最優(yōu)解。當f(x)是非二次函數(shù)

10、時, Newton法雖然是二階收斂的, 但只具有局部的收斂性, 也即當初值x(0)充分接近最優(yōu)解時, Newton法才是收斂的。例5.4 求解 解: 取初值 有 在實用中算法的第4步常改寫為解方程組 此時第5步的終止條件為 。 19例5.5 用Newton法求解 準確解為 。 解：取初值第一輪迭代： 20第二輪迭代： 21計算結果如下表： 22迭代次數(shù)01111-0.521.3913043-0.6956521731.7459441-0.9487980941.9862783-1.0482081051.9987342-1.0001700061.9999996-1.000001905.3.2 阻尼N

11、ewton法 阻尼Newton法是將Newton法中的 看成一個搜索方向, 并且用一維搜索方法求出最優(yōu)步長的方法。 算法5.3.2(阻尼Newton法) 給出初始點x(0)及誤差精度0。 12求 , 若 , 停止計算并輸出x*=x(k)3求 并計算4求 , 其中 滿足 23 245若 則停止計算, 輸出x*=x(k+1)否則令 轉2。 阻尼Newton法也有無法克服的缺點。 第一、Hesse矩陣可能出現(xiàn)奇異的狀況。 第二、即使Hesse矩陣非奇異, 但無法保證Hesse矩陣的正定性, 為克服這兩個缺點, 將迭代公式取為： 其中 是充分大的正數(shù), 以保證 是對稱正定矩陣。 使用阻尼Newton法

12、可以克服Newton法的局部收斂性的缺點, 從而可以適當?shù)胤艑拰Τ跏键cx(0)的要求。 5.4 擬Newton法(變尺度法) Newton法成功的關鍵是利用了Hesse矩陣提供的曲率信息, 而計算Hesse矩陣的工作量大, 有的目標函數(shù)的Hesse矩陣不好求出, 需要一種僅用目標函數(shù)梯度的方法, 擬Newton法就是利用梯度 的信息, 構造出目標函數(shù)的曲率近似, 而且不必形成明顯的Hesse矩陣, 同時還具有收斂速度快的優(yōu)點。 Davidon于1959年提出了一個設想, 其核心是僅用在每次迭代中得到的梯度信息來近似Hesse矩陣, 該設想導致了一類非常成功的算法-擬Newton法, 包括兩個最

13、著名的算法: DFP算法和BFGS算法。 255.4.1 擬Newton法的基本思想:最速下降法和阻尼Newton法的迭代公式統(tǒng)一為：其中 為步長, Hk為n階對稱矩陣。若Hk=I, 則是最速下降法；若 , 則是阻尼Newton法; 26 前者有較好的整體收斂性, 但收斂太慢, 后者收斂快, 但整體收斂性差, 要計算二階導數(shù), 工作量大, 現(xiàn)期望Hk的選取既能逐步逼近 , 又不計算二階導數(shù), 為此, 對Hk附加條件。1). Hk是對稱正定矩陣;2). Hk+1由Hk經(jīng)簡單修正而得到 27為使算法有下降性質, 顯然, 當Hk正定時, 從而方向 為下降方向。其中 稱為修正矩陣(也應為對稱陣), (

14、5.4.1)式稱為修正公式。3). Hk滿足擬Newton條件:常用的無約束方法其中事實上，由有取 29 擬Newton法的基本思想是:先取H0為某一對稱正定矩陣, 然后在每一次迭代中利用關系式(5.4.2)產(chǎn)生修正矩陣, 再由關系式(5.4.1)產(chǎn)生迭代矩陣Hk, 并確定出相應的搜索方向。 由于修正矩陣Hk的選取不唯一, 因此使用不同的方法產(chǎn)生的修正矩陣Hk , 便可產(chǎn)生不同的矩陣序列Hk。由于這種方法產(chǎn)生的搜索方向在每一次迭代中都作改變度量矩陣意義下的最速下降方向, 因此這類方法統(tǒng)稱為變尺度法。這里只介紹兩種常用的變尺度法, DFP法和BFGS法。 30 DFP方法是由Dividon于19

15、59年首先提出, 后在1963年又由Fletcher和Powell作了改進簡化而形成的, 故常稱之為DFP方法。在目前是無約束非線性規(guī)劃方法中最有效的算法之一。由于擬Newton法要求Hk滿足設其中 為待定向量。在（2）兩端同乘 有5.4.2 DFP方法 31為了使（1）成立，必須要為了保證 及（2）的右邊為對稱矩陣，取 32此時有故此時修正矩陣為：DFP算法的矩陣迭代公式為：算法5.4.1 (DFP法)1. 任取 和H0(一般取H0=I)2. 若 則停; 否則令 k由一維搜索求得;3. 計算4. kk+1, 轉2。 33例5.6 用DFP算法求解取解: 取H0=I時, DFP法的第一步與最速

16、下降法相同。 34第二輪迭代：先計算 35得:令： 利用：求得：因 停止, x(2)即為最優(yōu)解。 36 37 BFGS方法是由Broyden, Fletcher, Goldfarb和Shanno于1970年共同研究的成果。5.4.3 BFGS方法由于擬Newton法要求 滿足取其中 是一個實數(shù)。滿足 38取 變得DFP公式。若取迭代公式 BFGS法比DFP法更具有實用性, 其原因是BFGS法對一維搜索的精度要求不高, 并且由BFGS法產(chǎn)生的矩陣Hk不易于變?yōu)槠娈惥仃嚒６鴮τ贒FP法, 由于一維搜索的不精確和計算誤差的累積可能導致某一步的 Hk為奇異矩陣。 5.5 共軛梯度法 定義5.5.1 設

17、H為n階對稱正定矩陣, 若n維非零向量pi, pj滿足 , 則稱向量pi, pj是 H-共軛的。 特別當H=I時有 , 此時H-共軛就變成了向量正交的概念。所以, H-共軛實質上是向量正交的推廣, 而且將對稱正定矩陣H進行分解H=QTQ ,此時就有： , 對向量pi, pj施行線性變換y=Qp, 則有 ; 即向量yi和yj是正交向量。 39定義5.5.2 對m個n維非零向量p1, p2, , pm; 若有 稱向量組p1, p2, , pm是H-共軛向量組, 也稱彼此H-共軛。 顯然H-共軛向量組是線性無關的向量組, 而且由于Rn中有且僅有n個彼此H-共軛的向量, 所以Rn中的H-共軛向量p1,

18、 p2, , pn構成Rn的一組基。 40 實用中常常需要從一組線性無關的向量組中, 構造出彼此H-共軛的向量組, 稱它為H-共軛化方法。設向量組g1, g2, , gm線性無關。令 則向量組p1, p2, , pm是H-共軛向量組，在實用中還可以將其單位化。 41 42 設x*為f(x)最優(yōu)點, x(0) 為任一給定的初始點, 若p0, p1, , pn-1是H-共軛的, 則它們可以構成Rn中的一組基, 因此向量x*-x(0) 就可由p0, p1, , pn-1線性表示。設則 這樣求f(x)的最優(yōu)解x*就轉化為求系數(shù) 的問題。設x(k)為一個迭代點, 令是 的極小點, 則有 , 從而有 43

19、記 有 當f(x)是二次函數(shù) 時, 有此時有 得 由于x*是f(x)的極小點, 故有 44在(5.5.1)式的兩端同時左乘 有同理, 記 , 則兩端左乘 , 并由H-共軛得 45即k是從迭代點x(k)出發(fā)沿方向pk求二次函數(shù)的極小點的步長。 因此, 若有了n個彼此H共軛的方向p0, p1, , pn-1則無論初始點x(0)是如何選取的, 從該初始點出發(fā) 分別沿p0, p1, , pn-1作一維搜索, 最多作n次一維搜索便可得二次函數(shù)f(x)的極小點x*, 這個性質稱為二次截止性。而且共軛方向的選取有很大的隨意性, 由此就有不同的共軛方向法。5.5.1 自然共軛方向法 該方法是從n個單位向量ei(i=1,2,n)出發(fā), 利用共軛化過程產(chǎn)生共軛方向p1, p2, , pn, 從而建立起相應的共軛方向法。 算