無約束優(yōu)化法.doc

《無約束優(yōu)化法.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第三章無約束優(yōu)化法l概述l梯度法l牛頓法l共軛梯度法l坐標(biāo)輪換法l鮑威爾法概述無約束優(yōu)化問題的一般形式：求設(shè)計(jì)變量使目標(biāo)函數(shù)，對沒有任何約束條件。工程實(shí)際問題中，無約束結(jié)構(gòu)優(yōu)化問題很少，多數(shù)是有約束條件的。學(xué)習(xí)無約束結(jié)構(gòu)優(yōu)化原因：1）工程也有少量無約束結(jié)構(gòu)優(yōu)化問題，其數(shù)學(xué)模型就是無約束優(yōu)化問題，除了在非常接近最小點(diǎn)的情況下，可以按無約束問題處理；2）為研究約束優(yōu)化問題打下基礎(chǔ)；3）約束優(yōu)化問題可以通過一系列無約束方法達(dá)到。無約束優(yōu)化問題的求解，可以直接應(yīng)用函數(shù)極值問題的求解方程：的問題，即求，使其滿足：個(gè)方程組，一般為非線性的，很難用解析方法求解，一般采用數(shù)值方法

2、。與其用數(shù)值方法求解非線性方程組，倒不如用數(shù)值方法直接求解無約束極值問題。數(shù)值方法最常用的就是搜索法，其基本思想：從給定的初始點(diǎn)出發(fā)，按照一定原則尋找搜索方向，沿方向進(jìn)行搜索，確定最佳步長，使得函數(shù)沿方向下降最快，依次形成迭代公式：各種無約束優(yōu)化方法的區(qū)別在于確定搜索方向的方法，這是無約束優(yōu)化方法的關(guān)鍵。根據(jù)構(gòu)成搜索方向所使用的信息不同分為：（1）間接法利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)，如梯度法（最速下降法）、牛頓法、共軛梯度法和變尺度法；（1）直接法直接利用目標(biāo)函數(shù)，如坐標(biāo)輪換法、鮑威爾法和單形替換法。梯度法最早由1847年柯西提出，是無約束優(yōu)化的基本方法。其基本思

3、想：取目標(biāo)函數(shù)的負(fù)梯度方向作為迭代的搜索方向，必使函數(shù)值下降的速度最快。設(shè)在第次迭代中取得迭代點(diǎn)，從該點(diǎn)出發(fā)，取負(fù)梯度方向:為搜索方向，式中：第次得到的新點(diǎn)：一般步長常采用沿負(fù)梯度方向做一維搜索：算法特點(diǎn)：初始階段改進(jìn)較快，最優(yōu)解附近改進(jìn)較慢。具體迭代步驟：1.選擇初始點(diǎn)及迭代精度，令迭代次數(shù)；2.計(jì)算點(diǎn)的梯度及梯度的模，并令3.判斷是否滿足收斂精度。一般情況下，若，則為近似最優(yōu)點(diǎn)，為近似最優(yōu)值，可以輸出最優(yōu)解，，否則進(jìn)行4.4.從點(diǎn)出發(fā)，沿負(fù)梯度方向求最優(yōu)步長，及沿進(jìn)行一維搜索，求得使函數(shù)下降最多的步長因子1.確定新的近似點(diǎn)，此點(diǎn)也就是下次迭代的出發(fā)點(diǎn)令，轉(zhuǎn)入2

