信息與計(jì)算科學(xué)畢業(yè)論文無(wú)約束優(yōu)化的改進(jìn)變尺度算法

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　?。?0 屆）</b></p><p>　　無(wú)約束優(yōu)化的改進(jìn)變尺度算法 </p><p>　　所在學(xué)院 </p><p&g

2、t;　　專業(yè)班級(jí) 信息與計(jì)算科學(xué) </p><p>　　學(xué)生姓名 學(xué)號(hào) </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 </p><p><b&g

3、t;　　摘要</b></p><p>　　最優(yōu)化計(jì)算是實(shí)際應(yīng)用中的一個(gè)十分活躍的數(shù)學(xué)方法. 隨著計(jì)算機(jī)的普及, 已廣泛應(yīng)用于化工, 機(jī)械, 建筑等許多工程技術(shù)部門. 而且在解決生產(chǎn)組織, 資源分配等管理科學(xué)問(wèn)題時(shí), 最優(yōu)化計(jì)算也是一種重要方法. 無(wú)約束優(yōu)化在實(shí)際最優(yōu)化問(wèn)題中占有很大的比例, 而變尺度算法正是解決無(wú)約束優(yōu)化問(wèn)題最有效的算法之一.</p><p>　　在本文中, 我

4、們研究了變尺度算法的原理和計(jì)算步驟, 通過(guò)對(duì)比計(jì)算證明了算法的優(yōu)越性, 其收斂速度快且計(jì)算較為簡(jiǎn)潔. 并基于Wei zengxin提出的改進(jìn)BFGS公式研究了一類改進(jìn)的變尺度算法并通過(guò)數(shù)值實(shí)驗(yàn)證明其收斂性. </p><p>　　關(guān)鍵詞：無(wú)約束優(yōu)化; 變尺度; DPF; BFGS</p><p><b>　　Abstract</b></p><p&

5、gt;　　Optimization is a very active mathematical method in the practical application. As the computers being more and more popularity, Optimization has been widely </p><p>　　used in many engineering departmen

6、t such as chemical industry, machinery and</p><p>　　architecture. Even in solving some management science problems like production organization and resource resources, optimization is also an important metho

7、d. Unconstrained optimization holds a large proportion in practical optimization problems. And Variable-dimension is one of the most effective algorithms in solving unconstrained optimization problems.</p><p&g

8、t;　　In this dissertation, we studied the principle and the calculation steps of variable-dimension algorithm. We proved the superiority of variable-dimension algorithm through comparing the calculation, we see its conver

9、gence rate is fast and its calculation is very succinct. At last, we studied a new modified BFGS method based on Wei zengxin’s new modified BFGS formula and proved that it had convergence properties. </p><p>

10、;　　Keywords: Unconstrained optimization; variable-dimension; DPF; BFGS</p><p><b>　　目錄</b></p><p><b>　　摘要I</b></p><p>　　AbstractIV</p><p><b

11、>　　1 前言1</b></p><p>　　2 無(wú)約束最優(yōu)化的求解3</p><p>　　2.1 函數(shù)的極值點(diǎn)3</p><p>　　2.2 極值點(diǎn)存在的條件3</p><p>　　2.3 梯度法求解5</p><p>　　2.4 Newton法簡(jiǎn)介6</p>&l

12、t;p><b>　　3 變尺度算法7</b></p><p>　　3.1 變尺度法的基本思想7</p><p>　　3.2 變尺度法的基本原理7</p><p>　　3.3 DFP法8</p><p>　　3.4 BFGS法簡(jiǎn)介10</p><p>　　3.5 變尺度法的

13、優(yōu)越性11</p><p>　　3.6 變尺度法的matlab實(shí)現(xiàn)13</p><p>　　4 變尺度法的改進(jìn)15</p><p>　　4.1 BFGS法的改進(jìn)15</p><p>　　4.2 改進(jìn)算法的推導(dǎo)15</p><p>　　4.3 改進(jìn)算法的步驟16</p><p>

14、;　　4.4 算法的數(shù)值對(duì)比17</p><p><b>　　小結(jié)20</b></p><p><b>　　參考文獻(xiàn)21</b></p><p>　　致謝錯(cuò)誤!未定義書(shū)簽。</p><p><b>　　1 前言</b></p><p>　　隨著

15、生產(chǎn)和經(jīng)濟(jì)的高速發(fā)展, 最優(yōu)化的方法在越來(lái)越多的領(lǐng)域得到了應(yīng)用, 可謂是數(shù)學(xué)在實(shí)際應(yīng)用中最為廣泛的方法之一. </p><p>　　在實(shí)際中, 很多問(wèn)題的目標(biāo)函數(shù)或約束條件中都含有非線性函數(shù), 這一類問(wèn)題就是非線性規(guī)劃問(wèn)題. 非線性規(guī)劃是最優(yōu)化問(wèn)題的一個(gè)重要分支. 其數(shù)學(xué)模型可寫成以下形式</p><p>　　, （1.1）</p&g

