機(jī)械優(yōu)化設(shè)計(jì)_第四章無約束優(yōu)化方法

1、機(jī)械優(yōu)化設(shè)計(jì)第四章無約束優(yōu)化方法第四章無約束優(yōu)化方法一、概述一、概述二、最速下降法（梯度法）二、最速下降法（梯度法）三、牛頓型方法（牛頓法和阻尼牛頓法）三、牛頓型方法（牛頓法和阻尼牛頓法）四、共軛方向和共軛方向法四、共軛方向和共軛方向法五、共軛梯度法五、共軛梯度法六、變尺度法六、變尺度法七、坐標(biāo)輪換法七、坐標(biāo)輪換法機(jī)械優(yōu)化設(shè)計(jì) 實(shí)際中的工程問題大都是在一定限制條件下追實(shí)際中的工程問題大都是在一定限制條件下追求某一指標(biāo)為最小，屬于約束優(yōu)化問題。求某一指標(biāo)為最小，屬于約束優(yōu)化問題。 為什么要研究無約束優(yōu)化問題？為什么要研究無約束優(yōu)化問題？1）有些實(shí)際問題，其數(shù)學(xué)模型本身就是一個無約束問題；）有些實(shí)

2、際問題，其數(shù)學(xué)模型本身就是一個無約束問題；2）通過熟悉它的解法可以為研究約束優(yōu)化問題打下良好的）通過熟悉它的解法可以為研究約束優(yōu)化問題打下良好的基礎(chǔ)；基礎(chǔ)；3）約束優(yōu)化問題的求解可用通過一系列無約束優(yōu)化方法來）約束優(yōu)化問題的求解可用通過一系列無約束優(yōu)化方法來達(dá)到。達(dá)到。所以無約束優(yōu)化問題的解法是所以無約束優(yōu)化問題的解法是優(yōu)化設(shè)計(jì)方法的基本優(yōu)化設(shè)計(jì)方法的基本組成部分組成部分，也是優(yōu)化方法的基礎(chǔ)。，也是優(yōu)化方法的基礎(chǔ)。機(jī)械優(yōu)化設(shè)計(jì)1 1、無約束優(yōu)化問題、無約束優(yōu)化問題n求 維設(shè)計(jì)變量 使目標(biāo)函數(shù) 12,TnXx xxminfX X，而對 沒有任何限制條件。2 2、求解方法、求解方法（1 1）利用極

3、值條件來確定極值點(diǎn)的位置。）利用極值條件來確定極值點(diǎn)的位置。 （2 2）數(shù)值計(jì)算方法數(shù)值計(jì)算方法搜索方法搜索方法基本思想基本思想：從給定的初始點(diǎn) 出發(fā)，沿某一搜索方向 0 x0d進(jìn)行搜索，確定最佳步長 0使函數(shù)值沿 0d下降最大。依此方式不斷進(jìn)行，形成迭代的下降算法：1kkkkXXd(0,1,2)k 一、概述一、概述機(jī)械優(yōu)化設(shè)計(jì)3 3、算法框圖、算法框圖 機(jī)械優(yōu)化設(shè)計(jì)4 4、無約束優(yōu)化方法的分、無約束優(yōu)化方法的分類類根據(jù)確定其搜索方向根據(jù)確定其搜索方向 方法不同，可分為：方法不同，可分為： kd（2 2）利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)的無約束優(yōu)化方法）利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)的無約束優(yōu)化方法

4、（或稱（或稱間接法間接法）如：）如：最速下降法（梯度法）、共軛梯度法、最速下降法（梯度法）、共軛梯度法、牛頓法及變尺度法；牛頓法及變尺度法； 間接法間接法除了要計(jì)算目標(biāo)函數(shù)值外，還要計(jì)算目標(biāo)函數(shù)的除了要計(jì)算目標(biāo)函數(shù)值外，還要計(jì)算目標(biāo)函數(shù)的梯度，有的還要計(jì)算其海賽矩陣；梯度，有的還要計(jì)算其海賽矩陣；（1 1）只利用目標(biāo)函數(shù)值的無約束優(yōu)化方法（或稱）只利用目標(biāo)函數(shù)值的無約束優(yōu)化方法（或稱直接法，直接法，即不使用導(dǎo)數(shù)信息），如：即不使用導(dǎo)數(shù)信息），如：坐標(biāo)輪換法、單形替換法及鮑威坐標(biāo)輪換法、單形替換法及鮑威（PowellPowell）法。）法。 直接法直接法不必求函數(shù)導(dǎo)數(shù)，只計(jì)算目標(biāo)函數(shù)值。適用于求

5、不必求函數(shù)導(dǎo)數(shù)，只計(jì)算目標(biāo)函數(shù)值。適用于求解變量個數(shù)較少（小于解變量個數(shù)較少（小于2020）的問題，一般情況下效率較低。）的問題，一般情況下效率較低。搜索方向的構(gòu)成問題是無約束優(yōu)化方法的關(guān)鍵。搜索方向的構(gòu)成問題是無約束優(yōu)化方法的關(guān)鍵。機(jī)械優(yōu)化設(shè)計(jì)二、最速下降法（梯度法）二、最速下降法（梯度法）1 1、基本思想、基本思想 函數(shù)的負(fù)梯度方向是函數(shù)值在該點(diǎn)下降最快的方向。函數(shù)的負(fù)梯度方向是函數(shù)值在該點(diǎn)下降最快的方向。將將n n維問題轉(zhuǎn)化為一系列維問題轉(zhuǎn)化為一系列沿負(fù)梯度方向沿負(fù)梯度方向用一維搜索方法尋用一維搜索方法尋優(yōu)的問題，即利用負(fù)梯度作為搜索方向，故稱為最速下降優(yōu)的問題，即利用負(fù)梯度作為搜索方向

