結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法

1、結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 3.4 無(wú)約束優(yōu)化方法 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 3.4.1 概述 大多數(shù)實(shí)際問(wèn)題是約束優(yōu)化問(wèn)題。 約束優(yōu)化問(wèn)題的求解轉(zhuǎn)化為一系列的無(wú)約束優(yōu) 化問(wèn)題實(shí)現(xiàn)。 因此，無(wú)約束優(yōu)化問(wèn)題的解法是優(yōu)化設(shè)計(jì)方法的基本 組成部分，也是優(yōu)化方法的基礎(chǔ)。 * 0f x 無(wú)約束優(yōu)化問(wèn)題的極值條件 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 解析法 數(shù)值法 數(shù)學(xué)模型復(fù)雜時(shí)不便求解 可以處理復(fù)雜函數(shù)及沒(méi)有數(shù)學(xué)表達(dá)式 的優(yōu)化設(shè)計(jì)問(wèn)題 1kkk k xxa d 搜索方向問(wèn)題是無(wú)約束優(yōu)化方法的關(guān)鍵。 各種無(wú)約束優(yōu)化方法的區(qū)別：確定搜索方向的方法不同。 無(wú)約束優(yōu)化方法分類(lèi) 利用目標(biāo)函數(shù)的一階或二

2、階導(dǎo)數(shù) 利用目標(biāo)函數(shù)值 （最速下降法、共軛梯度法、牛頓法） （坐標(biāo)輪換法、鮑威爾等） 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 3.4.2 最速下降法 優(yōu)化設(shè)計(jì)追求目標(biāo)函數(shù)值最小，若搜索方向取該點(diǎn)的負(fù)梯度 方向，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快。 按此規(guī)律不斷走步，形成以下迭代算法： 1kkk k xxaf x 以負(fù)梯度方向?yàn)樗阉鞣较?，所以稱(chēng)最速下降法最速下降法或梯度法梯度法。 搜索方向確定為負(fù)梯度方向，還需確定步長(zhǎng)因子 k a 即求一維搜索的最佳步長(zhǎng)，既有 1 minmin kkkkk kk fxfxafxfxafx 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 0 T kk

3、k k fxafxfx 1 0 T kk f xf x 1 0 T kk dd 由此可知，在最速下降法中，相鄰兩個(gè)迭代點(diǎn)上的相鄰兩個(gè)迭代點(diǎn)上的 函數(shù)梯度相互垂直函數(shù)梯度相互垂直。而搜索方向就是負(fù)梯度方向， 因此相鄰兩個(gè)搜索方向互相垂直。 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 例4-1 求目標(biāo)函數(shù) 22 12 25f xxx 的極小點(diǎn)。 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 3.4.3 牛頓型方法 前面討論了一維搜索的牛頓方法。得出一維情況下的牛頓 迭代公式 1 k kk k fx xx fx 對(duì)于多元函數(shù)，在 k x泰勒展開(kāi)，得 f

4、xx 2 1 2 TT kkkkkk f xf xxxxxf xxx 設(shè) 1k x 為函數(shù)的極小點(diǎn)，根據(jù)極值的必要條件 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 1 0 k x 21 0 kkkk f xf xxx 1 12kkkk xxf xf x 這是多元函數(shù)求極值的牛頓法迭代公式。 例4-2 用牛頓法求 22 12 25f xxx 的極小值。 對(duì)牛頓法進(jìn)行改進(jìn)，提出“阻尼牛頓法” 1 12kkkk k xxf xf x 1 min kkkkk k f xfxa dfxad 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 3.4.4 共軛方向及共軛方向法 為了克服最速下降法的鋸