16、t;<p>　　即在n維空間的一個(gè)子集中求目標(biāo)函數(shù)的極小值點(diǎn)和極小值.</p><p>　　最優(yōu)化計(jì)算方法通?？煞譃閮深? 即無(wú)約束優(yōu)化和約束優(yōu)化. 在（1.1）中, 如果, 則問(wèn)題被稱為無(wú)約束非線性規(guī)劃問(wèn)題, 即</p><p>　　, （1.2）無(wú)約束最優(yōu)化算法的重要性不僅體現(xiàn)在其本身解決無(wú)約束優(yōu)化問(wèn)題的應(yīng)用，而且還

17、可以將一些約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題來(lái)處理. 從這個(gè)意義上講, 無(wú)約束優(yōu)化算法也是處理約束優(yōu)化問(wèn)題的基本方法.</p><p>　　無(wú)約束優(yōu)化的算法有許多種, 早在1847年, Cauchy就提出了最速下降法, 也稱梯度法. 這就是最早的求解無(wú)約束最優(yōu)化問(wèn)題的方法. 對(duì)于變量不多的某些問(wèn)題, 此方法是可行的, 但是對(duì)于變量較多的一類問(wèn)題, 就常常不適用了. 其原因是除某些特殊情形外, 計(jì)算產(chǎn)生的方程組是非線性的,

18、對(duì)它的求解十分困難; 而最速下降法的收斂速度往往又很慢. 之后出現(xiàn)并發(fā)展了收斂性能較好的牛頓法, 需要計(jì)算目標(biāo)函數(shù)的二階導(dǎo)數(shù), 故而計(jì)算量較大. 而變尺度法則是既保持了牛頓法收斂速度快的特點(diǎn), 是超線性收斂的, 又克服了牛頓法計(jì)算量大的缺點(diǎn). 變尺度算法最早由Davidon在1959年提出, 是無(wú)約束最優(yōu)化計(jì)算方法中最為杰出的, 最富有創(chuàng)造性的工作. 之后經(jīng)由Fletcher和Powell的改進(jìn)簡(jiǎn)化, 于1963年形成了Davidon-

19、Fletcher-Powell法, 簡(jiǎn)稱DFP法. 1970年, Huang對(duì)變尺度算法作了處理，得出了包含3個(gè)自由參數(shù)的Huang族變尺度法. 在這之前的1967年, Broyden也曾提出只包含1個(gè)自由參數(shù)的Broyden族變尺度法, 現(xiàn)視作Huang族變尺度法的一個(gè)子</p><p>　　無(wú)約束最優(yōu)化方法已具有較完善的方法, 但是仍有許多工作可以做. 在當(dāng)代的變尺度研究中, Liao aiping在Byrd

20、和Nocedal提供的工具框架下, 對(duì)BFGS法作了改進(jìn), 于1997年提出了一種雙參數(shù)修正的擬牛頓法, 具有更好的適應(yīng)性. Xiao yunhai和Wei zengxin等人也分別對(duì)BFGS公式做了改進(jìn). </p><p>　　本文的第二章主要介紹了無(wú)約束優(yōu)化求解的條件及基礎(chǔ)方法. 第三章詳細(xì)介紹了變尺度算法的原理及計(jì)算步驟, 并通過(guò)計(jì)算顯示其優(yōu)越性. 第四章基于BFGS法的各類改進(jìn)公式研究了一類改進(jìn)的變尺度算

21、法并利用數(shù)值實(shí)驗(yàn)證明其優(yōu)越性. </p><p>　　2 無(wú)約束最優(yōu)化的求解</p><p>　　2.1 函數(shù)的極值點(diǎn)</p><p>　　求解最優(yōu)化問(wèn)題, 關(guān)鍵就是求出極小點(diǎn). 函數(shù)的極小點(diǎn)有兩種: 局部極小點(diǎn)和全局極小點(diǎn). 在文獻(xiàn)[5]中做出如下定義: </p><p>　　定義2.1 對(duì)于, , 若存在, 使得當(dāng)時(shí), 總滿足<

