1、優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法第四章 無約束優(yōu)化計算方法4.1 引言4.2 單變量優(yōu)化計算方法4.3 多變量優(yōu)化計算的非梯度方法4.4 多變量優(yōu)化計算的梯度方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 求解優(yōu)化問題的基本解法有：求解優(yōu)化問題的基本解法有： 即利用數(shù)學(xué)分析即利用數(shù)學(xué)分析( (微分、變分等）的方法，根據(jù)微分、變分等）的方法，根據(jù)函數(shù)（泛函）極值的必要條件和充分條件求出其最優(yōu)解析函數(shù)（泛函）極值的必要條件和充分條件求出其最優(yōu)解析解的解的求解方法求解方法 。在目標(biāo)函數(shù)比較簡單時，求解還可以。在目標(biāo)函數(shù)比較簡單時，求解還可以。 局限性：局限性：工程優(yōu)化問題的目標(biāo)函數(shù)和約束條件往往比較復(fù)工程優(yōu)化問題的目標(biāo)函數(shù)和

2、約束條件往往比較復(fù)雜，有時甚至還無法用數(shù)學(xué)方程描述，在這種情況下應(yīng)用數(shù)雜，有時甚至還無法用數(shù)學(xué)方程描述，在這種情況下應(yīng)用數(shù)學(xué)分析方法就會帶來麻煩。學(xué)分析方法就會帶來麻煩。4.1 引言引言優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 數(shù)值迭代法的數(shù)值迭代法的是進行反復(fù)的數(shù)值計算，尋是進行反復(fù)的數(shù)值計算，尋求求目標(biāo)目標(biāo)函數(shù)值不斷函數(shù)值不斷下降下降的可行計算點，直到最后獲得足夠精的可行計算點，直到最后獲得足夠精度的度的最優(yōu)點最優(yōu)點。這種方法的求優(yōu)過程大致可歸納為以下步驟：這種方法的求優(yōu)過程大致可歸納為以下步驟： 1 1）首先初選一個盡可能靠近最小點的初始點）首先初選一個盡可能靠近最小點的初始點X X（0 0），從，從X

3、 X（0 0）出發(fā)按照一定的原則尋找可行方向和初始步長，向前跨出一步出發(fā)按照一定的原則尋找可行方向和初始步長，向前跨出一步達到達到X X（1 1）點；點； 2 2）得到新點）得到新點X X（1 1）后再選擇一個新的使函數(shù)值迅速下降的后再選擇一個新的使函數(shù)值迅速下降的方向及適當(dāng)?shù)牟介L，從方向及適當(dāng)?shù)牟介L，從X X（1 1）點出發(fā)再跨出一步，達到點出發(fā)再跨出一步，達到X X（2 2）點，點，并依此類推，一步一步地向前探索并重復(fù)數(shù)值計算，最終達到并依此類推，一步一步地向前探索并重復(fù)數(shù)值計算，最終達到目標(biāo)函數(shù)的最優(yōu)點。目標(biāo)函數(shù)的最優(yōu)點。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法在中間過程中每一步的迭代形式為：在中間過程

4、中每一步的迭代形式為：(1)( )( )( )(1)( )()()kkkkkkSFF k=0,1,2,xxxx 上式中：上式中：X X（k k）第第k k步迭代計算所得到的點，稱第步迭代計算所得到的點，稱第k k步迭代點，步迭代點， 亦為第亦為第k k步設(shè)計方案；步設(shè)計方案； a a（k k）第第k k步迭代計算的步長；步迭代計算的步長； S S（k k）第第k k步迭代計算的探索方向。步迭代計算的探索方向。迭代計算機逐步逼近最優(yōu)點過程示意圖迭代計算機逐步逼近最優(yōu)點過程示意圖 用迭代法逐步逼近最優(yōu)用迭代法逐步逼近最優(yōu)點的探索過程如圖所示。點的探索過程如圖所示。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 運用迭代

