第三章

無約束問題的最優(yōu)化方法

§3.1引言

§3.2一維搜索方法

§3.3坐標輪換法、共軛方向法和poweel法

§3.4梯度法和共軛梯度法

§3.5牛頓法和變尺度法

§3.6單形替換法

§3.7無約束優(yōu)化設計方法小結§3.1引言一.

目的：求一組n維設計變量x=[x1,x2,…,xn]t,使目標函數(shù)達到

min.f(x)x∈rn即求目標函數(shù)的最優(yōu)解：最優(yōu)點x*和最優(yōu)值f(x*)。二.意義：

為約束優(yōu)化方法的研究提供了策略思想、概念基礎和基本方法；為約束優(yōu)化問題的間接解法提供了有效而方便的方法；對于某些工程問題，進行分析后，便于提供解決的有效方法；約束優(yōu)化問題的求解往往可以通過一系列無約束優(yōu)化方法實現(xiàn)；無約束優(yōu)化問題的解法是優(yōu)化設計方法的基本組成部分?！?.1引言三.內容：一維搜索：求最優(yōu)步長因子α(k)多維（變量）優(yōu)化：確定搜索方向s(k)黃金分割切線法平分法插值法格點法坐標輪換法最速下降法共軛方向法鮑威爾法梯度法共軛梯度法牛頓法單形替換法變尺度法§3.1引言四.無約束優(yōu)化方法計算步驟：1、選擇一個初始點x(0)，這一點越靠近極小點x*越好。2、若已經(jīng)取得某設計點x(k)，并且該點不是近似極小點，則在x(k)點根據(jù)函數(shù)f(x)的性質，選擇一個方向s(k)，并且沿此方向搜索函數(shù)值是下降的，稱下降方向。3、當搜索方向s(k)確定后，由x(k)點出發(fā)，沿s(k)方向進行搜索，定出步長因子(k)，得到新的設計點：

x(k+1)=x(k)+(k)s(k)，并滿足f(x(k+1))<f(x(k))4、若x(k+1)滿足迭代計算終止條件，x(k+1)點作為x*；否則從該點出發(fā)，返回第二步繼續(xù)搜索迭代。開始給定x和s的初始值計算使f（x+s）極小x＝x+s

滿足收斂條件？結束形成新的s無約束優(yōu)化算法粗框圖

無約束優(yōu)化數(shù)值計算方法采用的是搜索方法，其基本思想是從給定的初始點出發(fā)，沿某一個搜索方向進行不斷的搜索，確定最佳步長使函數(shù)值沿搜索方向下降最大，其迭代公式為

x(k+1)=x(k)+(k)s(k)

各種無約束優(yōu)化方法的區(qū)別在于確定其搜索方向的s(k)的方法不同。所以，搜索方向的構成問題是無約束優(yōu)化問題的關鍵。五.無約束優(yōu)化方法的關鍵問題：§3.1引言六.無約束優(yōu)化方法的分類：§3.1引言

無約束優(yōu)化方法的分類依據(jù)就是根據(jù)(k)和s(k)的確定方法而定的。若根據(jù)構成搜索方向所使用的信息性質的不同，可以分為兩類。

1、間接法又稱解析法，是利用目標函數(shù)導數(shù)的無約束優(yōu)化方法，如最速下降法、共軛梯度法、牛頓法及變尺度法等。

2、直接法

只利用目標函數(shù)值的無約束優(yōu)化方法，如坐標輪換法、鮑威爾法及單形替換法等?！?.2一維搜索方法一.一維搜索：定義:

在第k次迭代時，從已知點x(k)出發(fā)，沿給定方向求最優(yōu)步長因子α(k)，使f(x(k)+α

s(k))達到最小值的過程，稱為一維搜索。方法：1.解析法：

f(x(k+1)

)=min.f(x(k)+α

s(k))=f(x(k)+α(k)s(k))

步驟:①f(x(k)+αs(k))沿s(k)

方向x(k)

臺勞展開；②取二次近似：對α求導，令其為零。

2.數(shù)值迭代法：直接法——應用序列消去原理：分數(shù)法、黃金分割法近似法——利用多項式函數(shù)逼近（曲線擬合）原理：

二次插值法、三次插值法④求得最優(yōu)步長因子：§3.2一維搜索方法二.迭代法求解一維搜索問題的基本思想：