6、，故稱為最速下降法或梯度法。法或梯度法。dfX 1kkkkXXfX(0,1,2)k 搜索方向取該點(diǎn)的負(fù)梯度方向即搜索方向取該點(diǎn)的負(fù)梯度方向即 ，使函，使函數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快。數(shù)值在該點(diǎn)附近的范圍內(nèi)下降最快。機(jī)械優(yōu)化設(shè)計(jì)2 2、最速下降法的原理、最速下降法的原理（1 1）使）使 ，按此規(guī)律不斷走步，形成迭代算法：按此規(guī)律不斷走步，形成迭代算法： dfX 1kkkkXXfX(0,1,2)k （2 2）其步長因子）其步長因子 取一維搜索的取一維搜索的最佳步長最佳步長，即，即k 根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得式，得 0Tk

7、kKkfXfXfX 10Tkkdd10Tkkfxfx或或 1minminkkkkkkkfxfxafxfxafx 機(jī)械優(yōu)化設(shè)計(jì) 由此可知，在最速下降由此可知，在最速下降法中，相鄰兩個迭代點(diǎn)上法中，相鄰兩個迭代點(diǎn)上的函數(shù)梯度相互垂直。而的函數(shù)梯度相互垂直。而搜索方向就是負(fù)梯度方向，搜索方向就是負(fù)梯度方向，因此相鄰兩個搜索方向互因此相鄰兩個搜索方向互相垂直相垂直。這就是說在迭代。這就是說在迭代點(diǎn)向函數(shù)極小點(diǎn)靠近的過點(diǎn)向函數(shù)極小點(diǎn)靠近的過程，走的是曲折的路線，程，走的是曲折的路線，形成形成“之之”字形的鋸齒現(xiàn)字形的鋸齒現(xiàn)象，而且越接近極小點(diǎn)鋸象，而且越接近極小點(diǎn)鋸齒越細(xì)。齒越細(xì)。最速下降法的搜索路徑最

8、速下降法的搜索路徑函數(shù)梯度為局部性質(zhì)，因此并非函數(shù)梯度為局部性質(zhì)，因此并非“最快最快”。機(jī)械優(yōu)化設(shè)計(jì)梯度法的迭代歷程梯度法的迭代歷程機(jī)械優(yōu)化設(shè)計(jì)方法特點(diǎn)方法特點(diǎn)1 1）初始點(diǎn)可任選，每次迭代計(jì)算量小，存儲量少，）初始點(diǎn)可任選，每次迭代計(jì)算量小，存儲量少，程序簡短。即使從一個不好的初始點(diǎn)出發(fā)，開始程序簡短。即使從一個不好的初始點(diǎn)出發(fā)，開始的幾步迭代，目標(biāo)函數(shù)值下降很快，然后慢慢逼的幾步迭代，目標(biāo)函數(shù)值下降很快，然后慢慢逼近局部極小點(diǎn)；近局部極小點(diǎn)；2 2）任意相鄰兩點(diǎn)的搜索方向是正交的，它的迭代）任意相鄰兩點(diǎn)的搜索方向是正交的，它的迭代路徑為繞道逼近極小點(diǎn)。當(dāng)?shù)c(diǎn)接近極小點(diǎn)時，路徑為繞道逼近極

9、小點(diǎn)。當(dāng)?shù)c(diǎn)接近極小點(diǎn)時，步長變得很小，越走越慢。步長變得很小，越走越慢。機(jī)械優(yōu)化設(shè)計(jì)最最速速下下降降法法的的程程序序框框圖圖機(jī)械優(yōu)化設(shè)計(jì)例：例：求目標(biāo)函數(shù)求目標(biāo)函數(shù) 221225fXxx的極小點(diǎn)的極小點(diǎn)解法解法1 1：取初始點(diǎn)取初始點(diǎn) 02,2TX，則初始點(diǎn)處的函數(shù)值，則初始點(diǎn)處的函數(shù)值及梯度分別為：及梯度分別為：01021042450100fXxfXx010000024242 1002100XXfX 0為一維搜索最佳步長，應(yīng)滿足極值必要條件為一維搜索最佳步長，應(yīng)滿足極值必要條件 10022minmin (2 4 )25(2 100 )minf Xf Xf X 0008(24)5000(2

10、 100)0 06260.0200307231252機(jī)械優(yōu)化設(shè)計(jì)則第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值則第一次迭代設(shè)計(jì)點(diǎn)位置和函數(shù)值0120241.9198772 1000.3071785 10X13.686164fX經(jīng)過經(jīng)過1010次迭代后，得到最優(yōu)解：次迭代后，得到最優(yōu)解：0,0TX0fX 該問題的目標(biāo)函數(shù)的等值線為一族橢圓，迭代該問題的目標(biāo)函數(shù)的等值線為一族橢圓，迭代點(diǎn)走的是一段鋸齒形路線。點(diǎn)走的是一段鋸齒形路線。機(jī)械優(yōu)化設(shè)計(jì)解法解法2 2：引入變化引入變化 11225yxyx，則目標(biāo)函數(shù)則目標(biāo)函數(shù) 12,f x x變?yōu)樽優(yōu)?221212,y yyy0104Y010224220YyYy 0100

