第四章無約束優(yōu)化方法

1、.,第四章無約束優(yōu)化方法,第一節(jié) 概述,從第一章列舉的機(jī)械設(shè)計(jì)問題，大多數(shù)實(shí)際問題是約束優(yōu)化問題。,約束優(yōu)化問題的求解轉(zhuǎn)化為一系列的無約束優(yōu)化問 題實(shí)現(xiàn)的。,因此，無約束優(yōu)化問題的解法是優(yōu)化設(shè)計(jì)方法的基本組 成部分，也是優(yōu)化方法的基礎(chǔ)。,無約束優(yōu)化問題的極值條件,.,解析法,數(shù)值法,數(shù)學(xué)模型復(fù)雜時(shí)不便求解,可以處理復(fù)雜函數(shù)及沒有數(shù)學(xué)表達(dá)式 的優(yōu)化設(shè)計(jì)問題,搜索方向問題是無約束優(yōu)化方法的關(guān)鍵。,各種無約束優(yōu)化方法的區(qū)別：確定搜索方向的方法不同。,無約束優(yōu)化方法分類,利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù),利用目標(biāo)函數(shù)值,（最速下降法、共軛梯度法、牛頓法）,（坐標(biāo)輪換法、鮑威爾等）,.,.,第二節(jié) 最速下降

2、法,優(yōu)化設(shè)計(jì)追求目標(biāo)函數(shù)值最小，若搜索方向取該點(diǎn)的負(fù)梯度 方向，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快。,按此規(guī)律不斷走步，形成以下迭代算法：,以負(fù)梯度方向?yàn)樗阉鞣较?，所以稱最速下降法或梯度法。,搜索方向確定為負(fù)梯度方向，還需確定步長因子,即求一維搜索的最佳步長，既有,.,由此可知，在最速下降法中，相鄰兩個(gè)迭代點(diǎn)上的函數(shù) 梯度相互垂直。而搜索方向就是負(fù)梯度方向，因此相鄰 兩個(gè)搜索方向互相垂直。,.,.,.,.,第三節(jié)牛頓型方法,在第三章中，我們已經(jīng)討論了一維搜索的牛頓方法。,得出一維情況下的牛頓迭代公式,對(duì)于多元函數(shù)，在,泰勒展開，得,.,這是多元函數(shù)求極值的牛頓法迭代公式。,對(duì)牛頓法進(jìn)行改進(jìn)，提

3、出“阻尼牛頓法”,.,.,第四節(jié)共軛方向及共軛方向法,為了克服最速下降法的鋸齒現(xiàn)象，提高收斂速度，發(fā)展了 一類共軛方向法。搜索方向是共軛方向。,一、共軛方向的概念,共軛方向的概念是在研究二次函數(shù),時(shí)引出的。,首先考慮二維情況,.,如果按最速下降法，選擇負(fù)梯度方向?yàn)樗阉鞣较颍瑫?huì)產(chǎn)生鋸齒現(xiàn)象。,為避免鋸齒的發(fā)生，取下一次的迭代搜索方向直接指向極 小點(diǎn)，如果選定這樣的搜索方向，對(duì)于二元二次函數(shù)只需 進(jìn)行兩次直線搜索就可以求到極小點(diǎn)。,.,應(yīng)滿足什么條件？,對(duì)于二次函數(shù) 在 處取得極小點(diǎn)的必要條件,等式兩邊同乘 得,是對(duì)G的共軛方向。,.,三、共軛方向法,1、選定初始點(diǎn) ，下降方向 和收斂精度，k=0