先選定一個初始點x0，從x0出發(fā)沿某一選定方向p0求f(x)的極小點，設其為x1；然后再從x1出發(fā)沿某一選定方向p1求f(x)的極小點，設其為x2；如此下去，從xk出發(fā)沿某一選定方向pk求的極小點xk+1，…

，直到求得的xk滿足要求為止。求得的值是逐漸下降的：

稱pk為第k次的搜索方向，因此，在過xk的pk方向上，任意一點可以表示為x=xk+t*pk，目標函數(shù)值為f(xk+t*pk)，目標函數(shù)實際上成了一元函數(shù)。所以沿pk方向求f(x)的極小點，就是求一元函數(shù)f(xk+t*pk)的極小問題，表示為：總結：將優(yōu)化問題轉化為一系列的一維搜索問題§3.2一維搜索方法沿方向s的一維搜索§3.2一維搜索方法單峰區(qū)間解析概念：

在區(qū)間[α1，α3]內，函數(shù)只有一個峰值，則此區(qū)間為單峰區(qū)間。單峰區(qū)間內，一定存在一點α*，當任意一點α2＞α*時，f(α2)＞f(α*)，說明：單峰區(qū)間內，函數(shù)可以有不可微點，也可以是不連續(xù)函數(shù)；三.搜索區(qū)間的確定：f(x)0α1α3α0αf(x)α3α1f(α)αα3α2α*α10當α2＜α*時，仍有f(α2)＞f(α*)，則α*是最優(yōu)點，也即為最優(yōu)步長因子α(k)。α2確定的搜索區(qū)間必定是一個含有最優(yōu)點α*的單峰區(qū)間?！?.2一維搜索方法2。單峰區(qū)間幾何概念：

指函數(shù)在區(qū)間內只有一個極小點。在極小點左邊的函數(shù)值應是嚴格下降，在極小點右邊的函數(shù)值應是嚴格上升，即單峰區(qū)間內的函數(shù)值具有的特征是：“高—低—高”。進退法確定的單峰區(qū)間三.搜索區(qū)間的確定：§3.2一維搜索方法3.定步長搜索法:4.加速步長搜索法：f2=f(α1+t0)α1f1解：計算試點例3-1

用進退法求單變量函數(shù)的搜索區(qū)間。初始點，步長比較兩試點函數(shù)值，由于作前進搜索比較兩試點函數(shù)值，由于作前進搜索比較兩試點函數(shù)值，由于作前進搜索此時，三個試點函數(shù)值已經(jīng)出現(xiàn)“高－低－高”特征，得搜索區(qū)間為§3.2一維搜索方法四.黃金分割法(0.618)：1.序列消去原理：f(α)αα3(1)α12α*α1(1)0α3(2)α11α21α22α1(2)α1(3)α3(3)§3.2一維搜索方法黃金分割法消去示例：§3.2一維搜索方法2.黃金分割與0.618：bd

古希臘建筑師認為：邊長為b，d的矩形建筑物，若邊長能符合以下條件，則最美觀：歐幾里德幾何稱這種邊長分割為黃金分割。

序列消去法中，為提高效率，減少計算量和存儲量，希望黃金分割法的算法框圖解：在搜索區(qū)間內取兩試點并且計算它們函數(shù)值

比較兩試點函數(shù)值，縮短搜索區(qū)間，由于，消去右區(qū)間，令：例3-2用黃金分割法求單變量函數(shù)的極小點。初始搜索區(qū)間，迭代精度判斷迭代終止條件：

不滿足迭代終止條件。再取兩試點并且比較它們的函數(shù)值，繼續(xù)縮短搜索區(qū)間。搜索區(qū)間經(jīng)過6次縮短（中間迭代過程略）后，區(qū)間長度為：可以終止迭代，得到近似極小點和最優(yōu)解

§3.2一維搜索方法五.二次插值法（拋物線法）：1.基本原理：步驟：§3.2一維搜索方法2.步驟(續(xù))：3.結果分析：問題：若不滿足精度，如何縮小區(qū)間，再擬合（分四種情況分析）？

②令：單谷搜索區(qū)間縮短情況x1x2x3xp*f2fp*x1x1x1x2x2x2xp*xp*xp*x3x3x3f2f2f2fp*fp*fp*bacd入口xp*>x2?f2*>fp*?f2<fp*?x3x2f3