11、0002 42410 201020YYY 0260.552 010240102000Y 10Y0,0TX0fX，經(jīng)過坐標(biāo)（尺度）變化后，只需要經(jīng)過一次迭代，就可找到經(jīng)過坐標(biāo)（尺度）變化后，只需要經(jīng)過一次迭代，就可找到最優(yōu)解：最優(yōu)解：機(jī)械優(yōu)化設(shè)計(jì)不同等值線的迭代過程不同等值線的迭代過程機(jī)械優(yōu)化設(shè)計(jì)討論1221212122201,250502xf x xxxxxx1221212122201,022yy yyyyyy 可以看出二者的對角形矩陣不同，前者的可以看出二者的對角形矩陣不同，前者的等值線為一族橢圓，后者的等值線為一族同等值線為一族橢圓，后者的等值線為一族同心圓，這說明心圓，這說明對角形矩陣是

12、表示度量的矩陣對角形矩陣是表示度量的矩陣或者是表示尺度的矩陣或者是表示尺度的矩陣，最速下降法的收斂，最速下降法的收斂速度和變量的尺度有很大關(guān)系。速度和變量的尺度有很大關(guān)系。機(jī)械優(yōu)化設(shè)計(jì)3 3、最速下降法收斂速度的估計(jì)式、最速下降法收斂速度的估計(jì)式2121kkmXXXXMM f x的海賽矩陣最大特征值上界的海賽矩陣最大特征值上界 的海賽矩陣最小特征值下界的海賽矩陣最小特征值下界 f x m2122624150625kkkXXXXXX2122102kkYYYY機(jī)械優(yōu)化設(shè)計(jì)梯度法的特點(diǎn)：梯度法的特點(diǎn)：（1 1）理論明確，程序簡單，對初始點(diǎn)要求不嚴(yán)格；）理論明確，程序簡單，對初始點(diǎn)要求不嚴(yán)格；（2 2

13、）對一般函數(shù)而言，梯度法的收斂速度并不快，）對一般函數(shù)而言，梯度法的收斂速度并不快，因?yàn)樽钏傧陆捣▋H僅是指某點(diǎn)的一個因?yàn)樽钏傧陆捣▋H僅是指某點(diǎn)的一個局部性質(zhì)局部性質(zhì)；（3 3）梯度法相鄰兩次搜索方向的正交性決定了迭代）梯度法相鄰兩次搜索方向的正交性決定了迭代全過程的全過程的搜索路徑呈鋸齒形搜索路徑呈鋸齒形，在遠(yuǎn)離極小點(diǎn)時逼近速，在遠(yuǎn)離極小點(diǎn)時逼近速度較快，而在接近極小點(diǎn)時逼近速度較慢；度較快，而在接近極小點(diǎn)時逼近速度較慢；（4 4）梯度法的）梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)密切相關(guān)收斂速度與目標(biāo)函數(shù)的性質(zhì)密切相關(guān)。對于等值線（面）為同心圓（球）的目標(biāo)函數(shù)，一次對于等值線（面）為同心圓（球）的目

