《機械優(yōu)化設(shè)計（第7版）》課件 孫靖民 第3章一維搜索方法；第4章無約束優(yōu)化方法

機械優(yōu)化設(shè)計第三章一維搜索方法×第一節(jié)

概述§第二節(jié)

搜索區(qū)間的確定與區(qū)間消去法原理§第三節(jié)

一維搜索的試探方法§第四節(jié)

一維搜索的插值方法§

第三章一維搜索方法

當采用數(shù)學(xué)規(guī)劃法尋求多元函數(shù)的極值點時，一般要進行一系列如下格式的迭代計算：當方向給定，求最佳步長就是求一元函數(shù)的極值問題。這一過程被稱為一維搜索。

§第一節(jié)一維搜索的概念求多元函數(shù)極值點，需要進行一系列的一維搜索?？梢娨痪S搜索是優(yōu)化搜索方法的基礎(chǔ)。求解一元函數(shù)的極小點，可采用解析解法，即利用一元函數(shù)的極值條件求在用函數(shù)的導(dǎo)數(shù)求時，所用的函數(shù)是僅以步長因子為變量的一元函數(shù)，而不是以設(shè)計點x為變量的多元函數(shù)。為了直接利用的函數(shù)式求解最佳步長因子?？砂鸦蛩暮唽懶问竭M行泰勒展開，取到二階項，即將上式對進行微分并令其等于零，給出極值點應(yīng)滿足的條件從而求得這里是直接利用函數(shù)而不需要把它化成步長因子。的函數(shù)。不過，此時需要計算點處的梯度 和海賽矩陣。解析解法的缺點——需要進行求導(dǎo)計算。對于函數(shù)關(guān)系復(fù)雜、求導(dǎo)困難或無法求導(dǎo)的情況，使用解析法將是非常不便的。因此，在優(yōu)化設(shè)計中，求解最佳步長因子主要采用數(shù)值解法，利用計算機通過反復(fù)迭代計算求得最佳步長因子的近似值。數(shù)值解法的基本思路是：首先確定所在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間，從而獲得的數(shù)值近似解。一維搜索是優(yōu)化搜索方法的基礎(chǔ)。*一維搜索方法解析法高等數(shù)學(xué)已學(xué)過，即利用一維函數(shù)的極值條件：

一維搜索也稱直線搜索。這種方法不僅對于解決一維最優(yōu)化本身具有實際意義，而且也是解多維最優(yōu)化問題的重要支柱。求一維搜索方法數(shù)值解法分類1.解析法：

步驟:①f(X(k)+αS(k))沿S(k)

方向在x(k)

點進行泰勒展開；②取二次近似：

對α求導(dǎo)，令其為零。

④求得最優(yōu)步長數(shù)值解法基本思路：

先確定所在的搜索區(qū)間，然后根據(jù)區(qū)間消去法原理不斷縮小此區(qū)間，從而獲得的數(shù)值近似解。解析解法對于函數(shù)關(guān)系復(fù)雜、求導(dǎo)困難等情況難以實現(xiàn)。在實際優(yōu)化設(shè)計中，數(shù)值解法的應(yīng)用更為有效，且適合計算機的運算特點。

一維搜索也稱直線搜索。這種方法不僅對于解決一維最優(yōu)化問題具有實際意義，而且也是求解多維最優(yōu)化問題的重要支柱。一維搜索一般分為兩大步驟：(1)確定初始搜索區(qū)間[a，b]，該區(qū)間應(yīng)是包括一維函數(shù)極小點在內(nèi)的單谷區(qū)間。(2)在單谷區(qū)間[a,b]內(nèi)通過縮小區(qū)間尋找極小點。1、確定搜索區(qū)間的外推法在給定區(qū)間內(nèi)僅有一個谷值（或有唯一的極小點）的函數(shù)稱為單谷函數(shù)，其區(qū)間稱為單谷區(qū)間。函數(shù)值：“大—小—大”圖形：“高—低—高”單谷區(qū)間中一定能求得一個極小點?！斓诙?jié)搜索區(qū)間的確定與區(qū)間消去法原理從開始，以初始步長向前試探。如果函數(shù)值上升，則步長變號，即改變試探方向。如果函數(shù)值下降，則維持原來的試探方向，并將步長加倍。區(qū)間的始點、中間點依次沿試探方向移動一步。此過程一直進行到函數(shù)值再次上升時為止，即可找到搜索區(qū)間的終點。最后得到的三點即為搜索區(qū)間的始點、中間三點和終點，形成函數(shù)值的“高－低－高”趨勢。單谷區(qū)間f(x)0α1α3α0f(x)α3α1說明：單谷區(qū)間內(nèi)，函數(shù)可以有不可微點，也可以是不連續(xù)函數(shù)；外推方法基本思想：對任選一個初始點及初始步長，通過比較這兩點函數(shù)值的大小，確定第三點位置，比較這三點的函數(shù)值大小，確定是否為“高—低—高”形態(tài)。步驟：

