優(yōu)化設(shè)計2-一維優(yōu)化及牛頓法

2023/2/213.3一維優(yōu)化問題優(yōu)化問題的數(shù)值解法：

X(k+1)=X(k)+λ

(k)S(k)

F[X(k)+λ

(k)S(k)]=minF[X(k)+λ(k)S(k)]

從一個初始點X(0)出發(fā)，按一定規(guī)則確定一個搜索方向S(0),然后在S(0)上搜索到目標(biāo)函數(shù)的極小值X(1)；接著又以X(1),作為下一個迭代的出發(fā)點，重復(fù)以上過程，直到把目標(biāo)函數(shù)達(dá)到最優(yōu)值f(X*)為止。在此過程中求λ(k)用到的方法叫一維搜索的優(yōu)化方法。

2023/2/222023/2/233.3.1單峰區(qū)間

1.單峰區(qū)間在單峰區(qū)間內(nèi)，在極小點左邊，函數(shù)值隨x的增加是嚴(yán)格減小的；在極小點右邊，函數(shù)是嚴(yán)格增大的。因此在單峰區(qū)間內(nèi)，函數(shù)值具有“高——低——高”的形態(tài)，可利用這一特征來確定初始單峰區(qū)間。2.確定單峰區(qū)間的進(jìn)退算法一維搜索的各種方法的基本思想是“區(qū)間消去法”，而區(qū)間消去法的基本思想是：逐步縮小搜索的區(qū)間，直至最小點存在的范圍小于給定的誤差范圍為止。2023/2/24基本思路：對單峰函數(shù)f(x)任選一個初始點x1及初始步長h，通過比較這兩點函數(shù)值的大小，來決定第三點的位置，比較這三點的函數(shù)值的大小，確定是否為“高——低——高”的形態(tài)，依此確定向前或后退搜索。2023/2/25確定單峰區(qū)間的進(jìn)退算法進(jìn)退法：通過比較函數(shù)值大小來確定單峰區(qū)間的方法。給定的初始點和步長

單峰區(qū)間：2023/2/26進(jìn)退步驟:(1)

選定初始點x1、初始步長h(h>0)。計算函數(shù)值f1=f(x1)和f2=f(x1+h)。比較f1和f2，可分三種情況：若f1>f2，則說明極小點x*必在x1的右方，應(yīng)作前進(jìn)運(yùn)算，轉(zhuǎn)(2);若f1<f2，則說明x*必在x1的左方，應(yīng)作后退運(yùn)算，轉(zhuǎn)（3）；若f1=f2，則說明極小點x*必在點x1和x1+h點之間，已形成“高—低—高”形態(tài)，則初始單峰區(qū)間為[x1,x1+h]。

(2)

當(dāng)f1>f2，將步長加倍，取下一個計算點為x=x1+2h，計算f(x1+2h),并令f1=f(x1+h),f2=f(x1+2h)。再比較f1和f2：若f1<f2，則相鄰三點的函數(shù)值形成“高—低—高”形態(tài)，得到初始單峰區(qū)間[x1,x1+2h];若f1>f2，則應(yīng)再作前進(jìn)計算，步長加倍，取下一計算點為x=x1+4h，并比較f1=f(x1+2h)和f2=f(x1+4h)的函數(shù)值。如此反復(fù)循環(huán)，直到相鄰三點的函數(shù)值形成“高—低—高”形態(tài)為止;若f1=f2，則初始單峰區(qū)間為[x1+h,x1+2h]

2023/2/27(3)

當(dāng)f1<f2，做后退運(yùn)算。步長改為負(fù)值，即從x1出發(fā)，向反方向搜索。取下一個計算點為x=x1-h，計算f(x1-h)，并令f2=f(x1),f1=f(x1-h)。此時：若f2<f1，則可確定初始單峰區(qū)間為[x1-h,x1+h]。若f2>f1，將步長加倍，繼續(xù)后退。再算出下一個點的函數(shù)值f(x1-2h)，…。如此反復(fù)循環(huán)，直到相鄰三點的函數(shù)值出現(xiàn)“高—低—高”形態(tài)為止；若f2=f1，則初始單峰區(qū)間為[x1-h,x1]。