14、標(biāo)函數(shù)，一次搜索即可達(dá)到極小點(diǎn)。搜索即可達(dá)到極小點(diǎn)。機(jī)械優(yōu)化設(shè)計(jì)三、牛頓型方法三、牛頓型方法基本思想：基本思想：在在 領(lǐng)域內(nèi)用一個二次函數(shù)領(lǐng)域內(nèi)用一個二次函數(shù) 來近似來近似代替原目標(biāo)函數(shù)，并將代替原目標(biāo)函數(shù)，并將 的極小值作為目標(biāo)函數(shù)的極小值作為目標(biāo)函數(shù) 求優(yōu)的下一個迭代點(diǎn)求優(yōu)的下一個迭代點(diǎn) 。經(jīng)多次迭代，使之逼近目標(biāo)。經(jīng)多次迭代，使之逼近目標(biāo)函數(shù)函數(shù) 的極小點(diǎn)。的極小點(diǎn)。kx)(x)(x)(xf)(xf1kx), 2 , 1 , 0()()( 1kxfxfxxkkkk機(jī)械優(yōu)化設(shè)計(jì)對于多元函數(shù)對于多元函數(shù) fX，設(shè)，設(shè) kX為為 fX極小點(diǎn)極小點(diǎn) X的第一的第一個近似點(diǎn)，個近似點(diǎn)，fX泰勒展開

15、，保留到二次項(xiàng)，得泰勒展開，保留到二次項(xiàng)，得: :設(shè)設(shè) 1kX為為 X的極小點(diǎn)，它作為的極小點(diǎn)，它作為 fX極小點(diǎn)極小點(diǎn) X的下一個近似點(diǎn)，根據(jù)極值必要條件：的下一個近似點(diǎn)，根據(jù)極值必要條件：10kX即即 210kkkkfXfXXX112(0,1,2)kkkkXXf Xf Xk 2kfX 海賽矩陣海賽矩陣 1 1、牛頓法、牛頓法對于二次函數(shù)，海賽矩陣是常矩陣，故從任何點(diǎn)出發(fā)，只需一步可找對于二次函數(shù)，海賽矩陣是常矩陣，故從任何點(diǎn)出發(fā)，只需一步可找到極小點(diǎn)。到極小點(diǎn)。-多元函數(shù)求極值的多元函數(shù)求極值的牛頓法迭代公式。牛頓法迭代公式。 f xx 212TTkkkkkkf xf xxxxxf xxx

16、機(jī)械優(yōu)化設(shè)計(jì)例例: :221212,25f x xxx用牛頓法求用牛頓法求 的極小值的極小值 解解：取初始點(diǎn)取初始點(diǎn) 02,2TX，則，則 01022450100XxfXx2020050fX1201021050fX 110200102402121000050XXfXfX 代入牛頓法迭代公式可得代入牛頓法迭代公式可得: :從而經(jīng)過一次迭代即求得極小點(diǎn)和函數(shù)極小值。從而經(jīng)過一次迭代即求得極小點(diǎn)和函數(shù)極小值。機(jī)械優(yōu)化設(shè)計(jì)2 2、阻尼牛頓法、阻尼牛頓法 把把 12kkkdfXfX 看作一個搜索方向，看作一個搜索方向，稱其為牛頓方向，稱其為牛頓方向，則阻尼牛頓法的迭代公式為則阻尼牛頓法的迭代公式為：11

17、2(0,1,2)kkkkkkkkXXdXfXfXkk阻尼因子，即沿牛頓方向進(jìn)行一維搜索的最佳步長，阻尼因子，即沿牛頓方向進(jìn)行一維搜索的最佳步長，可通過如下極小化過程求得：可通過如下極小化過程求得： 1minkkkkkkf Xf Xdf Xd（1 1）阻尼牛頓法的迭代公式）阻尼牛頓法的迭代公式 在牛頓法中，迭代點(diǎn)的位置是按照極值條件確定，并未在牛頓法中，迭代點(diǎn)的位置是按照極值條件確定，并未含有沿下降方向搜尋的概念，因此采用牛頓迭代公式，對含有沿下降方向搜尋的概念，因此采用牛頓迭代公式，對于非二次函數(shù)，有時會使函數(shù)值上升。于非二次函數(shù)，有時會使函數(shù)值上升。機(jī)械優(yōu)化設(shè)計(jì)（2 2）阻尼牛頓法的計(jì)算步驟

18、）阻尼牛頓法的計(jì)算步驟1 1）給定初始點(diǎn)）給定初始點(diǎn) ，收斂精度，收斂精度 ，置，置 0X0k 2 2）計(jì)算）計(jì)算 122kkkfXfXfX、12kkkdfXfX 3 3）求）求 1kkkkXXd4 4）檢查收斂精度。若）檢查收斂精度。若 1kkXX，則，則 ，停機(jī)；，停機(jī)； 1kXX否則置否則置 1kk返回到返回到2 2），繼續(xù)進(jìn)行搜索。），繼續(xù)進(jìn)行搜索。機(jī)械優(yōu)化設(shè)計(jì)（3）阻尼牛頓法的阻尼牛頓法的 程序框圖程序框圖 機(jī)械優(yōu)化設(shè)計(jì)方法特點(diǎn)：方法特點(diǎn)：1 1）初始點(diǎn)應(yīng)選在極小點(diǎn)附近，有一定難度；）初始點(diǎn)應(yīng)選在極小點(diǎn)附近，有一定難度；2 2）盡管每次迭代都不會是函數(shù)上升，但不能保證每次）盡管每次迭

19、代都不會是函數(shù)上升，但不能保證每次都下降；都下降；3 3）若迭代點(diǎn)的海賽矩陣為奇異，則無法求逆矩陣，不）若迭代點(diǎn)的海賽矩陣為奇異，則無法求逆矩陣，不能構(gòu)造牛頓法方向；能構(gòu)造牛頓法方向；4 4）不僅要計(jì)算梯度，還要求海賽矩陣及其逆矩陣，計(jì)）不僅要計(jì)算梯度，還要求海賽矩陣及其逆矩陣，計(jì)算量和存儲量大。此外對于二階不可微函數(shù)也不適用。算量和存儲量大。此外對于二階不可微函數(shù)也不適用。 雖然阻尼牛頓法有上述缺點(diǎn)，但在特定條件下它具有收雖然阻尼牛頓法有上述缺點(diǎn)，但在特定條件下它具有收斂最快的優(yōu)點(diǎn)，可為其他算法提供思路和理論依據(jù)。斂最快的優(yōu)點(diǎn)，可為其他算法提供思路和理論依據(jù)。機(jī)械優(yōu)化設(shè)計(jì)梯度法與牛頓法的比較

20、梯度法與牛頓法的比較一般迭代式：一般迭代式：梯度法：梯度法：牛頓法：牛頓法：阻尼牛頓法：阻尼牛頓法：112(0,1,2)kkkkXXfXfXk 1kkkkXXfX(0,1,2)k 112(0,1,2)kkkkkkkkXXdXfXfXk1kkkkXXd(0,1,2)k 機(jī)械優(yōu)化設(shè)計(jì)四、共軛方向和共軛方向法四、共軛方向和共軛方向法（一）（一）共軛方向共軛方向的概念的概念 設(shè)設(shè)G為為nxn階實(shí)對稱正定矩陣，如果有兩個階實(shí)對稱正定矩陣，如果有兩個n維向量維向量 和和 滿足滿足 ，則稱向量，則稱向量 與與 關(guān)于矩陣關(guān)于矩陣 G共軛，或稱他們是共軛，或稱他們是G的共軛方向。的共軛方向。當(dāng)當(dāng)G為單位矩陣時，

21、為單位矩陣時，010TdGd 0d1d0d1d0)(10ddT共軛方向的概念是在研究二次函數(shù)共軛方向的概念是在研究二次函數(shù)12TTfXX GXb XcG當(dāng)當(dāng) 為對稱正定矩陣時引出的使搜索方向直指極小點(diǎn)。為對稱正定矩陣時引出的使搜索方向直指極小點(diǎn)。 為了克服最速下降法的鋸齒現(xiàn)象，提高收斂速度，發(fā)展了為了克服最速下降法的鋸齒現(xiàn)象，提高收斂速度，發(fā)展了一類共軛方向法。搜索方向是共軛方向。即將相鄰兩次搜一類共軛方向法。搜索方向是共軛方向。即將相鄰兩次搜索方向由正交變?yōu)楣曹棥Ｋ鞣较蛴烧蛔優(yōu)楣曹?。機(jī)械優(yōu)化設(shè)計(jì) 首先考慮二維情況，首先考慮二維情況，如果按最速下降法，選擇負(fù)梯度方如果按最速下降法，選擇負(fù)梯度