5、法，每次迭代所得新的點的目標(biāo)函數(shù)運用迭代法，每次迭代所得新的點的目標(biāo)函數(shù)都應(yīng)滿足函數(shù)值下降的要求：都應(yīng)滿足函數(shù)值下降的要求：(1)()()()kkFFxx(1)( )( )( )kkkkS xx（3）給定收斂準則）給定收斂準則迭代法要解決的問題：迭代法要解決的問題：終止準則終止準則準則1-點距準則(1)3()kfX準則2 -下降準則： (1)( )( )( )1kkkksXX (1)( )2()()kkffXX準則3-梯度準則 往往采用兩個準則來判別 （1）f(x)在x*附近比較平坦 (1)( )1()kkf xf x (1)( )2kkxx 往往采用兩個準則來判別（2） f(x)在X*附近比

6、較陡峭 (1)1()kkf xf x 12kkxx 結(jié)論：結(jié)論：由于不知道函數(shù)的具體形態(tài)，有時用兩個準則判斷更可靠！優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 當(dāng)采用數(shù)學(xué)規(guī)劃法尋求多元函數(shù)的極值點時當(dāng)采用數(shù)學(xué)規(guī)劃法尋求多元函數(shù)的極值點時，一般要進行一系列如下格式的迭代計算，一般要進行一系列如下格式的迭代計算:當(dāng)方向當(dāng)方向 給定，求最佳步長給定，求最佳步長 就是求一元函數(shù)就是求一元函數(shù) :( )ks( )k(1)( )( )( )( )()()()kkkkkffs xx的極值問題，這一過程被稱為一維搜索的極值問題，這一過程被稱為一維搜索. . (1)( )( )( )kkkkS xx優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法(1)

7、( )( )( )kkkkS xx一維搜索的最優(yōu)化方法一維搜索的最優(yōu)化方法-分析法分析法 例例 已知極小值在區(qū)間 內(nèi)，若從 點出發(fā)，根據(jù)迭代公式： 2min( )f xx1 1(0)1x (1)(0)(0)xxs(0)11( )22xxsf xx 取(1)12x 優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法(1)x( )f x2( )( 12 )f ( )2( 12 ) 24 ( 12 )dfd ( )0dfd4 ( 12 )0 12(1)11202x (1)0()20 xf xx*(1)0 xx*()f x將代入得：令 得： 將（3-3）代入（3-2）得： 因為 滿足準則3所以 =0（3-3）（3-2）優(yōu)化設(shè)計

8、方法優(yōu)化設(shè)計方法 由舉例可知，由舉例可知， 一維搜索方法解析法利用一一維搜索方法解析法利用一維函數(shù)的極值條件：維函數(shù)的極值條件：一維搜索方法數(shù)值解法分類一維搜索方法數(shù)值解法分類試探法插值法*()0kk ， 求后代入迭代公式后求解 一維搜索也稱直線搜索。這種方法不僅對一維搜索也稱直線搜索。這種方法不僅對于解決一維最優(yōu)化本身具有實際意義，而且也于解決一維最優(yōu)化本身具有實際意義，而且也是解多維最優(yōu)化問題的重要支柱。是解多維最優(yōu)化問題的重要支柱。4.2.1 進退法（確定搜索區(qū)間） 進退法也稱外推法，是一種通過比較函數(shù)值大小來確定單峰區(qū)間的方法。任意給定初始點 X1和步長h，算出f(x1) 和 x2=x

9、1+h 點的 f(x2)函數(shù)值。 圖(a)f(x1) f(x2) ，說明x*x1，將步長增加一倍，取x3=x2+2h ； 圖(b) f(x1) f(x2) ，說明x*f2, 應(yīng)在原方向繼續(xù)向前探測。應(yīng)在原方向繼續(xù)向前探測。x3= x2+h=1+1=2, f3=f(x3)=18由于由于f2f3,可知初始區(qū)間已經(jīng)找到，即可知初始區(qū)間已經(jīng)找到，即a,b=x1,x2=0,22）用黃金分割法縮小區(qū)間）用黃金分割法縮小區(qū)間 第一次縮小區(qū)間：第一次縮小區(qū)間： x1=0+0.382X X(2-0)=0.764, f1=0.282 x2=0+0.618 X X(2-0)=1.236, f2=2.72 f10.2