可自己畫出進(jìn)退法的程序框圖。2023/2/28區(qū)間縮小的序列消去原理：是通過對區(qū)間分割點函數(shù)值的計算和比較，將初始區(qū)間逐次進(jìn)行縮小，當(dāng)區(qū)間縮小到給定的精度要求時，可求得一維極小點的近似解。若，則極小點必在區(qū)間若，則極小點在若，則歸入上面任何一種情況。區(qū)間消去法ab2023/2/29黃金分割法：黃金分割：將一線段分成兩段，使得整段長度與較長段的比值等于較長段與較短段的比值解得3.3.2黃金分割法2023/2/210兩個原則：

等比收縮原則：即區(qū)間每一次的縮短率λ不變；

對稱取點原則：即所插入兩點在區(qū)間中位置對稱。2023/2/2110.618法算法步驟為：確定f(x)的初始搜索區(qū)間[a,b]及終止限ε。計算x2=a+0.618(b-a),f2=f(x2);計算x1=a+0.382(b-a),f1=f(x1);若|x2-x1|<ε，則輸出x*=(x2+x1)/2，停機(jī)；否則，轉(zhuǎn)(5);若f1≤f2;，則置b=x2，x2=x1，f2=f1,然后轉(zhuǎn)（3）；否則置a=x1，x1=x2，f1=f2,

，然后計算x2=a+0.618(b-a),f2=f(x2)，轉(zhuǎn)（4）。0.618法的計算框圖見下圖：3.3.2黃金分割法2023/2/2122023/2/213黃金分割法的特點：（1）函數(shù)不必可微（2）第一次計算取兩點，以后每次只需計算一點（3）收縮速度均勻。搜索次數(shù)3.3.2黃金分割法2023/2/214例3-4：minf(x)=-sinx

cosx，已知初始區(qū)間[a,b]＝[40°,50°]，區(qū)間縮小的相對精度ε2=0.13。（1）區(qū)間縮短次數(shù)（迭代次數(shù)）

取N=5

（2）第1輪迭代。計算黃金分割點，并對其函數(shù)值比較，縮短區(qū)間因，可淘汰或，這里淘汰，新區(qū)間為2023/2/2152023/2/2162023/2/2172023/2/2182023/2/2193.3.3二次插值法基本思想：多項式是逼近函數(shù)的一種常用工具。利用插值多項式進(jìn)行一維搜索的基本思想是構(gòu)造一個較低的插值多項式p(x)來近似地代替原目標(biāo)函數(shù)f(x)，并以函數(shù)p(x)的極值點xp*（即p/(x)=0的根）作為目標(biāo)函數(shù)f(x)的近似極值點。再通過比較各插值點和xp*的函數(shù)值及其所在位置，設(shè)法縮減搜索區(qū)間。從而最終逼近函數(shù)f(x)的極值點。

如果p(x)是二次多項式，則稱為二次插值法，若p(x)是三次多項式，則稱為三次插值法。一般來說，三次插值的收斂性要好一些，但要計算函數(shù)導(dǎo)數(shù)；而二次插值計算較簡單且具有一定的精度，故應(yīng)用廣泛。二次插值又稱為拋物線法。

2023/2/220設(shè)原目標(biāo)函數(shù)f(x)的初始單峰搜索區(qū)間[x1,x3]已確定。函數(shù)f(x)在x1,x2,x3三點處函數(shù)值f1,f2,f3，其中x1<x2<x3，且f(x1)>f(x2)<f(x3)。即在三點處函數(shù)值為“高—低—高”形態(tài)，見圖。作二次插值多項式p(x)=a+bx+cx2(A)2、p(x1)=a+bx1+cx12=f1p(x2)=a+bx2+cx22=f2(B)p(x3)=a+bx3+cx32=f33、對式（A）求導(dǎo)并令其等于零，得p/(x)=b+2cx=0由式（B）求待定系數(shù)a，b，c。得到多項式p(x)的極值點xp*。2023/2/221縮短區(qū)間：

若f(x)本身為二次函數(shù)，則在理論上一次求值就可找到最優(yōu)點，xp*即為所求。若f(x)為高于二次的函數(shù)或其它函數(shù)，則一般xp*不與原函數(shù)f(x)的極小點x*重合，如上圖所示。為了求得滿足一定精度要求的f(x)的極小點x*，可采用逐步縮小區(qū)間的辦法。搜索區(qū)間的縮小可根據(jù)xp*和x2，f(xp*)和f(x2)的相互關(guān)系，分六種不同的情況。