f2x2xp*f2

fp*x1x2f1

f2x2xp*f2

fp*出口yyynnnabcdx3xp*f3

fp*x1xp*f1

fp*二次插值法區(qū)間縮短流程圖§3.2一維搜索方法

與黃金分割法相比，二次插值法充分利用函數(shù)值的信息；收斂快；調用函數(shù)次數(shù)少。4.方法評價:5.迭代終止條件:當滿足如下兩個條件，可終止迭代：

如果和兩點的距離很小，即：

如果和充分接近，即：二次插值法的算法框圖解：1）確定初始插值結點與函數(shù)值

2）計算插值函數(shù)極小點

例3-3用二次插值法求一維函數(shù)的最優(yōu)解。初始單谷搜索區(qū)間，迭代精度

由于判別式成立，表明落在單谷搜索區(qū)間之內

3）縮短單谷搜索區(qū)間

由于和，則舍棄左邊的區(qū)間，構成縮短后的新搜索區(qū)間。即：4）檢驗迭代終止條件

滿足迭代終止條件，輸出最優(yōu)解

六.切線法：

一維搜索函數(shù)，假定已給出較好的近似點，連續(xù)可微的函數(shù)在極小點附近與一個二次函數(shù)很接近，所以可以在附近用一個二次函數(shù)來逼近函數(shù)：

以二次函數(shù)的極小點作為極小點的一個新近似點，根據(jù)極值必要條件：§3.2一維搜索方法解：

1)求函數(shù)的一階、二階導函數(shù)：例3-4

給定函數(shù)，初始值為，控制誤差，試用切線法求其極小點。

2)求

3)求4.000594.000664.039604.334745.1666784.0472086.86992109.44586184.3332240.005513.3829932.30199153.3518-524.000664.039604.334745.16667343210k值

4)迭代值如下：切線法流程圖ny開始結束k=k+1給定

k=0１.收斂速度快；２.需要計算函數(shù)的一階和二階導數(shù)，增加迭代工作量；３.要求初始點選得比較好，離極小點不遠，否則有可能使極小化序列發(fā)散或收斂到非極小點。切線法優(yōu)缺點:§3.2一維搜索方法§3.2一維搜索方法取具有極小點的單峰函數(shù)的探索區(qū)間[a,b]的坐標中點作為計算點，計算目標函數(shù)在該點處的導數(shù)為，并利用函數(shù)在極小點處的導數(shù)為零而在其左側為負、右側為正的原理，來判斷極小點所在的那一半探索區(qū)間，以消掉另一半?yún)^(qū)間。這樣逐次迭代下去，總能將探索區(qū)間收斂到一個局部極小點附近，求得極小點的近似解。收斂速度雖然較慢，但縮短率也達到0.5，特別是每次迭代計算量較少，可靠性較好，所以仍然是一個受歡迎的方法。七.平分法：§3.2一維搜索方法平分法的迭代計算步驟:給定計算，若，則停止迭代并取否則進行下一步。計算，若或，則停止迭代并取若則取為縮短后的搜索區(qū)間轉第二步若則取為縮短后的搜索區(qū)間轉第二步當求解困難時:

可直接計算并比較兩者大小，用序列消去法原理消去掉近一半的區(qū)域，再重新迭代，直到將探索區(qū)間縮短至精度要求為止。例3-5

試用平分法求的極小點和極小值，設解：

1)取

2)計算

3)縮短搜索區(qū)間為取

4)計算

5)所以函數(shù)的極小點為,極小值為:§3.2一維搜索方法設一維函數(shù)為f(x)，搜索區(qū)間為[a,b]，一維收斂精度為。在區(qū)間[a,b]的內部取n個等分點：x1,x2,…,xn。區(qū)間被分為n+1等分，各分點坐標為對應各點的函數(shù)值為y1,y2,…,yn+2。比較其大小，取最小者ym=min{yk,k=1,2,…,n＋2}，則在區(qū)間[xm-1,xm+1]內必包含極小點，取[xm-1,xm+1]為縮短后新區(qū)間，若新區(qū)間滿足收斂條件:xm+1-xm+1，則最優(yōu)解為x*

=xm，y*

=ym