10、優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 第二次縮小區(qū)間：第二次縮小區(qū)間： 令令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382X(1.236-0)=0.472, f1=0.317 由于由于f1f2, 故新區(qū)間故新區(qū)間a,b=x1,b=0.472, 1.236 因為因為 b-a=1.236-0.472=0.7640.2, 應(yīng)繼續(xù)應(yīng)繼續(xù)縮小區(qū)間。縮小區(qū)間。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 第三次縮小區(qū)間：第三次縮小區(qū)間：l令令 x1=x2=0.764, f1=f2=0.282l x2=0.472+0.618X X(1.236-0.472)=0.944, f2=0.747l由于由于f10.2, 應(yīng)

11、繼續(xù)縮小區(qū)間。應(yīng)繼續(xù)縮小區(qū)間。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 第四次縮小區(qū)間：第四次縮小區(qū)間： 令令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382X(0.944-0.472)=0.652, f1=0.223 由于由于f10.2, 應(yīng)繼續(xù)縮應(yīng)繼續(xù)縮小區(qū)間。小區(qū)間。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法第五次縮小區(qū)間：第五次縮小區(qū)間：l令令 x2=x1=0.652, f2=f1=0.223l x1=0.472+0.382X X(0.764-0.472)=0.584, f1=0.262l由于由于f1f2, 故新區(qū)間故新區(qū)間a,b=x1,b=0.584, 0.764l因為因為 b-a=0

12、.764-0.584=0.180.2, 停止迭代。停止迭代。極小點與極小值：極小點與極小值：x*=0.5X X(0.584+0.764)=0.674, f(x*)=0.222思考題思考題： 試用黃金分割法求 近似極小點及極小值。已知a,b=0,2，=0.01（只要求進行2輪迭代，判斷是否收斂）。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法一維搜索的插值方法 假定我們的問題是在某一確定區(qū)間內(nèi)尋求函數(shù)的極小點位置，雖然沒有函數(shù)表達式，但能夠給出若干試驗點處的函數(shù)值。我們可以根據(jù)這些點處的函數(shù)值，利用插值方法建立函數(shù)的某種近似表達式，進而求出函數(shù)的極小點，并用它作為原來函數(shù)極小點的近似值。這種方法稱作插值方法插值方法，

13、 又稱作函數(shù)迫近法函數(shù)迫近法。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法二次插值法（拋物線法）二次插值法（拋物線法）l 二次插值的基本思想是利用目標(biāo)函數(shù)在不同二次插值的基本思想是利用目標(biāo)函數(shù)在不同3點的函數(shù)值構(gòu)點的函數(shù)值構(gòu)成一個與原函數(shù)成一個與原函數(shù)f( (x) )相近似的二次多項式相近似的二次多項式p(x)，以函數(shù)，以函數(shù)p(x)的極的極值點值點 (即即p(x*p)=0的根的根)作為目標(biāo)函數(shù)作為目標(biāo)函數(shù)f( (x) )的近似極值點。的近似極值點。 *pxx23p2p1f3x*1xf(x)p(x)xx1p3f2fp優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)

14、化設(shè)計方法優(yōu)化設(shè)計方法例例1 用二次插值法求函數(shù)用二次插值法求函數(shù)f(x)= 3x3-4x+2的極小點，給的極小點，給定定 x0=0, =0.2。 解解 1）確定初始區(qū)間）確定初始區(qū)間 初始區(qū)間初始區(qū)間a,b=0,2, 中間點中間點x2=1。2）用二次插值法逼近極小點）用二次插值法逼近極小點相鄰三點的函數(shù)值相鄰三點的函數(shù)值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：代入公式：222222*2313121232313121231 ()()()2 ()()()pxxfxxfxxfxxxfxx fxxfxp*0.555, fp=0.292優(yōu)化設(shè)計方法優(yōu)化設(shè)