2023/2/2222023/2/2232023/2/2242023/2/225二次插值法計算步驟為：（1）確定初始搜索區(qū)間[x1,x3]，并給定ε。在初始區(qū)間[x1,x3]內(nèi)選定一點x2，應(yīng)滿足條件：x1<x2<x3,f(x1)>f(x2)<f(x3)，即函數(shù)值具有“高—低—高”形態(tài)。

（2）以x1,x2,x3三點構(gòu)造新插值曲線p(x)，并求出xp*。（3）檢驗∣x2-xp*∣<ε?若是，終止迭代，以x2,xp*中函數(shù)值較小的點作為最優(yōu)點x*；若否，轉(zhuǎn)下一步。

（4）判別x2和xp*,f(x2)和f(xp*)的相互關(guān)系屬于何種情況。舍去函數(shù)值較大的點x1（或x3），縮小區(qū)間，用x2,xp*,x3（或x1）作為新的三點（在這三點處函數(shù)值仍保持“高—低—高”形態(tài)），轉(zhuǎn)向（2）重新構(gòu)造新插值曲線p(x)。

2023/2/226

與0.618法相比較，二次插值法利用函數(shù)在已知幾個近似點的值來確定新的近似點位置。而0.618法僅對幾點函數(shù)值的大小進(jìn)行比較，沒有充分的利用函數(shù)本身的性質(zhì)。因此，當(dāng)函數(shù)f(x)具有較好的性質(zhì)（如連續(xù)可微性）時，插值法往往比0.618法效果好，但它的程序要比0.618法稍復(fù)雜些。2023/2/2272023/2/2282023/2/2292023/2/2302023/2/2312023/2/2323.4多維無約束優(yōu)化方法2023/2/2333.4多維無約束優(yōu)化方法2023/2/2343.4.2最速下降法（梯度法）在求解無約束極值問題的解析法中，最速下降法簡單易懂，迭代過程簡單，對初始點的要求不嚴(yán)格。特別是，一些更有效的方法也常是在對它的改進(jìn)后或在它的啟發(fā)下而獲得的。基本思想：在每個迭代點均沿著使目標(biāo)函數(shù)值下降最快的方向前進(jìn)，即負(fù)梯度方向，逐步走向最優(yōu)點。搜索方向取為：S(k)=-▽F(X(k))

或S(k)=-▽F(X(k))/||▽F(X(k))||則下一個迭代點為:X(k+1)=X(k)-λ(k)S(k)

2023/2/235最速下降法以負(fù)梯度方向（函數(shù)值下降最快方向）作為搜索方向2023/2/2362023/2/237梯度法（最速下降法）的特點：1）初始點選取沒有要求2）相鄰兩點的搜索方向正交缺點：迭代開始時下降幅度較大；在接近極小值點的時候，目標(biāo)函數(shù)下降得很慢總結(jié)：負(fù)梯度方向僅是局部下降最快，不是最好的下降方向最優(yōu)步長λ(k)的選取采用一維搜索：

F(X(k)+λ(k)S(k))=minF(X(k)+λS(k))2023/2/238最速下降法的迭代步驟：(1)給定初始點