若不能滿足精度要求，把當前區(qū)間作為初始搜索區(qū)間，重復上述步驟直至滿足精度為止。八.格點法：

新區(qū)間y1ym-1ymym+1yn＋2x1axm-1xmxm+1xn＋2b格點法區(qū)間搜索原理格點法流程圖yn開始p=y,m=ky<p給定

m=0,k=1，p=足夠大的數(shù)k=nk=k+1|b-a|<εnyyn相同點：都是利用區(qū)間消去法原理將初始搜索區(qū)間不斷縮短，從而求得極小點的數(shù)值近似解。不同點：試驗點位置的確定方法不同。直接法中試驗點的位置是由某種給定的規(guī)律確定的，并未考慮函數(shù)值的分布。黃金分割法是按照等比例0.618縮短率確定的，僅僅利用了試驗點函數(shù)值進行大小的比較；間接法中，試驗點的位置是按函數(shù)值近似分布的極小點確定的，利用了函數(shù)值本身或其導數(shù)信息。當函數(shù)具有較好的解析性質時，間接方法比直接方法效果更好?！?.2一維搜索方法九.間接法與直接法的異同點：§3.2一維搜索方法1.掌握進退法確定單谷搜索區(qū)間；2.掌握黃金分割法的原理和程序設計；3.掌握二次插值法的原理和程序設計；4.掌握切線法的原理和流程；5.了解平分法和格點法。十.學習要求：試用二次插值法求的近似極小點和極小值，已知十一.習題：一.坐標輪換法：1.基本思想：2.搜索方向與步長：

每次以一個變量坐標軸作為搜索方向，將n維的優(yōu)化問題轉化為一維搜索問題。例，第k輪迭代的第i次搜索，是固定除xi外的n-1個變量，沿xi變量坐標軸作一維搜索，求得極值點xi(k)…n次搜索后獲得極值點序列x1(k),x2(k,…,xn(k)，若未收斂，則開始第k+1次迭代，直至收斂到最優(yōu)點x*?！?.3

坐標輪換法、共軛方向法和poweel法一.坐標輪換法：3.方法評價：

方法簡單，容易實現(xiàn)。當維數(shù)增加時，效率明顯下降。收斂慢，以振蕩方式逼近最優(yōu)點。

受目標函數(shù)的性態(tài)影響很大。如圖a)所示，二次就收斂到極值點；如圖b)所示，多次迭代后逼近極值點；如圖c)所示，目標函數(shù)等值線出現(xiàn)山脊（或稱陡谷），在脊線的尖點a處沒有一個坐標方向可以使函數(shù)值下降，只有在銳角所包含的范圍搜索才可以達到函數(shù)值下降的目的，故坐標輪換法對此類函數(shù)會失效?！?.3

坐標輪換法、共軛方向法和poweel法i=n坐標輪換法的流程圖

開始給定：x0,k=1i=1,x0k=x0xik=x0k-1沿ei方向一維搜索求ixik=xi-1k+

ikeix=xkf=f(x)||xnk-x0k||x*=x

f*=f(x*)結束i=i+1x0k+1=xnkk=k+1nyny此問題可用一維優(yōu)化方法求解，這里用微分學求解：解：1.作第一輪迭代計算得：1)沿e1方向進行一維搜索例4-1

用坐標輪換法求目標函數(shù)的無約束最優(yōu)解，給定初始點，精度要求其中為第一輪的起始點。?。喊醋顑?yōu)步長原則確定2)以為新起點，沿e2方向一維搜索：按最優(yōu)步長原則確定得：3)按迭代終止條件檢驗

2.作第二輪迭代計算，如此共進行9輪得到結果二.共軛方向法：1.共軛方向的由來：2.共軛方向的定義：

共軛方向概念是在研究具有正定矩陣g的二次函數(shù)

的極小化問題時形成的。其基本思想是在不用導數(shù)的前提下，在迭代中逐次構造g的共軛方向?！?.3

坐標輪換法、共軛方向法和poweel法3.共軛方向法的二次收斂性：

正定的二元二次函數(shù)的等值線為一組橢圓，任選初始點x0，沿某個下降方向s0作一維搜索，得x1

此時，x1點的梯度必然與方向s0垂直，即有：x0x*x11s1-f(x1)s10s0