15、計方法 在新區(qū)間，相鄰三點的函數(shù)值在新區(qū)間，相鄰三點的函數(shù)值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1. xp*0.607, fp=0.243 由于由于fpx2, 新區(qū)間新區(qū)間a,b=x2, b=0.555,1 |x2-xp * |=|0.555-0.607|=0.0520.2, 迭代終止。迭代終止。 xp*0.607, f*=0.243由于由于fpf2, xp * 0.2, 應(yīng)繼續(xù)迭代。應(yīng)繼續(xù)迭代。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 坐標(biāo)輪換法坐標(biāo)輪換法是每次搜索只允許一個變量變化，其

16、余變量保持不變，即沿坐標(biāo)方向輪流進行搜索的尋憂方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量(其余變量視為常量)的優(yōu)化問題，因此又稱這種方法為變量輪換法變量輪換法。 在搜索過程中可以不需要目標(biāo)函數(shù)的導(dǎo)數(shù)，只需目標(biāo)函數(shù)值信息。這比前面所討論的利用目標(biāo)函數(shù)導(dǎo)數(shù)信息建立搜索方向的方法要簡單得多。4.3.1 坐標(biāo)輪換法坐標(biāo)輪換法4.3 多變量優(yōu)化計算的非梯度方法多變量優(yōu)化計算的非梯度方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法（1）計算量少，程序簡單，不需要求函數(shù)導(dǎo)數(shù)的直接）計算量少，程序簡單，不需要求函數(shù)導(dǎo)數(shù)的直接探索目標(biāo)函數(shù)最優(yōu)解的方法；探索目

17、標(biāo)函數(shù)最優(yōu)解的方法；（2）探索路線較長，問題的維數(shù)愈多求解的效率愈低。）探索路線較長，問題的維數(shù)愈多求解的效率愈低。當(dāng)維數(shù)當(dāng)維數(shù)n10時，則不應(yīng)采用此法。僅適用于時，則不應(yīng)采用此法。僅適用于n較少（較少（n 0，通常取，通常取a=1； （1 1）令）令, 2 , 1,100niiXXXniheXX構(gòu)造單純形；輸出輸出XL，為原問題近似極小點；否則，轉(zhuǎn)（，為原問題近似極小點；否則，轉(zhuǎn)（2）。）。構(gòu)造新單純形；構(gòu)造新單純形；5 . 0（4）根據(jù)不同）根據(jù)不同情情況，分別進行擴張，況，分別進行擴張，收縮或縮邊，其中收縮因子收縮或縮邊，其中收縮因子1121max )()(LiniLiXXXfXf（5）

18、如果滿足）如果滿足優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 1、坐標(biāo)輪換法、坐標(biāo)輪換法 計算效率較低計算效率較低 適合維數(shù)較低，目標(biāo)函數(shù)無導(dǎo)數(shù)或?qū)?shù)較難求得適合維數(shù)較低，目標(biāo)函數(shù)無導(dǎo)數(shù)或?qū)?shù)較難求得 2、Powell法法 具有二次收斂性，收斂速度較快，可靠性高，被認為是具有二次收斂性，收斂速度較快，可靠性高，被認為是直接法中最有效的方法之一直接法中最有效的方法之一 3、單純形法、單純形法 思路清楚，收斂慢思路清楚，收斂慢優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法4.4 梯度法梯度法(1)( )( )( )(0,1,2,)kkkkskxx(1)( )( )( )() (0,1,2,)kkkkafkxxx