1）選定初始點a1，初始步長h=h0，計算y1=f(a1)和y2=f(a1+h)2）比較y1和y2；a）如果y1>y2，向右前進，加大步長h=2h0，轉(zhuǎn)（3）向前；b）如果y1<y2，向左后退，h=-2h0，將a1和a2,y1和y2的值互換。轉(zhuǎn)（3）向后探測；c）如果y1=y2，極小點在a1和a1+h之間。3）產(chǎn)生新的探測點a3=a2+h，y3=f(a3)；4）比較函數(shù)值y2和y3：a）如果y2>y3

，加大步長h=2h，a1=a2,a2=a3,轉(zhuǎn)（3）繼續(xù)探測；b）如果y2<y3，則初始區(qū)間得到：a=min[a1,a3],b=max[a1,a3]，函數(shù)最小值所在區(qū)間為[a,b]。右圖表示沿的正向試探。每走一步都將區(qū)間的始點、中間點沿試探方向移動一步（進行換名）。經(jīng)過三步最后確定搜索間，并且得到區(qū)間始點、中間點和終點所對應(yīng)的函數(shù)值。y1y3→y2y2→y1a3→a2a2→a1a1Oaa3h0h02h0圖3-2正向搜索的外推法右圖所表示的情況是：開始是沿的正方向試探，但由于函數(shù)值上升而改變了試探方向，最后得到始點，中間點和終點及它們的對應(yīng)函數(shù)值，從而形成單谷區(qū)間為一維搜索區(qū)間。y1←y2a2←a3a1←a2←a1Oaa32h0h0h0y3y1←y2←y1y2←y3a1←a2圖3-3反向搜索的外推法khx1x2x30h0初始點初始點+h012h0初始點初始點+h0初始點+3h024h0初始點+h0初始點+3h0初始點+7h038h0初始點+3h0初始點+7h0初始點+15h0前進搜索步驟表khx1x2x30h0初始點初始點+h012h0初始點+h0初始點初始點-2h024h0初始點初始點-2h0初始點-6h038h0初始點-2h0初始點-6h0初始點-14h0后退搜索步驟表khx1y1x2y2x3y300.10.2090.18.2030.36.68110.40.18.2030.36.6810.74.42920.80.36.6810.74.4291.57.125khx1y1x2y2x3y300.1-0.21.812.0961.914.3771.914.3771.812.0961.68.4881-0.41.812.0961.68.4881.24.5842-0.81.68.4881.24.5840.45.9922、區(qū)間消去法原理基本思想：

，搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，從而找到極小點的數(shù)值近似解。在搜索區(qū)間內(nèi)任取兩點且計算其函數(shù)值得如下于是將有下列三種可能情形：(1)f（a1）<f（b1）,則極小點必在區(qū)間[a，b1]內(nèi);(2)f（a1）>f（b1）,則極小點必在區(qū)間[α1，b]內(nèi);(3)f（a1）=f（b1）,則極小點必在區(qū)間[α1，b1]內(nèi)f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1a1b1baababb1b1根據(jù)以上所述，只要在區(qū)間[a,b]內(nèi)取兩個點，算出它們的函數(shù)值并加以比較，就可以把搜索區(qū)間[a,b]縮短成[a,b1]，[α1，b]