s0與某一等值線相切于x1點。下一次的迭代，若選擇負梯度方向為搜索方向，將產(chǎn)生鋸齒現(xiàn)象。為避免鋸齒的產(chǎn)生，我們取迭代方向s0直指極小點x*，如圖所示。若選定這樣的方向，則對于二元二次函數(shù)只需進行s0

和s1兩次搜索就可以求得極小點x*，即§3.3

坐標輪換法、共軛方向法和poweel法3.共軛方向法的二次收斂性（續(xù)）：

由于，當時，由是的極小點，應滿足極值必要條件，故即：

等式兩端同乘以,得，故兩個向量，是g的共軛向量。

因此，若要使第二個迭代點成為正定二元二次函數(shù)的極小點，只要使兩次一維搜索的方向，關于函數(shù)的二階導數(shù)矩陣g共軛就可以了。

對于正定二次n維函數(shù)，從任意的初始點出發(fā)，沿著這n個共軛方向進行一維搜索，就可以得到目標函數(shù)的極小點。因此，對于二次函數(shù)來說，經(jīng)過n步搜索就可以達到函數(shù)的極小點。對于非二次n維函數(shù)，可以用二階泰勒級數(shù)將函數(shù)在極小點附近展開，省略去高于二次的項后可以得到函數(shù)的二次近似，同樣按照二次函數(shù)構成共軛方向。§3.3

坐標輪換法、共軛方向法和poweel法4.二維函數(shù)的共軛方向：

二維函數(shù)，任意給定某個方向，按這個方向上的兩條平行線進行一維搜索求得的極小點為和，它們應該是方向為的兩條平行線與目標函數(shù)等值線的切點。

連接兩個切點和構成向量：

可以證明，如果二維函數(shù)的海塞矩陣h是正定的，則s1向量與向量s2滿足條件：

具有這種性質的方向為關于正定矩陣h的共軛方向?！?.3

坐標輪換法、共軛方向法和poweel法

所以有：4.二維函數(shù)的共軛方向（續(xù)）：證明：

設二維函數(shù)在極值點x*附近的二次泰勒展開式為：

由此得函數(shù)的一階導數(shù)：

由于s1為等值線的切線，故方向s1應垂直于x(1)

,x(2)

的梯度方向：§3.3

坐標輪換法、共軛方向法和poweel法

所以有：4.二維函數(shù)的共軛方向（續(xù)2）：

兩式相減得：

由，上式可簡化為：§3.3

坐標輪換法、共軛方向法和poweel法5.二維函數(shù)共軛方向法的迭代過程：

1.令循環(huán)次數(shù)k＝1，取初始點，初始搜索方向為坐標方向

4.取下次循環(huán)的初始點，替換掉原來的第一方向，構成新的搜索方向：

5.k=k+1，轉步驟2。

2.從出發(fā)，依次沿和進行一維搜索，分別得到相應的極小點和。

3.構建新方向，沿方向進行搜索，得到第k次的極小點§3.3

坐標輪換法、共軛方向法和poweel法6.多維二次函數(shù)共軛方向的構建：

如果n維函數(shù)的海賽矩陣是正定的，一組非零向量滿足：

則向量系：是關于海賽矩陣h共軛，即他們是n個互為共軛的方向。

§3.3

坐標輪換法、共軛方向法和poweel法8.方法評價：

計算步驟復雜;

是二次收斂方法，收斂快。對非正定函數(shù)，也很有效;

是比較穩(wěn)定的方法。7.說明：

若是正定二次函數(shù)，n輪迭代后收斂于最優(yōu)點x*。若是非正定二次函數(shù)，則迭代次數(shù)增加。

若是n維問題，步驟相同。搜索方向：第一輪迭代，沿初始方向組si(1)(i=1,2,…,n)的n個方向和共軛方向s(1)，搜索n+1次得極值點xn+1(1)

；第二輪迭代，沿方向組si(2)(i=1,2,…,n；i≠m)的n-1個方向和共軛方向s(1)，構筑共軛方向s(2)搜索n+1次得極值點xn+1(2)

。其中，為保證搜索方向的線性無關，去除了sm(2)方向。

在第k輪迭代中，為避免產(chǎn)生線性相關或近似線性相關，需要去除前一輪中的某個方向sm(k)?！コ脑瓌t請自學?！?.3

坐標輪換法、共軛方向法和poweel法共軛方向法的程序框圖9.共軛方向法的缺陷：