19、基本思想基本思想：函數(shù)的負梯度方向是函數(shù)值在該點：函數(shù)的負梯度方向是函數(shù)值在該點下降最快的方向。將下降最快的方向。將n n維問題轉(zhuǎn)化為一系列沿負梯度維問題轉(zhuǎn)化為一系列沿負梯度方向用一維搜索方法尋優(yōu)的問題，利用負梯度作為方向用一維搜索方法尋優(yōu)的問題，利用負梯度作為搜索方向，故稱最速下降法或梯度法。搜索方向，故稱最速下降法或梯度法。 ( )fx 搜索方向搜索方向s取該點的負梯度方向取該點的負梯度方向 (最速下降方最速下降方向向) ，使函數(shù)值在該點附近的范圍內(nèi)下降最快，使函數(shù)值在該點附近的范圍內(nèi)下降最快 。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 為了使目標(biāo)函數(shù)值沿搜索方向為了使目標(biāo)函數(shù)值沿搜索方向 能夠獲能夠獲得

20、最大的下降值，其步長因子得最大的下降值，其步長因子 應(yīng)取一維搜索的最應(yīng)取一維搜索的最佳步長。即有佳步長。即有()kf xk()(1)( )( )( )( )()()min()min ( )kkkkkkaaffaffa f xxxxx 根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合根據(jù)一元函數(shù)極值的必要條件和多元復(fù)合函數(shù)求導(dǎo)公式，得函數(shù)求導(dǎo)公式，得 ( )( )( )( )()()0Tkkkkfff xxx(1)( )()()0kTkffxx(1)( )()0kTkss優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 在最速下降法中，在最速下降法中，相鄰兩個迭代點上的函相鄰兩個迭代點上的函數(shù)梯度相互垂直。而搜數(shù)梯度相互垂直。而搜

21、索方向就是負梯度方向，索方向就是負梯度方向，因此相鄰兩個搜索方向因此相鄰兩個搜索方向互相垂直。這就是說在互相垂直。這就是說在迭代點向函數(shù)極小點靠迭代點向函數(shù)極小點靠近的過程，走的是曲折近的過程，走的是曲折的路線。形成的路線。形成“之之”字字形的鋸齒現(xiàn)象，而且越形的鋸齒現(xiàn)象，而且越接近極小點鋸齒越細。接近極小點鋸齒越細。 最速下降法的搜索路徑最速下降法的搜索路徑優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法方法特點方法特點（1 1）初始點可任選，每次迭代計算量小，存儲）初始點可任選，每次迭代計算量小，存儲量少，程序簡短。即使從一個不好的初始點出量少，程序簡短。即使從一個不好的初始點出發(fā)，開始的

22、幾步迭代，目標(biāo)函數(shù)值下降很快，發(fā)，開始的幾步迭代，目標(biāo)函數(shù)值下降很快，然后慢慢逼近局部極小點。然后慢慢逼近局部極小點。 （2 2）任意相鄰兩點的搜索方向是正交的，它的）任意相鄰兩點的搜索方向是正交的，它的迭代路徑為繞道逼近極小點。當(dāng)?shù)c接近極迭代路徑為繞道逼近極小點。當(dāng)?shù)c接近極小點時，步長變得很小，越走越慢。小點時，步長變得很小，越走越慢。 優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法00102()10424()50100 xfxfxxx沿負梯度方向進行一維搜索，有沿負梯度方向進行一維搜索，有01000024()2 100fxxx0為一維搜索最佳步長，應(yīng)滿足極值必要條件為一維搜索最佳步長，應(yīng)滿足極值必要條件

23、 122()min (24 )25(2100 )min ( )f x例例4 41 1 求目標(biāo)函數(shù)求目標(biāo)函數(shù) 的極小點。的極小點。解解 取初始點取初始點則初始點處函數(shù)值及梯度分別為則初始點處函數(shù)值及梯度分別為02,2Tx2212( )25fxxx優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法00( )8(24)5 000(2 100)0 算出一維搜索最佳步長算出一維搜索最佳步長 06260.020 030 7231 252第一次迭代設(shè)計點位置和函數(shù)值第一次迭代設(shè)計點位置和函數(shù)值 0120241.919 8772 1000.307178 5 10 x1()3.686164fx繼續(xù)作下去，經(jīng)繼續(xù)作下去，經(jīng)1010次迭代后