4、步。例題：梯度法的特點(diǎn)：1.理論明確，方法簡單，概念清楚，計(jì)算量小，對初始點(diǎn)沒有嚴(yán)格要求。2.相鄰兩次迭代的梯度方向是相互正交的，搜索線路呈直角鋸齒形，越靠近極小點(diǎn)，搜索密度越大，收斂越慢。3.迭代次數(shù)與目標(biāo)函數(shù)等值線的形狀有關(guān)，目標(biāo)函數(shù)若為橢圓族越扁，迭代次數(shù)越多，搜索到最優(yōu)點(diǎn)的難度越大。4.習(xí)題一：試用梯度法求目標(biāo)函數(shù)的極小值，設(shè)初始點(diǎn)，。習(xí)題二：試用梯度法求目標(biāo)函數(shù)的最優(yōu)解。初始點(diǎn)，迭代精度。牛頓法牛頓法的基本思想就是利用二次函數(shù)來代替原目標(biāo)函數(shù)，以二次函數(shù)的極小點(diǎn)作為原目標(biāo)函數(shù)的極小點(diǎn)的近似，并逐步逼近該點(diǎn)。設(shè)一般目標(biāo)函數(shù)具有一、二階偏導(dǎo)數(shù)，此時(shí)，在處做泰

5、勒展開并取值二次項(xiàng)，得：其中為在的海森矩陣，是對稱方陣。求的極小問題轉(zhuǎn)換為的極小值問題。令，即：若為正定，解得：由于在極小點(diǎn)附近，作為極小點(diǎn)的下一個(gè)近似點(diǎn)其中：搜索方向步長恒為1。例題：以上例子說明，牛頓法比最速下降法收斂快習(xí)題三：用牛頓法求目標(biāo)函數(shù)的極小點(diǎn)和極小值。取初始點(diǎn)習(xí)題四：用牛頓法求的最優(yōu)解，取初始點(diǎn)，迭代精度。修正牛頓法其步牛頓法特點(diǎn)如果是對稱正定矩陣A的二次函數(shù)，則用牛頓法經(jīng)過一次迭代，就可達(dá)到最優(yōu)點(diǎn),如不是二次函數(shù)，則牛頓法不能一步達(dá)到極值點(diǎn)，但由于這種函數(shù)在極值點(diǎn)附近和二次函數(shù)很近似，因此牛頓法的收斂速度還是很快的。牛頓法的收斂速度雖然較快，但要

6、求海森矩陣要可逆，要計(jì)算二階導(dǎo)數(shù)和逆矩陣，就加大了計(jì)算機(jī)計(jì)算量和存儲(chǔ)量。習(xí)題五：用阻尼牛頓法求函數(shù)的最優(yōu)解，取初始點(diǎn)，迭代精度。共軛方向法和共軛梯度法共軛方向概念共軛方向的概念是在研究二次函數(shù)過程中引出的。考慮二維情形，如果按最速下降法，選擇負(fù)梯度方向?yàn)樗阉鞣较?，?huì)產(chǎn)生鋸齒現(xiàn)象；為避免鋸齒的發(fā)生，取下一次的迭代搜索方向直接指向極小點(diǎn)，如果選定這樣的搜索方向，對于二元二次函數(shù)只需進(jìn)行兩次直線搜索就可以求到極小點(diǎn)。初選初始點(diǎn)沿某個(gè)下降方向做一維搜索，得是沿方向搜索的最佳步長，即在點(diǎn)處的函數(shù)沿方向的方向?qū)?shù)為零?？紤]到點(diǎn)處方向?qū)?shù)與梯度之間的關(guān)系，有：為避免鋸齒現(xiàn)象，下

7、一次迭代搜索方向指向極小點(diǎn)其中為方向的最佳步長。這樣的滿足什么條件？對于二次函數(shù)在處取得極小點(diǎn)的必要條件：即：上式兩邊左乘得：滿足上式的兩個(gè)量和稱為的共軛向量，或稱和對是共軛方向。G是n×n對稱正定矩陣，方向向量d1,d2,···,dm的m≤n.如果：稱方向向量d1,d2,···,dm關(guān)于G的共軛方向共軛方向性質(zhì)：1），，。。。關(guān)于共軛，這些向量是線性無關(guān)的；2）在N維空間中相互共軛的向量個(gè)數(shù)不超過N個(gè)；3）若是單位矩陣，則，，。。。相互垂直正交；共軛方向法步驟：1.選定初始點(diǎn)，下降方向和收斂精度，迭代次數(shù)；2.沿方向進(jìn)行一維搜索，得；3.判斷是否滿足，若滿足則打

8、印輸出；否