共軛方向法的迭代過程可能會產(chǎn)生不理想的情況，在以后某環(huán)的迭代中可能出現(xiàn)基本方向組為線性相關向量系。以后的搜索將在維數(shù)下降后的設計空間中進行，無法收斂到n維設計空間中目標函數(shù)的極小點。

以三維問題為例，設從初始點出發(fā)，沿著坐標軸方向，進行第一環(huán)搜索，在各個方向獲得極小點為：

由該環(huán)搜索的初始點與終點產(chǎn)生的新生方向：§3.3

坐標輪換法、共軛方向法和poweel法9.共軛方向法的缺陷（續(xù)）：

如果其中第三維優(yōu)化步長等于或非常接近0，即表示沿著則坐標軸方向的搜索沒有前進或前進很少，則共軛方向：

表明向量與向量是線性相關的。

第2環(huán)搜索的基本方向組中，是與線性相關或接近線性相關，即向量在和組成的平面內。以后的搜索將在維數(shù)下降（不包含方向）的平面中進行，無法收斂到空間中目標函數(shù)的極小點。§3.3

坐標輪換法、共軛方向法和poweel法三.poweel法：1.基本步驟：1.給定初始點，選取由n個線性無關的向量組成的初始方向組，置。2.從出發(fā)，順次沿作一維搜索得。接著以為起點，沿方向：移動一個的距離，得到：

分別稱為一輪迭代的始點、終點和反射點。它們所對應的函數(shù)值分別為：

同時計算各中間點處的函數(shù)值，并記為：§3.3

坐標輪換法、共軛方向法和poweel法§3.3

坐標輪換法、共軛方向法和poweel法1.基本步驟（續(xù)）：

計算n個函數(shù)值之差：3.為了構造第k＋1環(huán)基本方向組，采用如下判別式：

按以下兩種情況處理：

其中最大者記作：鮑威爾判別式

a.上式中至少一個不等式成立，則第k+1環(huán)的基本方向仍用老方向組.,k+1的環(huán)初始點取:

1.基本步驟（續(xù)2）：b.兩式均不成立，則淘汰函數(shù)值下降最大的方向，并用第k環(huán)的新生方向補入k+1環(huán)基本方向組的最后，即k+1環(huán)的方向組為：

k+1環(huán)的初始點取，是第k環(huán)沿方向搜索的極小點。§3.3

坐標輪換法、共軛方向法和poweel法鮑威爾法的流程圖一.梯度法（最速下降法）：1.基本思想：2.負梯度方向為最速下降方向的證明：

目標函數(shù)負梯度向量方向代表最速下降方向，因此選擇負梯度向量方向為搜索方向，期望很快找到最優(yōu)點。s由方向導數(shù)概念可得：設：取最小值－1時，s為梯度的負方向?！?.4梯度法和共軛梯度法4.迭代格式：3.搜索方向：a.任意給定一個初始步長，使其滿足：根據(jù)一元函數(shù)的極值必要條件和多元復合函數(shù)的求導公式，得：或負梯度方向或單位負梯度向量5.最佳步長的選?。篵.沿負梯度方向作一維搜索，求最佳步長，對目標函數(shù)求極小，以得到最佳步長：即：§3.4梯度法和共軛梯度法

最速下降法向極小點的逼近路徑是鋸齒形路線，越接近極小點，鋸齒越細，前進速度越慢。

這是因為，梯度是函數(shù)的局部性質，從局部上看，在該點附近函數(shù)的下降最快，但從總體上看則走了許多彎路，因此函數(shù)值的下降并不快。5.最佳步長的選?。ɡm(xù)）：

此式表明，相鄰的兩個迭代點的梯度是彼此正交的。也即在梯度的迭代過程中，相鄰的搜索方向相互垂直。6.搜索路徑：§3.4梯度法和共軛梯度法（1）任選初始迭代點x(0)，選收斂精度。（2）確定x(k)點的梯度(開始k=0)。（3）判斷是否滿足終止條件，若滿足輸出最優(yōu)解，結束計算。否則轉下步。（4）從x(k)點出發(fā)，沿

方向作一維搜索求最優(yōu)步長(k)。得下一迭代點。令k=k+1返回步驟（2）。7.迭代終止條件：