5、齒現(xiàn)象，提高收斂速度，發(fā)展了 一類(lèi)共軛方向法。搜索方向是共軛方向。 一、共軛方向的概念 1 2 TT f xx Gxb xc 共軛方向的概念是在研究二次函數(shù) 時(shí)引出的。 首先考慮二維情況 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 如果按最速下降法，選擇負(fù)梯度方向?yàn)樗阉鞣较颍瑫?huì)產(chǎn)生 鋸齒現(xiàn)象。 為避免鋸齒的發(fā)生，取下一次的迭代搜索方向直接指向極 小點(diǎn)，如果選定這樣的搜索方向，對(duì)于二元二次函數(shù)只需 進(jìn)行兩次直線搜索就可以求到極小點(diǎn)。 100 0 xxa d *11 1 xxa d 1 10 0 T x f f xd d 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 1 d 應(yīng)滿(mǎn)足什么條件？ 對(duì)于二次函數(shù) 在 處取得極

6、小點(diǎn)的必要條件 f x * x * 0f xGxb *1111 11 f xG xa dbGxbaGd 11 1 0f xaGd 等式兩邊同乘 得 0 T d 01 0 T dGd 0 d 1 d 是對(duì)G的共軛方向的共軛方向。 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 三、共軛方向法 1、選定初始點(diǎn) ，下降方向 和收斂精度，k=0。 0 x 0 d 2、沿 方向進(jìn)行一維搜索，得 k d 1kkk k xxa d 3、判斷 是否滿(mǎn)足，若滿(mǎn)足則打印 1k f x 1k x 否則轉(zhuǎn)4。 4、提供新的共軛方向 ，使 1k d 1 0 T jk dGd 5、置 ，轉(zhuǎn)2。1kk 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法

7、結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 3.4.5 共軛梯度法 共軛梯度法是共軛方向法的一種，共軛向量由迭代點(diǎn) 的負(fù)梯度構(gòu)造出來(lái)，所以稱(chēng)共軛梯度法。 1 2 TT f xx Gxb xc 1kkk k xxa d 1kkk k xxa d k k gGxb 從點(diǎn) 出發(fā)，沿G某一共軛方向 作一維搜索，到達(dá) k x k d 1k x 1 1 k k gGxb 而在點(diǎn) 、 處的梯度分別為： k x 1k x 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 1 1 kkk kkk ggG xxa Gd 0 T jk dGd 1 0 T j kk dG gg 得出共軛方向與梯度之間的關(guān)系。此式表明沿方向 k d 進(jìn)行一維搜

8、索，其終點(diǎn) 與始點(diǎn) 的梯度值差 1k x k x 1kk gg 與 的共軛方向 正交。 k d j d 若dj和dk對(duì)G是共軛的，則 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 圖4-9 共軛梯度法的幾何說(shuō)明 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 3.4.6 變尺度法 1kkkk xxHf x 變尺度法的基本思想： 前面討論的梯度法和牛頓法，它們的迭代公式可以看作下列 公式的特例。 變尺度法是對(duì)牛頓法的修正，它不是計(jì)算二階導(dǎo)數(shù)的矩陣和 它的逆矩陣，而是設(shè)法構(gòu)造一個(gè)對(duì)稱(chēng)正定矩陣H來(lái)代替Hessian 矩陣的逆矩陣。并在迭代過(guò)程中，使其逐漸逼近H-1 。 由于對(duì)稱(chēng)矩陣H在迭代過(guò)

9、程中是不斷修正改變的，它對(duì)于一 般尺度的梯度起到改變尺度的作用，因此H又稱(chēng)變尺度矩陣。 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 一、尺度矩陣的概念 變量的尺度變換是放大或縮小各個(gè)坐標(biāo)。 通過(guò)尺度變換可以把函數(shù)的偏心程度降低到最低限度。 對(duì)于一般二次函數(shù) 1 2 TT f xx Gxb xc 如果進(jìn)行尺度變換 xQx 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 則在新的坐標(biāo)系中，函數(shù)的二次項(xiàng)變?yōu)?11 22 TTT x Gxx Q GQx 選擇這樣變換的目的：降低二次項(xiàng)的偏心程度。 若矩陣G是正定的，則總存在矩陣Q使 T Q GQI 使得函數(shù)偏心度變?yōu)榱恪?用Q-1 右乘等式兩邊，得 1T Q GQ 再用Q左乘