X(0)及收斂精度ε,令k=0;(2)求目標(biāo)函數(shù)的梯度向量▽F(X(k));(3)若||▽F(X(k)||≤ε，停止迭代；否則轉(zhuǎn)下步。(4)用一維搜索方法確定步長λ(k)

。(5)按X-λ▽f(X)求得下一個點，且k=k+1；轉(zhuǎn)（2）。2023/2/2392023/2/2402023/2/2412023/2/2423.4.3共軛梯度法

梯度法在迭代點遠(yuǎn)離極小點時，收斂速度較快，當(dāng)?shù)c接近極小點時，收斂速度變慢，其與共軛方向法結(jié)合可構(gòu)成高效的混合算法。2023/2/243共軛梯度法第一步的搜索方向：負(fù)梯度方向第二步及以后各步的搜索方向為上一步搜索方向的共軛方向2023/2/244共軛方向（1）定義：為n階正定矩陣，若兩個矢量滿足則稱和對矩陣共軛。共軛矢量方向為共軛方向。（2）共軛方向與函數(shù)極小值點的關(guān)系考察正定二次函數(shù)2023/2/245兩式相減，得沿的共軛方向可搜索到正定二次函數(shù)極小值點。沿共軛方向的搜索具有二次收斂性2023/2/246共軛梯度法的特點：（1）具有超線性收斂速度，計算效率高于梯度法，低于牛頓法（2）對初始點沒有要求（3）不需計算二階偏導(dǎo)及其逆矩陣，計算量小2023/2/2473.4.2牛頓法及其改進(jìn)1、牛頓法基本思想：在X(k)鄰域內(nèi)用一個二次函數(shù)ф(X)來替代原目標(biāo)函數(shù)f(X)，并將ф(X)的極小點Xp*作為對原目標(biāo)函數(shù)f(X)求優(yōu)的下一個迭代點X(k+1),經(jīng)過多次迭代，使之逐步逼近f(X)的極小點X*。

f(X)≈f(X(k))+▽f(X(k))T(X–X(k))+

?(X-X(k))T▽2f(X(k))(X-X(k))=ф(X)

2023/2/248由于ф(X)是二次函數(shù)，求ф(X)的極小點即令其梯度為零▽?dǎo)?X)=▽f(X(k))+▽2f(X(k))(X-X(k))=0由此解得的X即為X(k+1)，即X(k+1)=X(k)-[▽2f(X(k))]-1▽f(X(k))=X(k)-H(X(k))-1▽f(X(k))

搜索方向為：

S(k)=-H(X(k))-1▽f(X(k))2023/2/249

如果f(X)本身為二次函數(shù)，則H(X)是一個常量矩陣，其元素均為常量，這時逼近式是準(zhǔn)確的，因此從任一點出發(fā)，一次迭代即可達(dá)到極小值。對于非二次函數(shù)，若函數(shù)的二次性態(tài)較強(qiáng)或迭代點已進(jìn)入最優(yōu)點的鄰域，則其收斂速度也是很快的。

2023/2/250例：試用牛頓法求函數(shù)f(X)=x12+25x22的極小點。2023/2/2512、阻尼牛頓法由于牛頓法中的步長λ(k)=1，會造成在迭代過程中函數(shù)值有所增大的情況。因此，對初始點的選取有嚴(yán)格要求，盡管用牛頓法收斂很快，但初始點不能離極小點太遠(yuǎn)，否則可能不收斂。極小點的位置又是事先未知的，這個要求難以達(dá)到。為了擺脫對初始點的苛刻要求，人們對牛頓法進(jìn)行了改進(jìn)，即阻尼牛頓法。阻尼牛頓法的迭代公式為

X(k+1)=X(k)-

λ(k)H(X(k))-1▽f(X(k))

阻尼牛頓法保持了牛頓法的特點，且對初始點無特別要求。雖然計算量多了些，但實用性較好。2023/2/2523、阻尼牛頓法迭代步驟如下：（1）取初始點X(0),ε>0,令K=0.（2）計算▽f(X(k)).（3）若║▽f(X(k))║≤ε,停止,X*=X(k);否則轉(zhuǎn)（4）.（4）計算H(X(k))-1,令S(k)=-H-1▽f(X(k)).（5）

求λ(k),使f(X(k)+λ(k)S(k))=minf(X(k)+λ(k)S(k)).（6）令X(k+1)=X(k)+λ(k)S(k),K=K+1,轉(zhuǎn)(2)

牛頓法和阻尼牛頓法雖具有收斂快的優(yōu)點，但它們最大的缺點是每次迭代都要計算二階導(dǎo)數(shù)矩陣Hessian矩陣及其逆陣H-1，此計算量比較繁瑣。此外，牛頓法還要求H(X)正定，否則H(X)為奇異陣，無法計算H-1,所以對于多變量復(fù)雜目標(biāo)函數(shù)的優(yōu)化問題，故此法不可用。2023/2/2533.4.5變尺度法優(yōu)化迭代的一般公式可以表達(dá)為

X(k+1)=X(k)-λ(k)Ak▽f(X(k))