22、/p><p><b>　?。?.1）</b></p><p>　　則稱是的局部極小點(diǎn). 若當(dāng)時(shí), 式（2.3）不等號(hào)恒成立, 則稱是的嚴(yán)格局部極小點(diǎn). </p><p>　　定義2.2 對(duì)于任意, 若存在, 使得式（2.1）恒成立, 則稱是的全局極小點(diǎn). 若當(dāng)時(shí), 式（2.1）不等號(hào)恒成立, 則稱是的嚴(yán)格全局極小點(diǎn).</p><

23、;p>　　盡管在解決現(xiàn)實(shí)問(wèn)題的計(jì)算中, 我們要尋找的往往是全局極小點(diǎn), 但現(xiàn)有的理論和算法大多只能近似求出局部極小點(diǎn). 所以一般地說(shuō), 求解無(wú)約束最優(yōu)化問(wèn)題的算法都是通過(guò)多次迭代, 設(shè)法尋找多個(gè)局部極小點(diǎn)，然后將其中取值最小的那個(gè)極小點(diǎn)近似的作為全局極小點(diǎn). </p><p>　　2.2 極值點(diǎn)存在的條件</p><p>　　首先根據(jù)文獻(xiàn)[6]介紹梯度和海塞矩陣的定義.</p

24、><p>　　定義2.3 設(shè)是上的開(kāi)集, , 若對(duì)各分量的一階偏導(dǎo)數(shù)都存在, 即函數(shù)在點(diǎn)處一階可導(dǎo), 則稱向量</p><p><b>　　（2.2）</b></p><p>　　為函數(shù)在點(diǎn)處的梯度. </p><p>　　定義2.4 設(shè)是上的開(kāi)集, , 若對(duì)各分量的二階偏導(dǎo)數(shù)都存在, 即函數(shù)在點(diǎn)處二階可導(dǎo), 則稱向

25、量</p><p><b>　　（2.3）</b></p><p>　　為函數(shù)在點(diǎn)處的Hesse矩陣. </p><p>　　下面說(shuō)明極值點(diǎn)存在的必要條件和充分條件.</p><p>　　定理2.1（必要條件） 設(shè)是上某一開(kāi)集, 在上有一階連續(xù)偏導(dǎo)數(shù), 且在點(diǎn)取得局部極值, 則必有</p><p>

26、;<b>　　即</b></p><p><b>　　.</b></p><p>　　證明: 可反證, 假設(shè), 取, 則有</p><p><b>　　, </b></p><p>　　那么就是在點(diǎn)處的下降方向, 即存在, 使得</p><p><

27、b>　　, .</b></p><p><b>　　取, 由得</b></p><p><b>　　, </b></p><p><b>　　故存在點(diǎn), 使</b></p><p><b>　　, </b></p><

28、p>　　這與是局部極點(diǎn)相矛盾. </p><p>　　定理 2.2（充分條件） 設(shè)是上某一開(kāi)集, 在上有二階連續(xù)偏導(dǎo)數(shù), ,</p><p>　　若, 且正定, 則為的嚴(yán)格局部極小點(diǎn). </p><p>　　證明: 對(duì)任意和, 由, 有二階Taylor展式</p><p><b>　　,</b></p>

29、;<p><b>　　正定, 那么</b></p><p><b>　　,</b></p><p><b>　　故存在, 使</b></p><p><b>　　,</b></p><p><b>　　即存在任意點(diǎn), 使</b

30、></p><p><b>　　,</b></p><p>　　故為的嚴(yán)格局部極小點(diǎn).</p><p>　　2.3 梯度法求解</p><p>　　在求解無(wú)約束極值問(wèn)題的方法中, 梯度法是最古老和最基礎(chǔ)的方法. 下面通過(guò)例題簡(jiǎn)單介紹梯度法的求解步驟. </p><p>　　例1 用梯度法

31、求的極小點(diǎn), 終止誤差</p><p><b>　　解 取初始點(diǎn)</b></p><p>　　此時(shí)分別計(jì)算得 </p><p><b>　　則繼續(xù)進(jìn)行迭代.</b></p><p><b>　　步長(zhǎng) </b></p><p>

32、;　　此時(shí) ,</p><p><b>　　故為極小點(diǎn).</b></p><p>　　2.4 Newton法簡(jiǎn)介</p><p>　　Newton法的基本思想是用一個(gè)二次連續(xù)可微函數(shù)去近似目標(biāo)函數(shù)，然后精確求出這個(gè)二次函數(shù)的極小點(diǎn), 以它作為所求函數(shù)極小點(diǎn)的近似值.</p>

33、<p>　　Newton法步驟:</p><p>　　第1步 選取初始點(diǎn), 令, 給定終止誤差</p><p>　　第2步 計(jì)算梯度, 若, 則停止并輸出. </p><p><b>　　否則繼續(xù)第3步.</b></p><p>　　第3步 構(gòu)造Newton方向</p><p>　