10、等式兩邊，得 T QQ GI 所以 1T QQG 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 說(shuō)明二次函數(shù)矩陣G的逆矩陣，可以通過(guò)尺度變換矩陣Q 求得。 這樣，牛頓法迭代過(guò)程中的牛頓方向可寫(xiě)成： 1kkTk dGf xQQf x 1kkkTk xxQQf x 三、變尺度法的一般步驟 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 3.4.7 坐標(biāo)輪換法 坐標(biāo)輪換法是每次搜索只允許一個(gè)變量變化，其余變量保持 不變，即沿坐標(biāo)方向輪流進(jìn)行搜索的尋優(yōu)方法。 它把多變量的優(yōu)化問(wèn)題輪流地轉(zhuǎn)化成單變量的優(yōu)化問(wèn)題。 因此又稱(chēng)變量輪換法變量輪換法。 其基本原理是將一個(gè)多維的無(wú)約束最優(yōu)化問(wèn)題轉(zhuǎn)化為 一系

11、列較低維的最優(yōu)化問(wèn)題來(lái)求解，簡(jiǎn)單地說(shuō)，就是先將 (n-1)個(gè)變量固定不動(dòng)，只對(duì)第一個(gè)變量進(jìn)行一維搜索得到 最優(yōu)點(diǎn)x1（1）。然后，又保持(n-1)個(gè)變量不變，再對(duì)第二 個(gè)變量進(jìn)行一維搜索到x2（1）等等。 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 坐標(biāo)輪換法原理圖（坐標(biāo)輪換法原理圖（動(dòng)畫(huà)演示動(dòng)畫(huà)演示） )0( 2 )0( 1 X X )0( 2 )1( 1 X X )1( 2 )1( 1 X X )2( 2 )2( 1 X X 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 2. 搜索方向與步長(zhǎng)的確定 （1）搜索方向的確定）搜索方向的確定 對(duì)于第k輪第i次的計(jì)算 1 kkkk ii

12、ii xxa d 第k輪第i次的迭代方向，它輪流取n維坐標(biāo)的單位向量。 0 . 1 . 0 k ii de 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 3.搜索步長(zhǎng)的確定 關(guān)于關(guān)于 值通常有以下幾種取法值通常有以下幾種取法 （1）加速步長(zhǎng)法）加速步長(zhǎng)法 （2）最優(yōu)步長(zhǎng)法）最優(yōu)步長(zhǎng)法 最優(yōu)步長(zhǎng)法就是利用一維最優(yōu)搜索方法來(lái)完成最優(yōu)步長(zhǎng)法就是利用一維最優(yōu)搜索方法來(lái)完成 每一次迭代，即每一次迭代，即 此時(shí)可以采用此時(shí)可以采用0.618方法或二次插值方法來(lái)計(jì)算方法或二次插值方法來(lái)計(jì)算 的值。的值。 )( k i 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 加速步長(zhǎng)法的搜索路線 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 圖圖414 最優(yōu)步長(zhǎng)法的搜索路線最優(yōu)步長(zhǎng)法的搜索路線 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 4 . 坐標(biāo)輪換法存在的問(wèn)題 圖圖415 坐標(biāo)輪換法在各種不同情況下的效能坐標(biāo)輪換法在各種不同情況下的效能 （a）搜索有效；（）搜索有效；（b）搜索低效；（）搜索低效；（c）搜索無(wú)效）搜索無(wú)效 結(jié)構(gòu)優(yōu)化算法基礎(chǔ)之無(wú)約束優(yōu)化方法 3.4.8 Powell法（方向加速法） Powell法是利用共軛方向可以加速收斂的性質(zhì)所法是利用共軛方向可以加速收斂的性質(zhì)所 形成的一種搜索算法。形成