24、，得到最優(yōu)解次迭代后，得到最優(yōu)解 00Tx()0fx優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 這個問題的目標(biāo)函數(shù)的等值線為一簇橢圓這個問題的目標(biāo)函數(shù)的等值線為一簇橢圓, ,迭代點從迭代點從 走的是一段鋸齒形路線，見圖。走的是一段鋸齒形路線，見圖。0 x優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法將上例中目標(biāo)函數(shù)將上例中目標(biāo)函數(shù) 引入變換引入變換2212( )25fxxx221212(,)y yyy其等值線由橢圓變成一簇同心圓。其等值線由橢圓變成一簇同心圓。 仍從仍從 即即 出發(fā)進行最速下降法出發(fā)進行最速下降法尋優(yōu)。此時：尋優(yōu)。此時：02,2Tx02,10Ty00102()10424()220yyyyy沿負梯度方向進行一維搜索：沿

25、負梯度方向進行一維搜索：則函數(shù)則函數(shù)f(f(X X) )變?yōu)椋鹤優(yōu)椋簓1=x1, y2=5x2優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法1000000()242410201020yyy為一維搜索最佳步長，可由極值條件：為一維搜索最佳步長，可由極值條件：10022()min ()min( )( )(24 )(1020 ) yyy0()0由由0260.552從而算得一步計算后設(shè)計點的位置及其目標(biāo)函數(shù)：從而算得一步計算后設(shè)計點的位置及其目標(biāo)函數(shù)：優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法010124010200()0 yy經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是因為經(jīng)過尺度變換：這是因為經(jīng)過

26、尺度變換：11225yxyx等值線由橢圓變成圓。等值線由橢圓變成圓。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法共軛梯度法共軛梯度法 共軛梯度法中每一個共軛向量都是依賴共軛梯度法中每一個共軛向量都是依賴于迭代點處的負梯度而構(gòu)造出來。于迭代點處的負梯度而構(gòu)造出來。 從從x(k)出發(fā)，沿負梯度方向作一維搜索出發(fā)，沿負梯度方向作一維搜索:(1)( )( )( )(0,1,2,)kkkkskxx()()()kksf x設(shè)與設(shè)與sk共共軛的下一個方向軛的下一個方向sk+1由由sk和點和點xk+1的負梯的負梯度的線形組合構(gòu)成，即：度的線形組合構(gòu)成，即：(1)(1)( )()kkkksfs x( )2(1)()( )0kTks

27、fsx共軛條件：共軛條件：優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 則：則：21()( )()0kTkkkfffs xxx解得：解得：212()()()()()()kTkkkkTkkffffffxxxxxx令令1( )2TfTxx Gxb xc為函數(shù)的泰勒二次展開式為函數(shù)的泰勒二次展開式()kkfxGxb則則11()kkfxGxb上兩式相減，并代入上兩式相減，并代入( )(1)( )( )kkkksxx( )( )(1)( )()()kkkksff Gxx優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法1()()kkkksffGxx將式將式11()kkkksfs x與式與式轉(zhuǎn)置兩邊相乘，應(yīng)用轉(zhuǎn)置兩邊相乘，應(yīng)用共軛條件共軛條件得：得：

28、11()() ()()0kkTkkkffff xxxx21112()()()()()()kkTkkkTkkffffffxxxxxx因此因此(1)(1)( )()kkkksfs x212()()kkkffxx(1)( )( )( )(0,1,2,)kkkkskxx優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法2212112( )242fxxxx xx，已知初始點，已知初始點1,11,1T Tl解：解： 1）第一次沿負梯度方向搜尋）第一次沿負梯度方向搜尋l計算初始點處的梯度計算初始點處的梯度0120212244()422xxfxxxx010000014141 212s xx為一維搜索最佳步長，應(yīng)