34、　令, 置, 轉(zhuǎn)向第2步. </p><p><b>　　3 變尺度算法</b></p><p>　　3.1 變尺度法的基本思想</p><p>　　變尺度法是對(duì)牛頓法的修正, 它不再需要繁瑣地計(jì)算二階偏導(dǎo)數(shù)的矩陣和它的逆矩陣, 而是設(shè)法構(gòu)造一個(gè)對(duì)稱正定矩陣, 用已得到的一階偏導(dǎo)數(shù)來(lái)代替二階偏導(dǎo)數(shù), 通過(guò)迭代步驟使其逐漸逼近Hesse矩陣或其

35、逆. 由于對(duì)稱正定矩陣在迭代過(guò)程中是不斷修正改變的, 它對(duì)于一般尺度的梯度起到改變尺度的作用, 因此稱做變尺度. </p><p>　　在迭代過(guò)程中, 先用梯度法, 再用牛頓法并避開(kāi)牛頓法的Hesse矩陣的逆矩陣的繁瑣計(jì)算, 這就是變尺度法的基本構(gòu)想. </p><p>　　3.2 變尺度法的基本原理</p><p>　　變尺度法的基本原理, 即構(gòu)造矩陣使其可以近

36、似Hesse矩陣或其逆.</p><p>　　假定無(wú)約束極值問(wèn)題的目標(biāo)函數(shù)具有二階連續(xù)偏導(dǎo)數(shù), 為對(duì)其極小點(diǎn)第k次迭代之后得到點(diǎn). 在該點(diǎn)將目標(biāo)函數(shù)展成Taylor級(jí)數(shù), 取二階近似, 得到</p><p><b>　　, </b></p><p><b>　?。?.1）</b></p><p>　

37、　對(duì)上式（3.1）兩邊求梯度有</p><p><b>　　,</b></p><p><b>　　令, 有</b></p><p><b>　　,</b></p><p><b>　　設(shè)可逆, 則</b></p><p>　　.

38、 （3.2）</p><p>　　記, , 式（3.2）即為 </p><p>　　. （3.3）</p><p>　　容易推證, 若是帶有正定系數(shù)矩陣A的二次函數(shù)：</p><p><b>　　,</b></p><p

39、>　　則（3.3）將成為等式, 即</p><p>　　, 且 . （3.4）</p><p>　　此時(shí), 只需計(jì)算目標(biāo)函數(shù)的一階導(dǎo)數(shù), 就可以依據(jù)方程估計(jì)該處的Hesse矩陣的逆. </p><p>　　為了用不包含二階導(dǎo)數(shù)的矩陣近似牛頓法中的Hesse矩陣的逆矩陣, 必須滿足</p><p><b

40、>　　, 即擬牛頓條件,</b></p><p>　　而矩陣是隨迭代步驟的變動(dòng)而變化的, 假定每一個(gè)這樣的矩陣由迭代格式</p><p>　　產(chǎn)生, 稱為修正矩降.</p><p>　　代入擬牛頓條件, 有 </p><p>　　或 .

41、 （3.5）</p><p>　　為了簡(jiǎn)單構(gòu)造出每一輪的搜索方向, 在開(kāi)始時(shí)可以取為單位矩陣. 然后, 在每第k輪利用擬牛頓條件按基本關(guān)系式（3.5）產(chǎn)生修正短陣, 并利用其使得到下一個(gè)迭代矩陣. 如此反復(fù)迭代, 可以產(chǎn)生一系列迭代矩陣從而相應(yīng)地確定出一系列搜索方向. </p><p>　　在變尺度算法中, 迭代格式為, 其中為搜索方向, 為步長(zhǎng),</p&

42、gt;<p>　　, 通過(guò)求得, 于是, 不同的校正公式構(gòu)成了不同的變尺度算法. </p><p><b>　　3.3 DFP法</b></p><p>　　DFP法是一個(gè)非常著名的變度量法, 首先由Davidon在1959年所提出, 后經(jīng)Fletcher和Powell加以改進(jìn)于1963年形成的. </p><p>　　DFP變

43、尺度法綜合了梯度法、牛頓法的優(yōu)點(diǎn)而又避棄它們各自的缺點(diǎn), 只需計(jì)算一階偏導(dǎo)數(shù), 無(wú)需計(jì)算二階偏導(dǎo)數(shù)及其逆矩陣, 對(duì)目標(biāo)函數(shù)的初始點(diǎn)選擇均無(wú)嚴(yán)格要求, 收斂速度快. 對(duì)于高維（維數(shù)大于50）問(wèn)題被認(rèn)為是無(wú)約束極值問(wèn)題最好的優(yōu)化方法之一. </p><p>　　為了產(chǎn)生迭代矩陣序列, 關(guān)鍵是要不斷地確定出修正矩陣, 假定一個(gè)簡(jiǎn)單的形式為</p><p>　　, 為待定向量