22、方向?yàn)樗阉鞣较?，會產(chǎn)生鋸齒現(xiàn)象。向?yàn)樗阉鞣较?，會產(chǎn)生鋸齒現(xiàn)象。 為避免鋸齒的發(fā)生，取下一次的迭代搜索方向直接指向?yàn)楸苊怃忼X的發(fā)生，取下一次的迭代搜索方向直接指向極小點(diǎn)，如果選定這樣的搜索方向，對于二元二次函數(shù)只極小點(diǎn)，如果選定這樣的搜索方向，對于二元二次函數(shù)只需進(jìn)行兩次直線搜索就可以求到極小點(diǎn)。需進(jìn)行兩次直線搜索就可以求到極小點(diǎn)。1000 xxa d*111xxa d 1100Txff xdd 如果能選定這樣的方向，則只如果能選定這樣的方向，則只需兩步搜索得到極小點(diǎn)，即需兩步搜索得到極小點(diǎn)，即機(jī)械優(yōu)化設(shè)計(jì)結(jié)論：結(jié)論：010TdGd 兩個向量兩個向量 0d1d，對對G是是共軛向量共軛向量。1d應(yīng)

23、滿足什么條件？應(yīng)滿足什么條件？對于二次函數(shù)對于二次函數(shù) 在在 處取得極小點(diǎn)的必要條件處取得極小點(diǎn)的必要條件 fx*x*0fxGxb*111111f xG xa dbGxbaGd 1110f xaGd 等式兩邊同左乘等式兩邊同左乘 得：得：0Td0d1d和和 稱為對稱為對G的的共軛方向共軛方向。12TTfXX GXb Xc01*1時，當(dāng)xx機(jī)械優(yōu)化設(shè)計(jì)（三）共軛方向法（三）共軛方向法 1 1、共軛方向法的步驟、共軛方向法的步驟（1 1）選定初始點(diǎn)）選定初始點(diǎn) 0X，下降方向，下降方向 0d和收斂精度和收斂精度 ，置，置 0k （2 2）沿）沿 kd方向進(jìn)行一維搜索，得方向進(jìn)行一維搜索，得 1kk

24、kkXXd（3 3）判斷）判斷 1kfX是否滿足，若滿足則打印是否滿足，若滿足則打印 ， 1kX停機(jī)，否則轉(zhuǎn)停機(jī)，否則轉(zhuǎn)4 4）。）。（4 4）提供新的共軛方向）提供新的共軛方向 1kd，使，使 10,0,1,2,TjkdGdjk（5 5）置）置 1kk，轉(zhuǎn)，轉(zhuǎn)2 2）。）。機(jī)械優(yōu)化設(shè)計(jì)2、共軛方向法、共軛方向法 程序框圖程序框圖機(jī)械優(yōu)化設(shè)計(jì)3 3、格拉姆、格拉姆斯密特向量系共軛化法（共軛方向的確定）斯密特向量系共軛化法（共軛方向的確定） 1 1、選定線性無關(guān)向量系、選定線性無關(guān)向量系 ，如，如n n個坐標(biāo)軸的單個坐標(biāo)軸的單位向量位向量；011,nv vv00dv2 2、取、取 ，令，令 ，根

25、據(jù)共軛條件得，根據(jù)共軛條件得10110dvd01001100TTdGddG vd011000TTdGvdGd 0110100TTdGvdvddGd1110TjkkkjkTjjjdGvdvddGd11,TjkkrTjjdGddGd 3 3、遞推可得：、遞推可得：機(jī)械優(yōu)化設(shè)計(jì)五、共軛梯度法五、共軛梯度法1 1、共軛梯度法是共軛方向法中的一種，該方法中每一個、共軛梯度法是共軛方向法中的一種，該方法中每一個共軛向量都是依賴與迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來。共軛向量都是依賴與迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來。對于二次函數(shù)對于二次函數(shù)12TTfXX GXb Xc1kkkkxxa d1kkkkxxa dkkgGxb從

26、點(diǎn)從點(diǎn) 出發(fā)，沿出發(fā)，沿G某一共軛方向某一共軛方向 作一維搜索作一維搜索,到達(dá)到達(dá)kxkd1kx11kkgGxb而在點(diǎn)而在點(diǎn) 、 處的梯度分別為：處的梯度分別為：kx1kx機(jī)械優(yōu)化設(shè)計(jì)10Tjkkdgg 1kkgg、kX1kX點(diǎn)處的梯度點(diǎn)處的梯度 jd若若 和和kd對對G是共軛方向，則：是共軛方向，則：11kkkkkkggG xxa Gd0TjkdGd 其中：其中： 機(jī)械優(yōu)化設(shè)計(jì) 得出共軛方向與梯度之間的關(guān)系。此式表明沿方向得出共軛方向與梯度之間的關(guān)系。此式表明沿方向kd進(jìn)行一維搜索，其終點(diǎn)進(jìn)行一維搜索，其終點(diǎn) 與始點(diǎn)與始點(diǎn) 的梯度值差的梯度值差1kxkx1kkgg與與 的共軛方向的共軛方向