變尺度法：Ak是需要構(gòu)造的一個n×n對稱方陣,即尺度矩陣。2023/2/254尺度矩陣A(k)的構(gòu)造，可從初始矩陣A(k)=E（單位矩陣）開始，它通過對公式

A(k+1)=A(k)+ΔA(k)

中的修正矩陣ΔA(k)的不斷修正，在迭代中逐步逼近于H(X(K))-1。由于修正矩陣的不同，就構(gòu)成了種種不同的變尺度法。2023/2/255DFP法中的修正矩陣ΔA(k)為：

式中：Δg(k)=g(k+1)-g(k)=▽f(X(k+1))-▽f(X(k))△X(k)=X(k+1)-X(k)

另一種變尺度法為BFGS，計算公式見書中表述。2023/2/256例：用DFP法解minf(X)=60-10x1-4x2+x12+x22-x1x2。初始點為X(0)=(0,0)T,ε=0.0001.解：（1）令K=0,（2）計算目標(biāo)函數(shù)的梯度▽f(X(0))

（3）搜索方向為

雖然此時搜索方向為負(fù)梯度方向。沿此方向進(jìn)行一維搜索，求得最優(yōu)步長因子λk2023/2/257將X(1)=X(0)+λS(0)代入目標(biāo)函數(shù)得

f(X(1))=60-10(10λ)-4(4λ)+(10λ)2+(4λ)2-(10λ)(4λ)=60-116λ+76λ

2=q(λ)為求極小值，將上式對λ求導(dǎo)，并令q/(λ)=0，即