或

[α1，b1]。對于第一種情況，我們已算出區(qū)間[a,b1]內(nèi)α1點的函數(shù)值，如果要把搜索區(qū)間[a,b1]進一步縮短，只需在其內(nèi)再取一點算出函數(shù)值并與f（α1）加以比較，即可達到目的。對于第二種情況，同樣只需再計算一點函數(shù)值就可以把搜索區(qū)間繼續(xù)縮短。第三種情形與前面兩種情形不同，因為在區(qū)間

[α1，b1]內(nèi)缺少已算出的函數(shù)值。要想把區(qū)間[α1，b1]進一步縮短，需在其內(nèi)部取兩個點（而不是一個點）計算出相應(yīng)的函數(shù)值再加以比較才行。如果經(jīng)常發(fā)生這種情形，為了縮短搜索區(qū)間，需要多計算一倍數(shù)量的函數(shù)值，這就增加了計算工作量。程序設(shè)計技巧為了避免多計算函數(shù)值，我們把第三種情形合并到前面兩種情形中去。例如，可以把前面三種情形改為下列兩種情形：從上述的分析中可知，為了每次縮短區(qū)間，只需要在區(qū)間內(nèi)再插入一點并計算其函數(shù)值。如此反復(fù)進行下去，當搜索區(qū)間長度足夠小時，可用區(qū)間內(nèi)的某點作為極小點的近似值。①若則取為縮短后的搜索區(qū)間。②若則取為縮短后的搜索區(qū)間。3、一維搜索方法分類

根據(jù)插入點位置的確定方法，可以把一維搜索法分成兩大類：試探法：即按照某種規(guī)律來確定區(qū)間內(nèi)插入點的位置，此點位置的確定僅僅按照區(qū)間縮短如何加快，而不顧及函數(shù)值的分布關(guān)系。如黃金分割法，裴波納契法等。裴波納契數(shù)列：1、1、2、3、5、8、13、21、34、55、89、144

插值法（函數(shù)逼近法）：通過構(gòu)造插值函數(shù)來逼近原函數(shù)，用插值函數(shù)的極小點作為區(qū)間的插入點，如牛頓法（切線法）、二次插值法（拋物線法）、三次插值法等。概述在實際計算中，最常用的一維搜索試探方法是黃金分割法，又稱作0.618法。我們可以通過學(xué)習(xí)黃金分割法來了解一維搜索試探方法的基本思想。在搜索區(qū)間[a,b]內(nèi)適當插入兩點α1、α2，并計算其函數(shù)值。α1、α2將區(qū)間分成三段。應(yīng)用函數(shù)的單谷性質(zhì)，通過函數(shù)值大小的比較，刪去其中一段，使搜索區(qū)間得以縮短。然后再在保留下來的區(qū)間上作同樣的處置，如此迭代下去，使搜索區(qū)間無限縮小，從而得到極小點的數(shù)值近似解?！斓谌?jié)一維搜索的試探方法——黃金分割法黃金分割法黃金分割法是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法。適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求“單谷”外不作其它要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當廣。黃金分割法對插入點的要求：

1）要求插入點α1、α2的位置相對于區(qū)間[a,b]兩端點具有對稱性，即

其中為待定常數(shù)。2）黃金分割法還要求在保留下來的區(qū)間內(nèi)再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。即每次縮小所得的新區(qū)間長度與縮小前區(qū)間長度之比（即：區(qū)間收縮率）為定值。設(shè)原區(qū)間[a,b]長度為1如下圖所示，保留下來的區(qū)間[a,α2]長度為，區(qū)間縮短率為。為了保持相同的比例分布，新插入點α3應(yīng)在位置上，α1在原區(qū)間的位置應(yīng)相當于在保留區(qū)間的位置。故有取方程正數(shù)解，得α1、α2將區(qū)間分成三段黃金分割法要求在保留下來的區(qū)間內(nèi)再插入一點所形成的區(qū)間新三段，與原來區(qū)間的三段具有相同的比例分布。兩內(nèi)分點值:結(jié)論：所謂黃金分割是指將一線段分成兩段的方法，使整段長與較長段的長度比值等于較長段與較短段長度的比值即。黃金分割法的搜索過程（1）給出初始搜索區(qū)間及收斂精度，將賦以