采用梯度準則：8.迭代步驟：§3.4梯度法和共軛梯度法梯度法流程圖ny開始給定：x(0)，

k=0x*=x(k)f*=f(x(k))結束x(k)=

x(0)k=k+1§3.4梯度法和共軛梯度法9.方法評價：

迭代過程簡單，對初始點的選擇，要求不高。梯度方向目標函數(shù)值下降迅速只是個局部性質，從整體來看，不一定是收斂最快的方向。以二維二次函數(shù)為例，相鄰兩次的搜索方向是正交的，所以搜索路徑是曲折的鋸齒形的；對于高維的非線性函數(shù)，接近極值點處，容易陷入穩(wěn)定的鋸齒形搜索路徑。例4-1

二維無約束目標函數(shù)試用梯度法求其極小值，初始點，精度

解：

1）計算目標函數(shù)在初始點的梯度、梯度的模和單位負梯度方向2）計算最佳搜索步長3）計算第一次迭代更新值和目標函數(shù)值4）當?shù)?次時，滿足終止條件，得到最有值§3.4梯度法和共軛梯度法二.共軛梯度法（旋轉梯度法）：1.基本思想：2.共軛方向：

對梯度法作一個修正，將搜索方向由負梯度方向旋轉一個角度，使相鄰的兩次搜索方向由正交變?yōu)楣曹?，成為二次收斂?.共軛系數(shù)：推導過程請自學。β(k)s(k)步驟：

5.方法評價：

迭代程序簡單，容易實現(xiàn)，存儲量較小。開始采用梯度方向，目標函數(shù)值下降快，后又為旋轉梯度方向，具有二次收斂速度，收斂快?！?.4梯度法和共軛梯度法開始k=0，計算：-f(x0)

||f(xk+1)

||？結束求(k)

，x(k+1)=

x(k)+(k)s(k)計算：f(xk+1)

x*=xk+1f(x*)=f(xk+1)yn給定：x(0)，

kn？x0=xk+1ynsk+1=-f(xk+1)

+

kskk=k+1共軛梯度法流程圖例4-2

二維無約束目標函數(shù)試用共軛梯度法求其極小值，初始點，精度

解：

1）計算目標函數(shù)在初始點的梯度、梯度的模和單位負梯度方向2）計算新迭代點的梯度和搜索方向的修正量，進行第2次搜索

可見，共軛梯度法具有兩次收斂性，對于二維函數(shù)只要經(jīng)過兩次迭代就可以達到極值點。

§3.5

牛頓法和變尺度法一.牛頓法（二階梯度法）：

1.基本思想：

將f(x)在x(k)

點作臺勞展開，取二次函數(shù)式Φ(x)作為近似函數(shù),以Φ(x)的極小值點作為f(x)的近似極小值點。說明：

f(x)若是正定二次函數(shù)，一般迭代一次即可；若是嚴重非線性函數(shù)，則可能不收斂，或收斂到鞍點。2.修正牛頓法（阻尼牛頓法）：一.牛頓法（二階梯度法）：

可通過如下極小化過程求得：

避免了迭代后函數(shù)上升的現(xiàn)象，保持了牛頓法二次收斂的特性，對初始點的選取并沒有苛刻的要求。阻尼牛頓法的計算步驟：1）給定初始點，收斂精度，置§3.5

牛頓法和變尺度法§3.5

牛頓法和變尺度法3.方法評價：

使用牛頓法時，若目標函數(shù)是嚴重非線性函數(shù)，則是否收斂將與初始點有很大關系；而使用修正牛頓法，能保證每次迭代目標函數(shù)值下降，從而放寬了對初始點的要求。若初始點選得合適，牛頓法的收斂速度相當快。牛頓法求逆矩陣的工作量大，計算量與存儲量均隨n2上升。3）求，其中為沿進行一維搜索的最佳步長4）檢查收斂精度。若，則，否則，令，返回2）繼續(xù)進行搜索。2）計算：阻尼牛頓法流程圖§3.5

牛頓法和變尺度法

變尺度法也稱擬牛頓法，它是基于牛頓法的思想而又作了重大改進的一類方法。

梯度法只需計算函數(shù)的一階偏導數(shù)，計算量小，當?shù)c遠離最優(yōu)點時，函數(shù)值下降很快，但當?shù)c接近最優(yōu)點時收斂速度極慢。dfp變尺度法是由davidon于1959年提出的一種變尺度法；bfgs變尺度法是由broydon等提出的改進算法，提高了算法的穩(wěn)定性。