29、滿足為一維搜索最佳步長，應(yīng)滿足1002()min()min(40203)ffsxxl迭代精度迭代精度 。 0.001優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法得得:00.25120.5x2）第二次迭代：）第二次迭代：21200()50.2520()ffxx11()2fx11002()1.5sfs x21122220.51.50.5 1.5sxx代入目標(biāo)函數(shù)代入目標(biāo)函數(shù)22( )(22 )2(0.5 1.5 )2(22 )(0.5 1.5 )4(22 )( )f x 優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法得得1因因2()0fx收斂。收斂。( )0 由由22240,()8,()20ff xxx從而有：從而有：優(yōu)化設(shè)計方法優(yōu)化設(shè)計

30、方法梯度法的特點梯度法的特點 （1）理論明確，程序簡單，對初始點要求不嚴格。）理論明確，程序簡單，對初始點要求不嚴格。 （2）對一般函數(shù)而言，梯度法的收斂速度并不快，因）對一般函數(shù)而言，梯度法的收斂速度并不快，因為最速下降方向僅僅是指某點的一個局部性質(zhì)。為最速下降方向僅僅是指某點的一個局部性質(zhì)。 （3）梯度法相鄰兩次搜索方向的正交性，決定了迭代）梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈鋸齒狀，在遠離極小點時逼近速度全過程的搜索路線呈鋸齒狀，在遠離極小點時逼近速度較快，而在接近極小點時逼近速度較慢。較快，而在接近極小點時逼近速度較慢。 （4）梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)密

31、切相關(guān)。）梯度法的收斂速度與目標(biāo)函數(shù)的性質(zhì)密切相關(guān)。對于等值線對于等值線(面面)為同心圓（球）的目標(biāo)函數(shù)，一次搜索為同心圓（球）的目標(biāo)函數(shù)，一次搜索即可達到極小點。即可達到極小點。優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法牛頓法及其改進牛頓法及其改進2( )( )()() ()1()()()2kkTkkTkkffffxxxxxxxxxxx設(shè)設(shè) 為為 的極小點的極小點 1kx( )x1()0kx( )x( )x( )f x1kx( )f x21()()()0kkkkffxxxx優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法121()()(0,1,2,)kkkkffk xxxx這就是多元函數(shù)求極值的牛頓法迭代公式。這就是多元函數(shù)求極值的

32、牛頓法迭代公式。 對于二次函數(shù)對于二次函數(shù) ，海賽矩陣海賽矩陣H H是一個常矩陣，其中是一個常矩陣，其中各元素均為常數(shù)。因此，無論從任何點出發(fā)，只各元素均為常數(shù)。因此，無論從任何點出發(fā)，只需一步就可找到極小點。需一步就可找到極小點。 例題：例題： 求目標(biāo)函數(shù)求目標(biāo)函數(shù) 的極小點。的極小點。解解 取初始點取初始點2212( )25fxxx02,2Tx102010102402()()121000050ff xxxx優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法00 x()0fx 從牛頓法迭代公式的推演中可以看到，迭代點的位置是從牛頓法迭代公式的推演中可以看到，迭代點的位置是按照極值條件確定的，其中并未含有沿下降方向搜尋

33、的概按照極值條件確定的，其中并未含有沿下降方向搜尋的概念。因此對于非二次函數(shù)，如果采用上述牛頓迭代公式，念。因此對于非二次函數(shù)，如果采用上述牛頓迭代公式，有時會使函數(shù)值上升有時會使函數(shù)值上升 。阻尼牛頓法阻尼牛頓法 121()()(0,1,2,)kkkkkkkksffkxxxxxk阻尼因子阻尼因子 ，沿牛頓方向進行一維搜索的最佳步長，沿牛頓方向進行一維搜索的最佳步長，由下式求得：由下式求得： 1()()min()kkkkkkkffsfsxxx經(jīng)過一次迭代即求得極小點經(jīng)過一次迭代即求得極小點函數(shù)極小值函數(shù)極小值優(yōu)化設(shè)計方法優(yōu)化設(shè)計方法 這樣，原來的牛頓法就相當(dāng)于阻尼牛頓法的步長因子k 取成固定值1的情況。 由于阻尼牛頓法每次迭代都在牛頓方向上進行一維搜索，這就避免了迭代后函數(shù)值上升