（2）按坐標點計算公式計算并計算其對應(yīng)的函數(shù)值

（3）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標點計算公式，進行區(qū)間名稱的代換，并在保留區(qū)間中計算一個新的試驗點及其函數(shù)值。（4）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠近，如果條件不滿足返回到步驟（2）。（5）如果條件滿足，則取最后兩試驗點的平均值作為極小點的數(shù)值近似解?？s短區(qū)間的總次數(shù)（迭代次數(shù)）:黃金分割法程序框圖給定否否是是止也可采用迭代次數(shù)是否大于或等于k作終止準則。舉例對函數(shù)，當給定搜索區(qū)間時，試用黃金分割法求極小點。迭代序號aα1α2bf1比較f20-30.0561.94450.115<7.6671-3-1.1110.0561.944-0.987<0.1152-3-1.832-1.1110.056-0.306>-0.9873-1.832-1.111-0.6650.056-0.987<-0.8884-1.832-1.386-1.111-0.665-0.851>-0.9875-1.386-1.111-0.940-0.665例3-1用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點，給定x0=0,h=1,ε=0.2。解：1）確定初始區(qū)間a1=x0=0,f1=f(a1)=2a2=x0+h=0+1=1,f2=f(a2)=1由于f1>f2,應(yīng)加大步長繼續(xù)向前探測。a3=x0+2h=0+2=2,f3=f(a3)=18由于f2<f3,可知初始區(qū)間已經(jīng)找到，即[a,b]=[a1,a3]=[0,2]2）用黃金分割法縮小區(qū)間

第一次縮小區(qū)間：

a1=0+0.382×(2-0)=0.764,f1=0.282a2=0+0.618×(2-0)=1.236,f2=2.72

f1<f2,新區(qū)間[a,b]=[a,a2]=[0,1.236],b-a>0.2第二次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282

x1=0+0.382X(1.236-0)=0.472,f1=0.317由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.472,1.236]因為b-a=1.236-0.472=0.764>0.2,應(yīng)繼續(xù)縮小區(qū)間。

第三次縮小區(qū)間：令x1=x2=0.764,f1=f2=0.282

x2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.944]因為b-a=0.944-0.472=0.472>0.2,應(yīng)繼續(xù)縮小區(qū)間。

第四次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282

x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.764]因為b-a=0.764-0.472=0.292>0.2,應(yīng)繼續(xù)縮小區(qū)間。第五次縮小區(qū)間：令x2=x1=0.652,f2=f1=0.223

x1=0.472+0.382X(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.584,0.764]因為b-a=0.764-0.584=0.18<0.2,停止迭代。極小點與極小值：x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222§第四節(jié)一維搜索的插值方法概述一維搜索問題是在某一確定區(qū)間內(nèi)尋求一元函數(shù)的極小點的位置，在某些情況下，如果沒有函數(shù)表達式，但能夠給出若干試驗點處的函數(shù)值，就可以根據(jù)這些點處的函數(shù)值，利用插值法建立函數(shù)的某種近似表達式，進而求出函數(shù)的極小點，并用它作為原來函數(shù)極小點的近似值。這種方法稱作插值法，又稱作函數(shù)逼近法。試探法（如黃金分割法）與插值法的比較：不同點：表現(xiàn)在試驗點（插入點）位置的確定方法不同。多項式是函數(shù)逼近的一種常用工具。在搜索區(qū)間內(nèi)可以利用若干試驗點處的函數(shù)值來構(gòu)造低次多項式，用它作為函數(shù)的近似表達式，并用這個多項式的極小點作為原函數(shù)極小點的近似。常用的插值多項式為二次多項式。牛頓法（切線法）利用一點的函數(shù)值、一階導(dǎo)數(shù)值和二階導(dǎo)數(shù)值來構(gòu)造二次函數(shù)。二次插值法（拋物線法）