牛頓法不僅需要計算一階偏導數(shù)，而且要計算二階偏導數(shù)及其逆陣，計算量很大，但牛頓法具有二次收斂性，當?shù)c接近最優(yōu)點時，收斂速度很快。

若迭代過程先用梯度法，后用牛頓法并避開牛頓法的海賽矩陣的逆矩陣的煩瑣計算，則可以得到一種較好的優(yōu)化方法，這就是“變尺度法”產(chǎn)生的構想。一.變尺度法:§3.5

牛頓法和變尺度法二.dfp變尺度法:1.變尺度的定義：每確定一次搜索方向，調整一次模（尺度）的大小，稱為變尺度。2.基本思想：

發(fā)揚梯度法和牛頓法各自的優(yōu)點，避免兩者各自的缺點，將兩者結合起來，形成變尺度法?！?.5

牛頓法和變尺度法3.變尺度矩陣的構造：原則：

使目標函數(shù)值有下降性，則變尺度矩陣應為實對稱矩陣（請證明）；使算法有二次收斂性，則s(k)(k=1,2,…)應關于h(k)

是共軛的；構造變尺度矩陣的遞推公式：4.修正矩陣:

§3.5

牛頓法和變尺度法步驟：1、選定初始點和收斂精度；2、計算初始點處的梯度，選取初始對稱正定矩陣a0，置k=0；3、計算搜索方向sk=

-akgk

；4、沿sk方向一維搜索，計算gk+1、sk=xk+1-xk

、yk=gk+1-gk

。5、判斷是否滿足終止準則，若滿足輸出最優(yōu)解，否則轉6。6、當?shù)鷑次還未找到極小點，重置ak為單位矩陣，并以當前點為初始點返回2，否則轉7。7、計算ak+1=ak+Δak，置k=k+1返回3。6.方法評價：

dfp變尺度法以逐次逼近的方法實現(xiàn)h-1

的計算，當目標函數(shù)的一階導數(shù)易求時，以一階代替二階導數(shù)的計算是有效的方法。算法的第一步是梯度法，最速下降；接近x*時，又采用二次收斂的共軛方向，總的收斂速度較快。

h(k)

近似代表x(k)點的二階導數(shù)，當其為零時，可判斷x(k)為鞍點。

h(k)

的計算較復雜，存儲量較大。算法穩(wěn)定性較差，由于計算機有舍入誤差，容易使h(k)

的正定性破壞，趨于奇異。

§3.5

牛頓法和變尺度法dfp變尺度法流程圖例4-3

二維無約束目標函數(shù)試用dfp算法求其極小值。解：

1）取初始點，為了按dfp法構造第一次搜索方向，需要計算初始點處的梯度：并取初始變尺度矩陣為單位矩陣a0=i，則第一次搜索方向為：沿方向進行一維搜索，得：其中，為一維搜索最佳步長，應滿足：2）再按dfp法構造點處的搜索方向，需要計算：得：代入dfp校正公式，得：

得：則第二次搜索方向為：其中，為一維搜索最佳步長，應滿足：沿d1進行一維搜索：3)為了判斷x2點是否為極值點，需計算x2點處的梯度及其海賽矩陣：

梯度為零向量，海賽矩陣為正定矩陣，可見x2點滿足極值充分必要條件，因此x2為極小點。函數(shù)的極值解為：dfp算法由于舍入誤差和一維搜索的不精確，有可能導致ak奇異，而使數(shù)值穩(wěn)定性方面不夠理想。所以1970年提出更穩(wěn)定的算法，稱為bfgs算法，其校正公式為：

因為變尺度法的有效性促使其不斷發(fā)展，所以出現(xiàn)過許多變尺度法的算法，1970年黃（huang）從共軛條件出發(fā)對變尺度法做了統(tǒng)一處理，寫出了統(tǒng)一公式：一.bfgs變尺度法:

可以看出，當取，就是dfp法的公式。當取，就是bfgs法的公式§3.5

牛頓法和變尺度法§3.6

單形替換法一.單形替換法基本思想:單純形：在一定的空間中的最簡單的圖形，如三角形，四面體等。

先算出n維空間n+1個點