4、。,2、沿 方向進(jìn)行一維搜索，得,3、判斷 是否滿足，若滿足則打印,否則轉(zhuǎn)4。,4、提供新的共軛方向 ，使,5、置 ，轉(zhuǎn)2。,.,.,第五節(jié) 共軛梯度法,共軛梯度法是共軛方向法的一種，共軛向量有迭代點(diǎn) 的負(fù)梯度構(gòu)造出來，所以稱共軛梯度法。,從點(diǎn) 出發(fā)，沿G某一共軛方向 作一維搜索,到達(dá),而在點(diǎn) 、 處的梯度分別為：,.,.,圖4-9 共軛梯度法的幾何說明,.,.,第六節(jié)變尺度法,變尺度法的基本思想：,前面討論的梯度法和牛頓法，它們的迭代公式可以看作下列 公式的特例。,變尺度法是對(duì)牛頓法的修正，它不是計(jì)算二階導(dǎo)數(shù)的矩陣和 它的逆矩陣，而是設(shè)法構(gòu)造一個(gè)對(duì)稱正定矩陣H來代替Hesse 矩陣的逆矩陣。

5、并在迭代過程中，使其逐漸逼近H-1 。,由于對(duì)稱矩陣H在迭代過程中是不斷修正改變的，它對(duì)于一 般尺度的梯度起到改變尺度的作用，因此H又稱變尺度矩陣。,.,一、尺度矩陣的概念,變量的尺度變換是放大或縮小各個(gè)坐標(biāo)。,通過尺度變換可以把函數(shù)的偏心程度降低到最低限度。,對(duì)于一般二次函數(shù),如果進(jìn)行尺度變換,.,則在新的坐標(biāo)系中，函數(shù)的二次項(xiàng)變?yōu)?選擇這樣變換的目的：降低二次項(xiàng)的偏心程度。,若矩陣G是正定的，則總存在矩陣Q使,使得函數(shù)偏心度變?yōu)榱恪?用Q-1 右乘等式兩邊，得,再用Q左乘等式兩邊，得,所以,.,說明二次函數(shù)矩陣G的逆矩陣，可以通過尺度變換矩陣Q 求得。,這樣，牛頓法迭代過程中的牛頓方向可寫

6、成：,三、變尺度法的一般步驟,.,.,第七節(jié) 坐標(biāo)輪換法,坐標(biāo)輪換法是每次搜索只允許一個(gè)變量變化，其余變量保持 不變，即沿坐標(biāo)方向輪流進(jìn)行搜索的尋優(yōu)方法。,它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量的優(yōu)化問題。,因此又稱變量輪換法。,其基本原理是將一個(gè)多維的無約束最優(yōu)化問題轉(zhuǎn)化為一系列較低維的最優(yōu)化問題來求解，簡單地說，就是先將(n-1)個(gè)變量固定不動(dòng)，只對(duì)第一個(gè)變量進(jìn)行一維搜索得到最優(yōu)點(diǎn)x1（1）。然后，又保持(n-1)個(gè)變量不變，再對(duì)第二個(gè)變量進(jìn)行一維搜索到x2（1）等等。,.,.,圖412 坐標(biāo)輪換法原理圖（動(dòng)畫演示）,.,2. 搜索方向與步長的確定,（1）搜索方向的確定,對(duì)于第k輪第i次的

7、計(jì)算,第k輪第I次的迭代方向，它輪流取n維坐標(biāo)的單位向量。,.,3.搜索步長的確定,關(guān)于 值通常有以下幾種取法 （1）加速步長法 （2）最優(yōu)步長法 最優(yōu)步長法就是利用一維最優(yōu)搜索方法來完成每一次迭代，即 此時(shí)可以采用0.618方法或二次插值方法來計(jì)算 的值。,.,圖413 加速步長法的搜索路線,.,圖414 最優(yōu)步長法的搜索路線,.,4 . 坐標(biāo)輪換法存在的問題,圖415 坐標(biāo)輪換法在各種不同情況下的效能 （a）搜索有效；（b）搜索低效；（c）搜索無效,.,第八節(jié) Powell法（方向加速法）,Powell法是利用共軛方向可以加速收斂的性質(zhì)所形成的一種搜索算法。,一、共軛方向的生成,.,.,二、基本算法,.,