利用三個點的函數(shù)值形成一個拋物線來構(gòu)造二次函數(shù)。

1、牛頓法（切線法）對于一維搜索函數(shù)，假定已經(jīng)給出極小點的一個較好的近似點，在點附近用一個二次函數(shù)來逼近函數(shù)然后以該二次函數(shù)的極小點作為極小點的一個新的近似點。根據(jù)極值必要條件：牛頓法的幾何解釋：在上圖中，在處用一拋物線代替曲線，相當于用一斜線代替。這樣各個近似點是通過對作切線求得與軸的交點找到，故牛頓法又稱為切線法。牛頓法的計算步驟：1）給定初始點

，控制誤差

，并令

2）計算

3）求

4）若

，則求得近似解，停止計算，否則作5）。

5）令

轉(zhuǎn)2）。

例題：

給定

，試用牛頓法求其極小點。

解：1）給定初始點

，控制誤差

2）3）4）重復(fù)上邊的過程，進行迭代，直到

為止。可得到計算結(jié)果如下表:

表3-2牛頓法的搜索過程k01234值ak35.166674.334744.03964.00066f'(ak)-52153.3518332.301993.382990.00551f"(ak)-24184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059優(yōu)點：收斂速度快。缺點：每一點都要進行二階導(dǎo)數(shù)，工作量大；當用數(shù)值微分代替二階導(dǎo)數(shù)，由于舍入誤差會影響迭代速度；要求初始點離極小點不太遠，否則有可能使極小化發(fā)散或收斂到非極小點。牛頓法的特點：２、二次插值法（拋物線法）基本思想：二次插值的基本思想是利用目標函數(shù)在不同3點的函數(shù)值構(gòu)成一個與原函數(shù)f(x)相近似的二次多項式p(x)，以函數(shù)p(x)的極值點xp(即p’(x*p)=0的根)作為目標函數(shù)f(x)的近似極值點。（1）二次插值多項式的構(gòu)成及其極值點設(shè)在單谷區(qū)間中的三點

的相應(yīng)函數(shù)值

，則可以做出如下的二次插值多項式：多項式

的極值點可從極值的必要條件求得，即

，

為了確定這個極值點，只需計算出系數(shù)a1和a2

。其方法法是利用a0、a1、a2的聯(lián)立方程組中相鄰兩個方程消去a0

，從而得到關(guān)于a1、a2的方程組解得所以如果令則這樣就得到了f(α)極小點α*的近似解αp。

１）如果區(qū)間長度

足夠小，則由

便得出我們所要求的近似極小點

2）如果不滿足，必須縮小區(qū)間

，根據(jù)區(qū)間消取法原理不斷縮小區(qū)間。根據(jù)區(qū)間消去法原理，需要已知區(qū)間內(nèi)兩點的函數(shù)值。其中點α2的函數(shù)值y2=f（α2）已知，另外一點可取αp點并計算其函數(shù)值yp=f（αp）。當y2<yp

時取[α1，αp]為縮短后的搜索區(qū)間（如右圖）。當y2≥yp

時取[α2，α3]為縮短后的搜索區(qū)間。

程序設(shè)計技巧為了在每次計算插入點的坐標時能應(yīng)用同一計算公式，新區(qū)間端點的坐標及函數(shù)值名稱需換成原區(qū)間端點的坐標及函數(shù)值名稱。在每個新區(qū)間上仍取α1、α2、α3三點及其相應(yīng)函數(shù)值y1＞y2＞y3

。這樣當計算插入點（即拋物線極小點αp）位置時仍可以應(yīng)用原來的計算公式。根據(jù)αp與α2的相對位置，yp與y2的大小以及正向搜索（h>0）或反向搜索（h<0）的不同，具體換名有如下表所示的八種情況。（P56)上表中的中的h就是在進行外推法時求初始搜索區(qū)間過程中所形成的最后步長，h可正可負，分別對應(yīng)于沿α

正向或反向進行的一維搜索。分析上述八種換名情況可知，如果乘積的符號相同，那么正向搜索和反向搜索將采取同樣的換名方式，從而可將上述八種情況合并成四種情況，從而可將程序框圖簡化。二次插值法程序框圖例1：用二次插值法求