44、 （3.6）</p><p><b>　　兩邊共乘, 有.</b></p><p>　　與（3.5）做比較, 顯然</p><p><b>　　, ,</b></p><p>　　由于要求對(duì)稱, 需取 , （3.7）</p&

45、gt;<p>　　則有 </p><p>　　. （3.8）</p><p>　　綜合（3.7）和（3.8）, 得</p><p>　　, （3.9）</p><p>　　可得修正矩陣的表達(dá)形式

46、</p><p><b>　　,</b></p><p>　　從而得到矩陣的迭代式</p><p><b>　　, 即DFP公式.</b></p><p><b>　　計(jì)算步驟: </b></p><p>　?。?）給定初始點(diǎn)及允許誤差, 令初始矩陣（單

47、位矩陣）</p><p>　　（2）求初始梯度向量, 若, 則停止迭代輸出. </p><p>　　否則, 轉(zhuǎn)向（3）. </p><p>　?。?）構(gòu)造初始DFP方向 </p><p>　　（4）進(jìn)行一維搜索, 通過(guò) , 確定最佳步長(zhǎng). </p><p>　　且令 </p><p

48、>　　（5）求梯度向量, 若</p><p>　　則停止迭代并輸出, 即為所求的近似解. </p><p>　　否則, 轉(zhuǎn)向（6）. </p><p>　?。?）構(gòu)造DFP方向</p><p>　　利用DFP公式計(jì)算,</p><p><b>　　取, 轉(zhuǎn)向（4）</b></p>

49、<p>　?。?）繼續(xù)迭代, 直到求出某點(diǎn)滿足精度要求為止. </p><p>　　在上述求解過(guò)程中, 如果迭代進(jìn)行n輪之后仍未停止, 則令新的起點(diǎn), 重新按DFP程序進(jìn)行搜索, 以避免計(jì)算誤差的積累而造成的影響. </p><p>　　3.4 BFGS法簡(jiǎn)介</p><p>　　BFGS法是Broyden，F(xiàn)letcher，Goldfarb和Sha

50、nno共同研究的變尺度法. </p><p>　　在DFP法中, 著眼于以構(gòu)造新矩陣來(lái)近似Hesse矩陣的逆, 而B(niǎo)FGS法就是換一種途徑, 構(gòu)造新矩陣來(lái)近似Hesse矩陣. 重復(fù)之前3.3.1討論, 可得到BFGS公式</p><p><b>　?。?.10）</b></p><p><b>　　也可表示為</b><

51、;/p><p><b>　　（3.11）</b></p><p>　　BFGS法的計(jì)算步驟與DPF法相同, 只需用BGFS公式取代DPF公式即可. </p><p>　　3.5 變尺度法的優(yōu)越性</p><p>　　在無(wú)約束優(yōu)化中, 最速下降法求解, 方法簡(jiǎn)便但收斂速度慢; Newton法求解雖然收斂速度快, 但需要計(jì)算二

52、階導(dǎo)數(shù)矩陣的逆矩陣, 計(jì)算工作量很大. </p><p>　　而變尺度法既具有收斂速度快的優(yōu)點(diǎn), 又不需計(jì)算二階導(dǎo)數(shù)矩陣, 計(jì)算量小. </p><p>　　例2 求解無(wú)約束非線性規(guī)劃問(wèn)題, 其中, 選取初始點(diǎn), 終止誤差. </p><p><b>　　1、用最速下降法</b></p><p><b>　　負(fù)

53、梯度方向</b></p><p><b>　　則令 </b></p><p><b>　　得 </b></p><p><b>　　故 </b></p><p>　　經(jīng)計(jì)算, 重復(fù)以上步驟, 需10輪迭代才可滿足誤差要求. </p><p>

54、<b>　　2、Newton法</b></p><p><b>　　需計(jì)算二階導(dǎo)數(shù)矩陣</b></p><p><b>　　故 </b></p><p><b>　　Newton方向 </b></p><p><b>　　得下一迭代點(diǎn) </

55、b></p><p>　　此時(shí) , 停止迭代. </p><p>　　3、變尺度法, 采用DFP法</p><p><b>　　初始搜索方向 </b></p><p><b>　　故 </b></p><p><b>　　于是 </b></