dq/dλ=-116+152λ=0解得λ(0)=0.7631得X(1)=X(0)+λ(0)S(0)=[0,0]T+0.7631[10,4]T=[7.631,3.052]T（4）收斂性判別2023/2/258(5）因此時K<n=2，所以計算△X(k)=△X(0)=X(1)-X(0)=[7.631,3.052]T△g(k)=△g(0)=▽f(X(1))-▽f(X(0))=[12.211,-1.526]T按公式計算尺度矩陣

A(k+1)=A(k)+ΔA(k)和ΔA(k)=(ΔX(k)ΔX(k)T)/(ΔX(k)TΔg(k))-(A(k)Δg(k)Δg(k)TA(k))/(Δg(k)TA(k)Δg(k))計算近似矩陣A(k+1)A(1)=A(0)+ΔA(0)=由此可見，它是一個對稱正定矩陣。2023/2/259（6）K←k+1。構(gòu)造新的搜索方向（擬牛頓方向）為:S(k+1)=S(1)=-A(1)▽f(X(1))=[0.646,5.169]T

沿S(1)方向作一維搜索求λ(1)，方法與求λ(0)相同，得λ(1)=0.5701，新的迭代點為:X(2)=X(1)+λ(1)S(1)=[7.9999,5.9999]T≈[8,6]T（7）收斂性差別：║▽f(X(2))║=(02+02)1/2<ε，停止迭代。輸出最優(yōu)解

X*=X(2)=[8,6]Tf(X*)=f(X(2))=8注意：DFP變尺度法屬于共軛方向法。2023/2/260對比以二次函數(shù)為例：梯度法：每步以負(fù)梯度方向為搜索方向，要走很多步才能到達(dá)極值點附近。牛頓法：從初始點出發(fā)沿負(fù)梯度方向轉(zhuǎn)移角度一步即可到達(dá)極值點。共軛梯度法：第一步負(fù)梯度方向，第二步梯度的共軛方向，兩步達(dá)到最優(yōu)。變尺度法：兩步達(dá)到最優(yōu)2023/2/261二元四次函數(shù)方法梯度法牛頓法共軛梯度法變尺度法次數(shù)100355極值2.5402.111.7次數(shù)7320極值002023/2/262直接解法2023/2/2633.4.5坐標(biāo)輪換法坐標(biāo)輪換法屬于直接解法。坐標(biāo)輪換法的基本思想是將n個變量的優(yōu)化問題轉(zhuǎn)化為一系列一維最優(yōu)化問題來求解。設(shè)n維設(shè)計變量為

X=[x1,x2,…,xn]Tn維空間的坐標(biāo)方向（坐標(biāo)軸的單位向量）為：

e1=[1,0,0,……,0]Te2=[0,1,0,……,0]T……en=[0,0,0,……,0,1]T坐標(biāo)輪換法就是分別（輪換地）沿各個坐標(biāo)軸方向搜索最優(yōu)解2023/2/264

簡單地說，就是先將n-1個變量固定不變，只對第一個變量x1（即e1方向）進(jìn)行一維搜索，得到最優(yōu)解X(1)。然后再對第二個變量進(jìn)行一維搜索，而保持其余n-1個變量不變，如此等等。每次均保持n-1個變量不變，只對一個變量進(jìn)行一維搜索，如此一直得到X(n),即完成一次輪換計算。若滿足收斂準(zhǔn)則，則停止迭代；否則從前一輪的最末點X(n)開始，將X(n)賦值給X(0)，重復(fù)上述過程，作下一輪搜索。如此直到收斂為止。根據(jù)上述原理，對于第k輪計算，其迭代計算公式為

Xi(k)=Xi-1(k)+λSi(k)(i=1,2,…,n)

Si(k)=ei=1(i=1,2,…,n)2023/2/265坐標(biāo)輪換法的迭代步驟如下：（１）取初始點X(0)及ε>0，令k=1。（２）令i=1,Xi-1(k)=

X(0)。（3）一維搜索求在ei方向的最優(yōu)步長λi，使

f(Xi-1(k)+λi(k)ei)=minf(Xi-1(k)+λei)Xi(k)=Xi-1(k)+λi(k)ei（4）

若i=n，則轉(zhuǎn)（5）；否則，則i=i+1，轉(zhuǎn)(3)。（5）

檢驗‖Xn(k)-X0(0)‖≤ε？若滿足收斂準(zhǔn)則，停止迭代，X*=Xn(k)；否則，令X(0)=Xn(k)，k=k+1，轉(zhuǎn)(2)。2023/2/266例：用坐標(biāo)輪換法求minf(X)=60-10x1-4x2+x12+x22-x1x2，取X(0)=[0,0]T。解：其搜索過程如圖：第一次迭代：令x1=0，則f(x2)=60-4x2+x22,對x2尋優(yōu)得x2=2，此時f(X(1))=56，再固定x2=2，則f(x1)=56-12x1+x12，對x1尋優(yōu)得x1=6，此時f(X(2))=20，即X(2)=[6,2]T，轉(zhuǎn)下一輪。2023/2/267

第二輪迭代：

固定x1=6，則f(x2)=36-10x2+x22，對x2尋優(yōu)得x2=5，此時f(X(3))=11，再固定x2=5，則f(x1)=65-15x1+x12，對x1尋優(yōu)得x1=7.5，此時f(X(4))=8.75，即X(4)=[7.5,5]T，轉(zhuǎn)下一輪。如此迭代下去，直至逼近實際極小點

X*=[8,6]T,f(X*)=82023/2/2683.4.6Powell（鮑威爾）法鮑威爾法是無約束最優(yōu)化問題效果最佳的一種計算方法。在優(yōu)化設(shè)計中，常使用鮑威爾法配合懲罰函數(shù)法，來處理有約束優(yōu)化問題，它屬于共軛方向法。鮑威爾法又分為初始鮑威爾法和改進(jìn)的鮑威爾法2023/2/269改進(jìn)鮑威爾法基本思想是：基于坐標(biāo)輪換法的構(gòu)思，在不使用導(dǎo)數(shù)的前提下，在迭代中逐次產(chǎn)生共軛方向組（以加快收斂速度）。在每輪迭代獲得新的方向Sk(n+1)之后，在組成下一輪迭代的新方向組時，有選擇地去掉其中某一個方向Skm（1≤m≤n），以避免新方向組中的各方向出現(xiàn)線性相關(guān)的情形。2023/2/270這種改進(jìn)的具體方法是：（1）選擇初始點X(0)作為X0(1)，選擇計算精度ε，取n個單位坐標(biāo)向量為初始方向組，即

Si(0)=ei

,(i=1,2,…,n)（2）從X0(1)出發(fā)，用坐標(biāo)輪換法依次沿S1(0)

、S2(0)

、…、Sn(0)方向作一維搜索，可得各自方向上的