上的極小點。

12α144.5α24.54.705120α355y1-0.756802-0.977590y2-0.977590-0.999974y3-0.958924-0.958924αp4.7051204.710594yp-0.999974-0.999998二次插值法計算過程示例例2用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點，給定x0=0,ε=0.2。2）用二次插值法逼近極小點相鄰三點的函數(shù)值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入公式：xp*＝0.555,fp=0.292解

1）確定初始區(qū)間初始區(qū)間[a,b]=[0,2],中間點x2=1,f(x2)=1。由于fp<f2,xp*

<x2,新區(qū)間[a,b]=[a,x2]=[0,1]|x2-xp*

|=1-0.555=0.445>0.2,應(yīng)繼續(xù)迭代。在新區(qū)間，相鄰三點的函數(shù)值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1,代入xp*公式計算得：xp*＝0.607,fp=0.243

由于fp<f2,xp>x2,新區(qū)間[a,b]=[x2,b]=[0.555,1]|x2-xp*|=|0.555-0.607|=0.052<0.2,迭代終止。

xp*＝0.607,f*=0.243例3用二次插值法求的極值點。初始搜索區(qū)間，。 解：取x2點為區(qū)間[x1,x3]的中點，,計算x1,x2,x33點處的函數(shù)值f1=19，f2=-96.9375，f3=124?？梢姾瘮?shù)值滿足“高－低－高”形態(tài)。 以x1,x2,x3為插值點構(gòu)造二次曲線，求第一次近似的二次曲線p(x)的極小值點，由公式得：，比較函數(shù)值可知這種情況應(yīng)消除左邊區(qū)段。然后用作為x1,x2,x3新3點,重新構(gòu)造二次曲線p(x)，如此反復(fù)計算，直到為止。整個迭代過程的計算結(jié)果列于表。插值法和試探法的比較試探法中試驗點位置是由某種給定的規(guī)律確定的，它不考慮函數(shù)值的分布。例如，黃金分割法是按等比例0.618縮短率確定的。插值法中，試驗點位置是按函數(shù)值近似分布的極小點確定的。試探法僅僅利用了試驗點函數(shù)值大小的比較，而插值法還要利用函數(shù)值本身或者其導(dǎo)數(shù)信息。試探法僅對試驗點函數(shù)值的大小進行比較，而函數(shù)值本身的特性沒有得到充分利用，這樣即使對一些簡單的函數(shù)，例如二次函數(shù)，也不得不象一般函數(shù)那樣進行同樣多的函數(shù)值計算。插值法是利用函數(shù)在已知試驗點的值（或?qū)?shù)值）來確定新試驗點的位置。當函數(shù)具有比較好的解析性質(zhì)時（例如連續(xù)可微性），插值法比試探法效果更好。機械優(yōu)化設(shè)計第四章無約束優(yōu)化方法×4.1概述4.2最速下降法4.3牛頓型方法4.4共軛方向及共軛方向法4.5共軛梯度法4.6變尺度法4.7坐標輪換法4.8鮑威爾方法4.9單型替換法第四章無約束優(yōu)化方法第一節(jié)概述，數(shù)值解法：是利用已有的信息，通過計算點一步一步地直接移動，逐步逼近最后達到最優(yōu)點。1）選擇迭代方向即探索方向；2）在確定的方向上選擇適當步長邁步進行探索第四章無約束優(yōu)化方法第一節(jié)概述，無約束優(yōu)化方法可以分成兩類：一類是利用目標函數(shù)的一階或二階導(dǎo)數(shù)的無約束優(yōu)化方法（如最速下降法、共軛梯度法、牛頓法及變尺度法）；另一類只利用目標函數(shù)的無約束優(yōu)化方法（如坐標輪換法、單形替換法及鮑威爾法等）。第四章無約束優(yōu)化方法第二節(jié)最速下降法，定義：最速下降法就是采用使目標函數(shù)值下降得最快的負梯度方向作為探索方向，來求目標函數(shù)的極小值的方法，又稱為梯度法。最速下降法的迭代公式第四章無約束優(yōu)化方法第二節(jié)最速下降法，最速下降法的迭代步驟：第四章無約束優(yōu)化方法第二節(jié)最速下降法，第四章無約束優(yōu)化方法第二節(jié)最速下降法，最速下降法的特點：