56、p><p>　　故不滿足終止誤差, 構(gòu)造下一輪DFP方向</p><p><b>　　由 </b></p><p><b>　　得 </b></p><p>　　根據(jù)DFP公式, 有</p><p><b>　　故DFP方向 </b></p>

57、<p><b>　　由</b></p><p><b>　　令</b></p><p><b>　　解得</b></p><p><b>　　則</b></p><p><b>　　滿足</b></p><

58、;p>　　停止迭代輸出, 即最優(yōu)解. </p><p>　　3.6 變尺度法的matlab實(shí)現(xiàn)</p><p>　　matlab的優(yōu)化工具箱對(duì)各種優(yōu)化問(wèn)題提供了的一個(gè)完整的解決方案. 其豐富的涵蓋范圍、簡(jiǎn)潔的函數(shù)表達(dá)、多種優(yōu)化算法的任意選擇、對(duì)算法參數(shù)的自由設(shè)置, 可使用戶方便靈活地使用優(yōu)化函數(shù). </p><p>　　根據(jù)文獻(xiàn)[8], 在優(yōu)化工具箱中,

59、fminunc函數(shù)和fminsearch函數(shù)用于求解無(wú)約束非線性最優(yōu)化問(wèn)題. </p><p>　　matlab中fminunc的基本命令是</p><p>　　[X,FVAL]=FMINUNC(FUN,X0,OPTIONS,P1,P2, ...)</p><p>　　其中的返回值X 是所求得的極小點(diǎn), FVAL 是函數(shù)的極小值, 其它返回值的含義參見(jiàn)相關(guān)的幫助.

60、FUN 是一個(gè)M 文件, 當(dāng)FUN只有一個(gè)返回值時(shí), 它的返回值是函數(shù)f (x)；當(dāng)FUN有兩個(gè)返回值時(shí), 它的第二個(gè)返回值是f (x)的梯度向量；當(dāng)FUN有三個(gè)返回值時(shí), 它的第三個(gè)返回值是f (x)的二階導(dǎo)數(shù)陣（Hessian 陣）. X0是向量x的初始值, OPTIONS 是優(yōu)化參數(shù), 可以使用缺省參數(shù). P1, P2 是可以傳遞給FUN 的一些參數(shù). </p><p>　　例3 求函數(shù)的最小值. <

61、/p><p>　　解：編寫M 文件fun2.m 如下：</p><p>　　function [f,g]=fun1(x);</p><p>　　f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;</p><p>　　g=[-400*x(1)*(x(2)-x(1)^2)-2*(1-x(1));200*(x(2)-x(1)^2)];&

62、lt;/p><p><b>　　輸入：</b></p><p>　　options = optimset('GradObj','on');</p><p>　　[x,y]=fminunc('fun1',rand(1,2),options)</p><p>　　即可求得函數(shù)的極小

63、值. x =1.0000 1.0000</p><p>　　y =1.0835e-022</p><p>　　求多元函數(shù)的極值也可以使用 Matlab 的fminsearch 命令, 其使用格式為</p><p>　　[X,FVAL,EXITFLAG,OUTPUT]＝FMINSEARCH(FUN,X0,OPTIONS,P1,P2,...)</p>

64、<p>　　例4 求函數(shù)取最小值時(shí)的x值. </p><p>　　解：編寫 f (x)的M 文件fun2.m如下：</p><p>　　function f=fun2(x);</p><p>　　f=sin(x)+3;</p><p><b>　　輸入：x0=2;</b></p><p&g

65、t;　　[x,y]=fminsearch(@fun2,x0)</p><p>　　即求得在初值2 附近的極小點(diǎn)及極小值</p><p><b>　　x =4.7124</b></p><p>　　y = 2.0000</p><p><b>　　4 變尺度法的改進(jìn)</b></p>&l

66、t;p>　　4.1 BFGS法的改進(jìn)</p><p>　　在變尺度校正公式中, DFP公式和BFGS公式是兩個(gè)非常著名的公式. 數(shù)學(xué)研究者運(yùn)用了大量數(shù)值實(shí)驗(yàn), 表明BFGS公式的數(shù)值穩(wěn)定性要優(yōu)于DFP公式, 故在實(shí)際計(jì)算中BFGS方法一般被認(rèn)為是變尺度方法中最有效的一種. 為了提高搜索效率, 很多人對(duì)BFGS公式提出了各種改進(jìn)形式.</p><p>　　根據(jù)（3.11）, BFG

67、S公式可表達(dá)為</p><p>　　1997年, Liao aiping在Byrd和Nocedal提供的工具框架下, 對(duì)BFGS法作了改進(jìn), 提出了一種雙參數(shù)修正的擬牛頓法, 具有更好的適應(yīng)性，其形式為</p><p><b>　　,</b></p><p><b>　　其中, . </b></p><