27、正交。正交。kdjd結(jié)論：結(jié)論：10Tjkkdgg機(jī)械優(yōu)化設(shè)計(jì)2 2、共軛梯度法計(jì)算原理、共軛梯度法計(jì)算原理kX)2 , 1 , 0(1kdxxkkkk從從 出發(fā)，沿負(fù)梯度方向作一維搜索：出發(fā)，沿負(fù)梯度方向作一維搜索：)(kkxfd設(shè)與設(shè)與 共軛的下一個方向共軛的下一個方向 是由是由 和點(diǎn)和點(diǎn) 的負(fù)梯的負(fù)梯度的線性組合構(gòu)成，即：度的線性組合構(gòu)成，即：kd1kdkd1kxkkkkdxfd)(11共軛條件（與梯度的關(guān)系）：共軛條件（與梯度的關(guān)系）：0)()()(11kkTkxfxfd將式（將式（1 1）代入（）代入（2 2）得：）得：（1 1）（2 2）0)()()()(11kkkkkxfxfdx

28、f機(jī)械優(yōu)化設(shè)計(jì)22111)()()()()()(kkkTkkTkkxfxfxfxfxfxfkkkkdxfd)(11221)()(kkkxfxf因此可得共軛方向的遞推公式：因此可得共軛方向的遞推公式：)2 , 1 , 0(1kdxxkkkkkkkkdxfd)(11機(jī)械優(yōu)化設(shè)計(jì)3 3、共軛梯度法計(jì)算過程、共軛梯度法計(jì)算過程 （1 1）設(shè)初始點(diǎn)）設(shè)初始點(diǎn) 0X 、00dg 、1000XXd計(jì)算計(jì)算1g（2 2）求）求 的共軛方向的共軛方向 0d2110120,gdgdg 2111XXd計(jì)算計(jì)算2g（3 3）求與）求與 和和 均共軛的方向均共軛的方向 0d1d2221221gdgdg （4 4）再沿）

29、再沿 方向進(jìn)行一維搜索，如此繼續(xù)下去，方向進(jìn)行一維搜索，如此繼續(xù)下去， 2d可求得共軛方向的遞推公式為：可求得共軛方向的遞推公式為： 21112(0,1, 2,1)kkkkkgdgdkng 機(jī)械優(yōu)化設(shè)計(jì)4 4、共軛梯度法、共軛梯度法 程序框圖程序框圖機(jī)械優(yōu)化設(shè)計(jì)六、變尺度法六、變尺度法1 1、問題的提出、問題的提出能否克服各自的缺點(diǎn)，綜合發(fā)揮其優(yōu)點(diǎn)？能否克服各自的缺點(diǎn)，綜合發(fā)揮其優(yōu)點(diǎn)？2 2）阻尼牛頓法）阻尼牛頓法1 1）梯度法）梯度法* * 簡單，開始時目標(biāo)函數(shù)值下降較快，但越來越慢。簡單，開始時目標(biāo)函數(shù)值下降較快，但越來越慢。* * 目標(biāo)函數(shù)值在最優(yōu)點(diǎn)附近時收斂快，但要用到二目標(biāo)函數(shù)值在最

30、優(yōu)點(diǎn)附近時收斂快，但要用到二階導(dǎo)數(shù)和矩陣求逆。階導(dǎo)數(shù)和矩陣求逆。112(0,1,2)kkkkkkkkXXdXfXfXk1kkkkXXfX機(jī)械優(yōu)化設(shè)計(jì)2 2、變尺度法的基本思想、變尺度法的基本思想 對于一般函數(shù)對于一般函數(shù) ，當(dāng)用牛頓法尋求極小點(diǎn)時，當(dāng)用牛頓法尋求極小點(diǎn)時， fX其牛頓迭代公式為：其牛頓迭代公式為： 11(0,1,2,)kkkkkXXGgk 其中：其中： kkgfX 2kkGfX 為了避免迭代公式中計(jì)算海賽矩陣的逆陣，用對為了避免迭代公式中計(jì)算海賽矩陣的逆陣，用對稱正定矩陣稱正定矩陣 近似近似 的逆，每迭代一次，尺度的逆，每迭代一次，尺度就改變一次。而就改變一次。而 的產(chǎn)生從給定

31、的產(chǎn)生從給定 開始逐步修整開始逐步修整得到。得到。 H k2kfX H k 1H機(jī)械優(yōu)化設(shè)計(jì)3 3、尺度矩陣的概念、尺度矩陣的概念對于一般二次函數(shù)對于一般二次函數(shù) 12TTfXX GXb Xc如進(jìn)行尺度變化如進(jìn)行尺度變化XQX1122TTTX GXX Q GQX若矩陣若矩陣 是正定的，則總存在矩陣是正定的，則總存在矩陣 使使 可得可得 GQTQ GQI1TQQG牛頓迭代法公式變?yōu)椋号ｎD迭代法公式變?yōu)椋?1kkTkkXXQQfXTHQQ牛頓法可以看成經(jīng)過尺度變化后的梯度法牛頓法可以看成經(jīng)過尺度變化后的梯度法 -尺度矩陣尺度矩陣 變量的尺度變換是放大或縮小各個坐標(biāo)。變量的尺度變換是放大或縮小各個坐