1）對初始搜索點無嚴格要求；

2）收斂速度不快；

3）相鄰兩次迭代搜索方向互相垂直，在遠離極值點處收斂快，在靠近極值點處收斂慢；

4）收斂速度與目標函數(shù)值的性質(zhì)有關(guān)，對等值線是同心圓的目標函數(shù)來說，經(jīng)過一次迭代就可以達到極值點。第四章無約束優(yōu)化方法第三節(jié)牛頓型法，牛頓型法的基本思想：利用二次曲線來逐點近似原目標函數(shù)，以二次曲線的極小點來近似原目標函數(shù)的極小點并逐漸逼近該點。

基本牛頓法的迭代公式：第四章無約束優(yōu)化方法第三節(jié)牛頓型法，基本牛頓法的迭代公式：第四章無約束優(yōu)化方法第三節(jié)牛頓型法，基本牛頓法的迭代公式：阻尼牛頓法的迭代公式：第四章無約束優(yōu)化方法

第三節(jié)牛頓型法，阻尼牛頓法的迭代步驟：第四章無約束優(yōu)化方法第三節(jié)牛頓型法，阻尼牛頓法的迭代公式：第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，

在下一次迭代時，選擇搜索方d1指向極小點x*，共軛方向以二元函數(shù)為例：我們?nèi)我膺x擇一個初始點x0點，沿著某個下降方向d0作一維搜索第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，共軛方向正交第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，共軛方向的性質(zhì)第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，共軛方向法的步驟第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，共軛方向的形成格拉姆-斯密特向量系共軛化的方法

n個線性無關(guān)的向量系vi（i=0,1，…，n-1）一組獨立向量dr（r=0,1，…，n-1）

第四章無約束優(yōu)化方法第四節(jié)共軛方向及共軛方向法，第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛梯度法：先沿最速下降方向(負梯度方向)探索第一步，然后沿與該負梯度方向相共軛的方向進行探索。第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛方向與梯度之間的關(guān)系：

它表示沿著方向dk做一維搜索，它的終點xk+1與始點xk的梯度之差與dk的共軛方向dj正交。第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛梯度法遞推公式：第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛梯度法步驟：第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛梯度法步驟：第四章無約束優(yōu)化方法第五節(jié)共軛梯度法，共軛梯度法

設(shè)法構(gòu)造出一個對稱正定矩陣來代替，并在迭代過程中使逐漸逼近

,那么就簡化了牛頓法的計算，并且保持了牛頓法收斂快的優(yōu)點。第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），變尺度法的基本思想：牛頓方向：變尺度法的迭代公式：尺度矩陣第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），尺度矩陣G正定牛頓迭代公式：目的：目標函數(shù)的偏心率減小到零。第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），變尺度矩陣的建立：變尺度法的迭代公式：搜索方向：尺度矩陣應(yīng)具備的條件：1）為正定對稱矩陣；2）具有簡單的迭代形式:3）滿足擬牛頓條件：令則第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），變尺度法的一般步驟：第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），變尺度法的流程圖：第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），DFP算法：DFP算法的校正公式第四章無約束優(yōu)化方法第六節(jié)變尺度法（擬牛頓法），DFP算法：第四章無約束優(yōu)化方法第七節(jié)坐標輪換法，基本思想：每次僅對多元函數(shù)的一個變量沿其坐標軸進行一維探索，其余各變量均固定不動，并依次輪換進行一維探索的坐標軸，完成第一輪探索后再重新進行第二輪探索，直到找到目標函數(shù)在全域上的最小點為止。目的：將一個多維的無約束最優(yōu)化問題，轉(zhuǎn)化為一系列的一維問題來求解。第四章無約束優(yōu)化方法第七節(jié)坐標輪換法，二維問題第四章無約束優(yōu)化方法第七節(jié)坐標輪換法，第k輪迭