資源描述：
《最優(yōu)化概述 - 副本》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、一.引言最優(yōu)化理論與算法是一個重要的數學分支,又稱數學規(guī)劃,它所研究的是討論在解決問題的眾多方案中什么樣的方案最優(yōu),以及怎樣找出最優(yōu)方案.其中尋找最優(yōu)方案的方法叫最優(yōu)化方法（算法）,這種方法的數學理論即為最優(yōu)化理論.它在生活中的應用隨處可見.比如,在網上買東西,人們會在各家店中進行性價比的比較,以及根據店家的優(yōu)惠方法選擇最實惠的購選方式;人們出門選擇最優(yōu)的交通工具;還有飲食搭配等等,這些都是一些常見及簡單問題的選擇.但對于相對復雜的設計問題最優(yōu)方案的選擇.我們首先要把設計問題轉化為數學模型,即用數學表達式描述設計問題;然后,按照數學模型的特點選擇優(yōu)化設計方法及其計算程序,運用計算
2、機求解最優(yōu)解,即最優(yōu)設計方案.對較復雜的問題進行優(yōu)化設計,本質上是根據優(yōu)化設計理論,采用優(yōu)化設計算法,運用計算機高質量高速度的完成設計任務.所以,這就對優(yōu)化設計的理論及算法提出了很多的要求.目前,對于最優(yōu)化理論大致分為無約束最優(yōu)化及有約束最優(yōu)化問題兩大類.而對于它們的解,我們多數情況下得到的都是局部最優(yōu)解,而對于求解具有全局收斂性的全局最優(yōu)解的方法尚不完善,還有待進一步探討.其中,對于無約束最優(yōu)化問題的求解方法有:線性搜索方法、最速下降法、Newton法、擬Newton法、共軛梯度法、信賴域算法、直接法.而對于約束最優(yōu)化問題的求解方法有:單純形法、有效集法、罰函數法、乘子法、可行
3、方向法、序列二次規(guī)劃算法.在本文中,主要介紹了共軛梯度法、信賴域算法、Powell直接法、乘子法、zoutendijk可行方向法的具體算法及一些其他優(yōu)化算法的區(qū)別.最后,對優(yōu)化算法的前景提出了展望.二.最優(yōu)化問題的求解方法1.無約束最優(yōu)化問題對于無約束最優(yōu)化問題的求解方法的主導思想是下降算法,而它的基本思想是從某個初始點出發(fā),按照使目標函數值下降的原則構造點列,最終求得問題的最優(yōu)解.15下降算法的一般步驟:步一:給定初始點,精度.令.步二:若,則終止算法,得解.否則，轉步三.步三:確定下降方向,使得.步四:確定步長,使得.步五:令,,轉步二.1.1下降算法中步長與下降方向依次進行
4、1.1.1線性搜索方法線性搜索方法又分為精確線性搜索與非精確線性搜索.它主要解決的問題是下降算法所涉及到的步長的確定問題.精確線性搜索的最簡單的方法就是黃金分割法（0.618法）.它主要適用于求解一元單峰函數的極小值問題.其基本思想是構造閉區(qū)間序列,滿足,且區(qū)間的長度按比例縮小.從而最終使得,由此可得.黃金分割法步驟:步0:確定包含極小值點的初始單峰區(qū)間,精度.令.取.令步1:若,則得.停止計算.步2:若,則令令轉步0.步3:若,則令.計算轉步1.步4:若,則令.15計算.轉步1.非精確線性搜索的最簡單的方法有Armijo型線性搜索與Wolf-Powell型線性搜索.它們與精確線
5、性搜索的區(qū)別在于,精確線性搜索要求步長取到一元函數的最小值,計算量較大.而它們只需步長使得一元函數在與步長值相同的點處的函數值較初始點的函數值有一定的下降量即可.其中Wolf-Powell型線性搜索是對Armijo型線性搜索中由于試探步的大小不確定問題所帶來缺陷的進一步完善.1.1.2下降方向的確定方法及差異在用線性搜索方法確定了下降算法中的下降量即步長后,可根據最速下降法、Newton法、擬牛頓法、共軛梯度法的具體步驟確定下降方向并最終求得問題的解.最速下降法是將負梯度方向即作為下降方向,Newton法的下降方向是,擬牛頓法只是用去代替Newton法中的以保證方向的下降性.共軛
6、梯度法應用的是共軛方向.下降方向確定后就可根據線性搜索確定的步長及下降算法的基本步驟求解問題.在這些求解方法中,最大的不同就在于下降方向的確定上,其次在于算法的收斂快慢.最速下降法在求解二次函數極小值時具有線性收斂速度且具有較少的存儲量,而牛頓法在求解問題時具有二次收斂性,但該算法要求對所有的k,正定.否則,就不能確保它所確定的方向是下降方向.對此問題,修正牛頓法對其進行了改善,用矩陣代替牛頓法中的進行問題的求解.對于牛頓法中存在的問題,修正牛頓法雖然克服了,但它又引入了新的問題,即當參數過小時,仍不能保證下降方向的正確性,當過大時又會影響收斂速度.而且不管是牛頓法還是修正牛頓法
7、都需計算目標函數的二階導.對于它們所存在的問題,擬牛頓法都可克服,且具有較快的收斂速度-超線性收斂速度.其基本思想是:在牛頓法的子問題中用的某個近似矩陣取代.其中近似矩陣應具有如下三個特點:（1）在某種意義下,使相應的算法產生的方向是牛頓方向的近似,以保證算法具有較快的收斂速度:（2）對所有的k,近似矩陣15對稱正定,從而使得算法產生的方向是目標函數在處的下降方向.（3）近似矩陣容易計算.然而,擬牛頓法也不是最完善的,雖然它具有較快的收斂速度,但要不停的存儲近似矩陣,因而，在求解