32、標(biāo)。通過尺度變通過尺度變換可以把函數(shù)的偏心程度降低到最低限度。換可以把函數(shù)的偏心程度降低到最低限度。機(jī)械優(yōu)化設(shè)計(jì)12)(kxf)(1kkkkkxfHxxnnkH是需要構(gòu)造是需要構(gòu)造 的一個對稱方陣，的一個對稱方陣，kHIHk如果如果 ，則得到梯度法；，則得到梯度法；12)(kkxfH如果如果 ，則得到阻尼牛頓法；，則得到阻尼牛頓法；當(dāng)矩陣當(dāng)矩陣 不斷地迭代而能很好地逼近不斷地迭代而能很好地逼近 時，時，就可以不再需要計(jì)算二階導(dǎo)數(shù)。就可以不再需要計(jì)算二階導(dǎo)數(shù)。變尺度法的關(guān)鍵在于尺度矩陣的產(chǎn)生。變尺度法的關(guān)鍵在于尺度矩陣的產(chǎn)生。機(jī)械優(yōu)化設(shè)計(jì) （2 2）變尺度矩陣應(yīng)滿足的條件）變尺度矩陣應(yīng)滿足的條件

33、 1 1）為了保證迭代公式具有下降性質(zhì)，要求）為了保證迭代公式具有下降性質(zhì)，要求 kH中的每一個矩陣都是對稱正定的；中的每一個矩陣都是對稱正定的；2 2）要求）要求 之間的迭代具有簡單的形式：之間的迭代具有簡單的形式： kH3 3）要求）要求 必須滿足擬牛頓條件。必須滿足擬牛頓條件。 kH111kkkkkHggXX11,kkkkkkSXXygg令令 1kkkHyS擬牛頓條件擬牛頓條件kkkEHH1即通過修正矩陣即通過修正矩陣 的不斷修正，使其在迭代中不斷的不斷修正，使其在迭代中不斷逼近逼近 。kE)(1kxG機(jī)械優(yōu)化設(shè)計(jì)4 4、變尺度法的一般步驟、變尺度法的一般步驟（1 1）選定初始點(diǎn)）選定初

34、始點(diǎn) 和收斂精度和收斂精度 ； 0X（2 2）計(jì)算）計(jì)算 ，選取初始對稱正定矩陣，選取初始對稱正定矩陣 ， 00gfX 0H置置 ； 0k （3 3）計(jì)算搜索方向）計(jì)算搜索方向 ； kkkdH g （4 4）沿）沿 方向進(jìn)行一維搜索方向進(jìn)行一維搜索 ，計(jì)算，計(jì)算kd1kkkkXXd111,kkkkkkkkgfXSXXygg （5 5）判斷是否滿足迭代終止準(zhǔn)則，若滿足則）判斷是否滿足迭代終止準(zhǔn)則，若滿足則 ， 1kXX停機(jī)，否則停機(jī)，否則6 6）；）； （6 6）當(dāng)?shù)┊?dāng)?shù)?次后還沒有找到極小點(diǎn)時次后還沒有找到極小點(diǎn)時, ,重置重置 為單位矩陣為單位矩陣 nkH并以當(dāng)前設(shè)計(jì)點(diǎn)位初始點(diǎn)并以當(dāng)前

35、設(shè)計(jì)點(diǎn)位初始點(diǎn) ；01kXX（7 7）計(jì)算矩陣）計(jì)算矩陣 1kkkHHE，置，置 1kk，返回到，返回到3 3。 機(jī)械優(yōu)化設(shè)計(jì)5 5、變尺度法、變尺度法計(jì)算程序框圖計(jì)算程序框圖機(jī)械優(yōu)化設(shè)計(jì)5 5、DFPDFP算法算法 DFP DFP算法的計(jì)算步驟和變尺度法的一半步驟相同，只是算法的計(jì)算步驟和變尺度法的一半步驟相同，只是具體計(jì)算校正矩陣時按公式：具體計(jì)算校正矩陣時按公式： 1(0,1,2)TTkkkkkkkkTTkkkkks sH y yHHHksyyH y例：用例：用DFPDFP算法求算法求 221212112,242f x xxxxx x的極值解。（求解過程詳見教材）的極值解。（求解過程詳見

36、教材） DFP DFP算法是由戴維頓（算法是由戴維頓（DavidonDavidon）于）于19531953年提出，又于年提出，又于19631963年由弗萊徹年由弗萊徹(Fletcher)(Fletcher)和鮑威爾加以發(fā)展，稱為現(xiàn)代和鮑威爾加以發(fā)展，稱為現(xiàn)代公認(rèn)較好的算法之一。公認(rèn)較好的算法之一。機(jī)械優(yōu)化設(shè)計(jì)七、坐標(biāo)輪換法七、坐標(biāo)輪換法 坐標(biāo)輪換法坐標(biāo)輪換法是在每次搜索只允許一個變量變是在每次搜索只允許一個變量變化，其余變量保持不變，即沿坐標(biāo)方向輪流進(jìn)行化，其余變量保持不變，即沿坐標(biāo)方向輪流進(jìn)行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪流地搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量（其

37、余變量視為常量）的優(yōu)化問題，轉(zhuǎn)化成單變量（其余變量視為常量）的優(yōu)化問題，因此又稱這種方法為因此又稱這種方法為變量輪換法變量輪換法。輪換過程中。輪換過程中不不需要目標(biāo)函數(shù)的導(dǎo)數(shù)，只需要目標(biāo)函數(shù)信息值需要目標(biāo)函數(shù)的導(dǎo)數(shù)，只需要目標(biāo)函數(shù)信息值。屬于直接法的無約束最優(yōu)化方法。屬于直接法的無約束最優(yōu)化方法。 此類方法適用于此類方法適用于不知道目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)不知道目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)式而僅知其目標(biāo)函數(shù)值信息的情況式而僅知其目標(biāo)函數(shù)值信息的情況。這也是直接。這也是直接法的一個優(yōu)點(diǎn)。法的一個優(yōu)點(diǎn)。機(jī)械優(yōu)化設(shè)計(jì)1、坐標(biāo)輪換法的尋優(yōu)過程、坐標(biāo)輪換法的尋優(yōu)過程 （1 1）從初始點(diǎn)）從初始點(diǎn) 出發(fā)，沿第一個坐標(biāo)方向