68、p>　　2003年, Xiao yunhai等人基于Wei zengxin提出的改進(jìn)方法中的, 將公式（3.11）中的第三項(xiàng)分子中的改為, 從而給出了另一種改進(jìn)形式,</p><p><b>　　.</b></p><p>　　2006年, Wei zengxin結(jié)合Liao的方法以及自己提出的方程, 同時(shí)結(jié)合廣義Wolfe準(zhǔn)則,也提出一種新的改進(jìn)形式, .&l

69、t;/p><p>　　綜合這些改進(jìn)形式, 方法大都是添加系數(shù), 或改變公式中的為, 或是用其它不精確線性搜索準(zhǔn)則進(jìn)行搜索. </p><p>　　4.2 改進(jìn)算法的推導(dǎo)</p><p>　　下面基于Wei zengxin提出的改進(jìn)方法對(duì)BFGS算法作改進(jìn).</p><p>　　令二次連續(xù)可微, 將其在處進(jìn)行Taylor展開(kāi), 得</p&g

70、t;<p><b>　　,</b></p><p><b>　　取, 有</b></p><p><b>　　,</b></p><p><b>　　可以推出</b></p><p><b>　　.</b></p&

71、gt;<p><b>　　令, , </b></p><p>　　用代替公式（3.11）的第三項(xiàng)分子中的, 得到改進(jìn)公式</p><p><b>　?。?.1）</b></p><p>　　4.3 改進(jìn)算法的步驟</p><p><b>　　算法步驟:</b>&

72、lt;/p><p>　?。?）選取初始數(shù)據(jù), 給定初始點(diǎn), 初始矩陣及終止誤差, 令 </p><p>　　（2）求初始梯度向量, 若, 則停止迭代輸出. </p><p>　　否則, 轉(zhuǎn)向（3）. </p><p>　?。?）求解線性方程組, 得到. </p><p>　　（4）由Wolfe-Powell型線性搜索確定最

73、佳步長(zhǎng). </p><p>　?。?）令, 若, 則停止迭代輸出.</p><p>　　否則由改進(jìn)公式（4.1）計(jì)算.</p><p>　　（6）令轉(zhuǎn)向（3）繼續(xù)迭代, 直到求出某點(diǎn)滿足精度要求為止. </p><p>　　下面給出Wolfe-Powell型線性搜索的定義及算法:</p><p>　　定義4.1 Wo

74、lfe-Powell型線性搜索, 即給定常數(shù), , 并且滿足, , 取步長(zhǎng), 使得不等式</p><p><b>　?。?.2）</b></p><p><b>　　（4.3）</b></p><p><b>　　同時(shí)成立. </b></p><p><b>　　Wo

75、lfe算法: </b></p><p>　　（1）給定初始數(shù)據(jù), , , , , </p><p>　?。?）令, 計(jì)算, .</p><p>　?。?）若滿足（4.2）和（4.3）, 則;</p><p>　　若不滿足（4.2）, 則令, , 不變, 轉(zhuǎn)向（2）.</p><p>　　若滿足（4.2）,但

76、不滿足（4.3）, 則令, , 不變, 轉(zhuǎn)向（2）.</p><p>　　4.4 算法的數(shù)值對(duì)比</p><p>　　以問(wèn)題為例. 其中, 給定終止誤差. </p><p>　　用matlab編寫如下:</p><p>　　function [X,K]=mbfgs(X1,m,n)</p><p>　　X1=input

