最優(yōu)化概述 - 副本

《最優(yōu)化概述 - 副本》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、一.引言最優(yōu)化理論與算法是一個重要的數(shù)學(xué)分支,又稱數(shù)學(xué)規(guī)劃,它所研究的是討論在解決問題的眾多方案中什么樣的方案最優(yōu),以及怎樣找出最優(yōu)方案.其中尋找最優(yōu)方案的方法叫最優(yōu)化方法（算法）,這種方法的數(shù)學(xué)理論即為最優(yōu)化理論.它在生活中的應(yīng)用隨處可見.比如,在網(wǎng)上買東西,人們會在各家店中進(jìn)行性價比的比較,以及根據(jù)店家的優(yōu)惠方法選擇最實(shí)惠的購選方式;人們出門選擇最優(yōu)的交通工具;還有飲食搭配等等,這些都是一些常見及簡單問題的選擇.但對于相對復(fù)雜的設(shè)計(jì)問題最優(yōu)方案的選擇.我們首先要把設(shè)計(jì)問題轉(zhuǎn)化為數(shù)學(xué)模型,即用數(shù)學(xué)表達(dá)式描述設(shè)計(jì)問題;然后,按照數(shù)學(xué)模型的特點(diǎn)選擇優(yōu)化設(shè)計(jì)方法及其計(jì)算程序,運(yùn)用計(jì)算機(jī)求解最

2、優(yōu)解,即最優(yōu)設(shè)計(jì)方案.對較復(fù)雜的問題進(jìn)行優(yōu)化設(shè)計(jì),本質(zhì)上是根據(jù)優(yōu)化設(shè)計(jì)理論,采用優(yōu)化設(shè)計(jì)算法,運(yùn)用計(jì)算機(jī)高質(zhì)量高速度的完成設(shè)計(jì)任務(wù).所以,這就對優(yōu)化設(shè)計(jì)的理論及算法提出了很多的要求.目前,對于最優(yōu)化理論大致分為無約束最優(yōu)化及有約束最優(yōu)化問題兩大類.而對于它們的解,我們多數(shù)情況下得到的都是局部最優(yōu)解,而對于求解具有全局收斂性的全局最優(yōu)解的方法尚不完善,還有待進(jìn)一步探討.其中,對于無約束最優(yōu)化問題的求解方法有:線性搜索方法、最速下降法、Newton法、擬Newton法、共軛梯度法、信賴域算法、直接法.而對于約束最優(yōu)化問題的求解方法有:單純形法、有效集法、罰函數(shù)法、乘子法、可行方向法、序列二次

3、規(guī)劃算法.在本文中,主要介紹了共軛梯度法、信賴域算法、Powell直接法、乘子法、zoutendijk可行方向法的具體算法及一些其他優(yōu)化算法的區(qū)別.最后,對優(yōu)化算法的前景提出了展望.二.最優(yōu)化問題的求解方法1.無約束最優(yōu)化問題對于無約束最優(yōu)化問題的求解方法的主導(dǎo)思想是下降算法,而它的基本思想是從某個初始點(diǎn)出發(fā),按照使目標(biāo)函數(shù)值下降的原則構(gòu)造點(diǎn)列,最終求得問題的最優(yōu)解.15下降算法的一般步驟:步一:給定初始點(diǎn),精度.令.步二:若,則終止算法,得解.否則，轉(zhuǎn)步三.步三:確定下降方向,使得.步四:確定步長,使得.步五:令,,轉(zhuǎn)步二.1.1下降算法中步長與下降方向依次進(jìn)行1.1.1線性搜索方法線

4、性搜索方法又分為精確線性搜索與非精確線性搜索.它主要解決的問題是下降算法所涉及到的步長的確定問題.精確線性搜索的最簡單的方法就是黃金分割法（0.618法）.它主要適用于求解一元單峰函數(shù)的極小值問題.其基本思想是構(gòu)造閉區(qū)間序列,滿足,且區(qū)間的長度按比例縮小.從而最終使得,由此可得.黃金分割法步驟:步0:確定包含極小值點(diǎn)的初始單峰區(qū)間,精度.令.取.令步1:若,則得.停止計(jì)算.步2:若,則令令轉(zhuǎn)步0.步3:若,則令.計(jì)算轉(zhuǎn)步1.步4:若,則令.15計(jì)算.轉(zhuǎn)步1.非精確線性搜索的最簡單的方法有Armijo型線性搜索與Wolf-Powell型線性搜索.它們與精確線性搜索的區(qū)別在于,精確線性搜索要

5、求步長取到一元函數(shù)的最小值,計(jì)算量較大.而它們只需步長使得一元函數(shù)在與步長值相同的點(diǎn)處的函數(shù)值較初始點(diǎn)的函數(shù)值有一定的下降量即可.其中Wolf-Powell型線性搜索是對Armijo型線性搜索中由于試探步的大小不確定問題所帶來缺陷的進(jìn)一步完善.1.1.2下降方向的確定方法及差異在用線性搜索方法確定了下降算法中的下降量即步長后,可根據(jù)最速下降法、Newton法、擬牛頓法、共軛梯度法的具體步驟確定下降方向并最終求得問題的解.最速下降法是將負(fù)梯度方向即作為下降方向,Newton法的下降方向是,擬牛頓法只是用去代替Newton法中的以保證方向的下降性.共軛梯度法應(yīng)用的是共軛方向.下降方向確定后就

6、可根據(jù)線性搜索確定的步長及下降算法的基本步驟求解問題.在這些求解方法中,最大的不同就在于下降方向的確定上,其次在于算法的收斂快慢.最速下降法在求解二次函數(shù)極小值時具有線性收斂速度且具有較少的存儲量,而牛頓法在求解問題時具有二次收斂性,但該算法要求對所有的k,正定.否則,就不能確保它所確定的方向是下降方向.對此問題,修正牛頓法對其進(jìn)行了改善,用矩陣代替牛頓法中的進(jìn)行問題的求解.對于牛頓法中存在的問題,修正牛頓法雖然克服了,但它又引入了新的問題,即當(dāng)參數(shù)過小時,仍不能保證下降方向的正確性,當(dāng)過大時又會影響收斂速度.而且不管是牛頓法還是修正牛頓法都需計(jì)算目標(biāo)函數(shù)的二階導(dǎo).對于它們所存在的問題,

7、擬牛頓法都可克服,且具有較快的收斂速度-超線性收斂速度.其基本思想是:在牛頓法的子問題中用的某個近似矩陣取代.其中近似矩陣應(yīng)具有如下三個特點(diǎn):（1）在某種意義下,使相應(yīng)的算法產(chǎn)生的方向是牛頓方向的近似,以保證算法具有較快的收斂速度:（2）對所有的k,近似矩陣15對稱正定,從而使得算法產(chǎn)生的方向是目標(biāo)函數(shù)在處的下降方向.（3）近似矩陣容易計(jì)算.然而,擬牛頓法也不是最完善的,雖然它具有較快的收斂速度,但要不停的存儲近似矩陣,因而，在求解