38、搜索，即出發(fā)，沿第一個坐標(biāo)方向搜索，即 00 x011de，得，得 按照一維搜索方法確定按照一維搜索方法確定00001011xxd最佳步長因子最佳步長因子 滿足滿足010001min f xd （2 2）從）從 出發(fā)，沿出發(fā)，沿 01x022de方向搜索得方向搜索得 00002122xxd其中：步長因子其中：步長因子 滿足：滿足： 020012min f xd02x為一輪為一輪 終點(diǎn)。終點(diǎn)。 0k （3 3）檢驗(yàn)始終點(diǎn)的距離是否滿）檢驗(yàn)始終點(diǎn)的距離是否滿足精度要求。滿足結(jié)束；不滿足精度要求。滿足結(jié)束；不滿足足 ，開始新一輪。，開始新一輪。 1002xx機(jī)械優(yōu)化設(shè)計(jì)結(jié)論：結(jié)論：對于對于 個變量的

39、函數(shù)，若在第個變量的函數(shù)，若在第 輪沿第個輪沿第個 坐標(biāo)坐標(biāo)nki方向方向 進(jìn)行搜索，其迭代公式為：進(jìn)行搜索，其迭代公式為： kid1(0,1,2,1,2,)kkkkiiiixxdkin其中搜索方向取坐標(biāo)方向，即其中搜索方向取坐標(biāo)方向，即 1,kiide in若若 0kknxx則則 knxx，否則，否則 10kknxx進(jìn)行下進(jìn)行下 一輪搜索，一直到滿足精度應(yīng)要求為止。一輪搜索，一直到滿足精度應(yīng)要求為止。機(jī)械優(yōu)化設(shè)計(jì)2 2、程序框圖、程序框圖 機(jī)械優(yōu)化設(shè)計(jì)3 3、坐標(biāo)輪換法的特點(diǎn)、坐標(biāo)輪換法的特點(diǎn)（1 1）收斂效果與目標(biāo)函數(shù)等值線的形狀有很大關(guān)系。）收斂效果與目標(biāo)函數(shù)等值線的形狀有很大關(guān)系。（2

40、 2）搜索只能輪流沿著坐標(biāo)方向搜索，要經(jīng)過多次）搜索只能輪流沿著坐標(biāo)方向搜索，要經(jīng)過多次曲折迂回的路徑才能達(dá)到極小點(diǎn)，在極值點(diǎn)附近收曲折迂回的路徑才能達(dá)到極小點(diǎn)，在極值點(diǎn)附近收斂速度很慢。斂速度很慢。機(jī)械優(yōu)化設(shè)計(jì)八、八、 鮑威爾（鮑威爾（PowellPowell）方法）方法( (方向加速法方向加速法) ) 自學(xué)自學(xué)概述：概述：PowellPowell法是以法是以共軛方向?yàn)榛A(chǔ)共軛方向?yàn)榛A(chǔ)的收斂較快的收斂較快的直接法之一，是一種十分有效的算法。的直接法之一，是一種十分有效的算法。 1964 1964年，年，PowellPowell提出這種算法，其基本思想提出這種算法，其基本思想是是直接利用迭代

41、點(diǎn)的目標(biāo)函數(shù)值直接利用迭代點(diǎn)的目標(biāo)函數(shù)值來構(gòu)造共軛方向，來構(gòu)造共軛方向，然后，從任一初始點(diǎn)開始，然后，從任一初始點(diǎn)開始，逐次沿共軛方向作一逐次沿共軛方向作一維搜索求極小點(diǎn)維搜索求極小點(diǎn)。并在以后的實(shí)踐中進(jìn)行了改進(jìn)。并在以后的實(shí)踐中進(jìn)行了改進(jìn)。機(jī)械優(yōu)化設(shè)計(jì)對于二次函數(shù)對于二次函數(shù)12TTfXX GXb Xc基本思想：基本思想：在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造G G的共的共軛方向。軛方向。1、共軛方向的生成、共軛方向的生成設(shè)設(shè) 為從不為從不同點(diǎn)出發(fā)，沿同一方同點(diǎn)出發(fā)，沿同一方向向 進(jìn)行一維搜索進(jìn)行一維搜索而得到的兩個極小點(diǎn)。而得到的兩個極小點(diǎn)。1,kkxxj

42、d機(jī)械優(yōu)化設(shè)計(jì)由梯度和等值面垂直的性質(zhì)，由梯度和等值面垂直的性質(zhì)， 和和 兩點(diǎn)處兩點(diǎn)處的梯度的梯度 之間存在關(guān)系：之間存在關(guān)系：jd1,kkxxbGxgbGxgkkkk11,0)()()()(11kkTjkkTjxxGdggd0)(, 0)(1kTjkTjgdgd1,kkgg1,kkxx另一方面，對于上述二次函數(shù)，其另一方面，對于上述二次函數(shù)，其 兩點(diǎn)處的梯兩點(diǎn)處的梯度可表示為：度可表示為：將兩式相減可得：將兩式相減可得：取方向取方向kkkxxd1結(jié)論結(jié)論：這說明要沿：這說明要沿 方向分別對函數(shù)作兩次一維搜索，方向分別對函數(shù)作兩次一維搜索，得到兩個極小點(diǎn)得到兩個極小點(diǎn) ，那么這兩點(diǎn)的連線所給出的，那么這兩點(diǎn)的連線所給出的方向方向 就是與就是與 一起對一起對G G共軛的方向。共軛的方向。jd1,kkxxkdjd機(jī)械優(yōu)化設(shè)計(jì)機(jī)械優(yōu)化設(shè)計(jì)2、基本算法（以二維情況為例）、基本算法（以二維情況為例）1）任選一初始點(diǎn)）任選一初始點(diǎn)x0，再選兩個線性無關(guān)的向再選兩個線性無關(guān)的向量如坐標(biāo)軸的單位向量量如坐標(biāo)軸的單位向量e1=1,0T和和e1=0,1e1=0,1T T本本作為初始搜索方向；