77、('X1=');m=input('m=');n=input('n=');eps=10^(- 6);</p><p>　　syms x1 x2;</p><p>　　f=inline('100*(x2- x1^2)^2+(1- x1)^2');</p><p>　　g1=inline('- 400

78、*(x2- x1^2)*x1-2+2*x1');</p><p>　　g2=inline('200*x2- 200*x1^2');</p><p>　　B=eye(2);i=0;X=ones(2,1);</p><p>　　while norm([g1(X1(1),X1(2)),g2(X1(1),X1(2))])>eps</p&g

79、t;<p>　　p=pinv(B)*(- [g1(X1(1),X1(2)),g2(X1(1),X1(2))]');t=1;a=0;b=inf;</p><p><b>　　while 1</b></p><p><b>　　T=X1+t*p;</b></p><p>　　if f(T(1),T(2))

80、>f(X1(1),X1(2))+m*t*[g1(X1(1),X1(2)),g2(X1(1),X1(2))]*p</p><p>　　b=t; t=(1/2)*(t+a);</p><p><b>　　continue</b></p><p><b>　　end;</b></p><p>　　i

81、f [g1(T(1),T(2)),g2(T(1),T(2))]*p<n*[g1(X1(1),X1(2)),g2(X1(1),X1(2))]*p</p><p>　　a=t; t=min(2*t,(1/2)*(t+b));</p><p>　　else break; </p><p><b>　　end; </b></p>&

82、lt;p><b>　　end;</b></p><p>　　X2=X1+t*p; Y=[g1(X2(1),X2(2))- g1(X1(1),X1(2)),g2(X2(1),X2(2))- g2(X1(1),X1(2))]'; S=X2-X1;</p><p>　　W=2*(f(X1(1),X1(2))- f(X2(1),X2(2)))+[g1(X2(1)

83、,X2(2))+g1(X1(1),X1(2)),g2(X2(1),X2(2))+g2(X1(1),X1(2))]*S;</p><p>　　A=(W/(norm(S)^2))*eye(2);</p><p>　　B=B-(B*S*S'*B)/(S'*B*S)+(Y*Y')/(S'*Y)+(Y*(A*S)'+A*S*Y'+A*S*(A*S)&#

84、39;)/(S'*Y);</p><p>　　X1=X2;i=i+1;</p><p><b>　　end; </b></p><p><b>　　X=X1 </b></p><p><b>　　K=i</b></p><p>　　取不同的的初始

85、點(diǎn)進(jìn)行計(jì)算, 可設(shè), , 得出結(jié)果, 并與BFGS算法作對(duì)比, 得出下表</p><p>　　表4.1 算法迭代次數(shù)對(duì)比</p><p>　　可以看出, 改進(jìn)后的算法同樣具有精確性, 且收斂速度更快. </p><p><b>　　小結(jié)</b></p><p>　　隨著社會(huì)的不斷發(fā)展, 經(jīng)濟(jì)的進(jìn)步, 人類已越來(lái)越意識(shí)到資

86、源的合理配置、效率提高的重要性, “優(yōu)化設(shè)計(jì)”這個(gè)詞語(yǔ)已在各個(gè)領(lǐng)域上到處可見(jiàn). 現(xiàn)代的優(yōu)化方法, 研究某些數(shù)學(xué)上定義的問(wèn)題的, 利用計(jì)算機(jī)為計(jì)算工具的最優(yōu)解. 無(wú)約束優(yōu)化的變尺度算法的應(yīng)用前景極為可觀. </p><p>　　本文首先介紹了無(wú)約束優(yōu)化極值點(diǎn)存在的條件以及最基礎(chǔ)的求解方法, 之后詳細(xì)研究了變尺度算法的原理和計(jì)算步驟, 并通過(guò)對(duì)比計(jì)算證明了算法的優(yōu)越性. 最后基于Wei zengxin提出的改進(jìn)BFG

87、S公式, 研究了一類改進(jìn)變尺度算法的原理, 且通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證其收斂性及優(yōu)勢(shì). </p><p><b>　　參考文獻(xiàn)</b></p><p>　　Courant, R., Variational methods for the solution of problems of equilibrium and vibrations [J], Bulletin of t

88、he American Mathematical Society, 1943, 49: 1-23.</p><p>　　鄧乃楊. 無(wú)約束最優(yōu)化計(jì)算方法 [M]. 科學(xué)出版社, 1982: 1-13.</p><p>　　朱儒楷, 黃皓, 朱開(kāi)永編著. 非線性規(guī)劃 [M]. 中國(guó)礦業(yè)大學(xué)出版社, 1990: 132-133.</p><p>　　Aiping Liao

89、. Modifying the BFGS method [J]. Operations Research Letters, 1997, 20: 171-177.</p><p>　　胡毓達(dá). 非線性規(guī)劃 [M]. 高等教育出版社, 1990: 7-10.</p><p>　　運(yùn)籌學(xué)教材編寫組. 運(yùn)籌學(xué) [M]. 第三版. 清華大學(xué)出版社, 2005: 133-170.</p>

90、<p>　　費(fèi)培之編著. 線性和非線性規(guī)劃引論極其應(yīng)用 [M]. 四川大學(xué)出版社, 1989: 204-214.</p><p>　　李濤. Matlab工具箱應(yīng)用指南:應(yīng)用數(shù)學(xué)篇 [M]. 電子工業(yè)出版社, 2000: 212-215.</p><p>　　Xiao Yunhai and Yehun, A modified BFGS method with global co

91、nvergence for unconstrained optimization problems, Guangxi Sciences, 2003(10): 253-257.</p><p>　　Wei Zengxin, Li Guoyin, Qi Liqun, New Quasi-Newton methods for unconstrained optimization problems, Applied Ma