優(yōu)化設(shè)計(jì)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)]

從一個(gè)初始點(diǎn)X(0)出發(fā)，按一定規(guī)則確定一個(gè)搜索方向S(0),然后在S(0)上搜索到目標(biāo)函數(shù)的極小值X(1)；接著又以X(1),作為下一個(gè)迭代的出發(fā)點(diǎn)，重復(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)，在極小點(diǎn)左邊，函數(shù)值隨x的增加是嚴(yán)格減小的；在極小點(diǎn)右邊，函數(shù)是嚴(yán)格增大的。因此在單峰區(qū)間內(nèi)，函數(shù)值具有“高——低——高”的形態(tài)，可利用這一特征來確定初始單峰區(qū)間。2.確定單峰區(qū)間的進(jìn)退算法一維搜索的各種方法的基本思想是“區(qū)間消去法”，而區(qū)間消去法的基本思想是：逐步縮小搜索的區(qū)間，直至最小點(diǎn)存在的范圍小于給定的誤差范圍為止。2023/2/24基本思路：對(duì)單峰函數(shù)f(x)任選一個(gè)初始點(diǎn)x1及初始步長h，通過比較這兩點(diǎn)函數(shù)值的大小，來決定第三點(diǎn)的位置，比較這三點(diǎn)的函數(shù)值的大小，確定是否為“高——低——高”的形態(tài)，依此確定向前或后退搜索。2023/2/25確定單峰區(qū)間的進(jìn)退算法進(jìn)退法：通過比較函數(shù)值大小來確定單峰區(qū)間的方法。給定的初始點(diǎn)和步長

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

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

(2)

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

2023/2/27(3)

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

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

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

對(duì)稱取點(diǎn)原則：即所插入兩點(diǎn)在區(qū)間中位置對(duì)稱。2023/2/2110.618法算法步驟為：確定f(x)的初始搜索區(qū)間[a,b]及終止限ε。計(jì)算x2=a+0.618(b-a),f2=f(x2);計(jì)算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,

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

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

取N=5

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

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

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

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

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

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

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

2023/2/226

與0.618法相比較，二次插值法利用函數(shù)在已知幾個(gè)近似點(diǎn)的值來確定新的近似點(diǎn)位置。而0.618法僅對(duì)幾點(diǎn)函數(shù)值的大小進(jìn)行比較，沒有充分的利用函數(shù)本身的性質(zhì)。因此，當(dāng)函數(shù)f(x)具有較好的性質(zhì)（如連續(xù)可微性）時(shí)，插值法往往比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最速下降法（梯度法）在求解無約束極值問題的解析法中，最速下降法簡單易懂，迭代過程簡單，對(duì)初始點(diǎn)的要求不嚴(yán)格。特別是，一些更有效的方法也常是在對(duì)它的改進(jìn)后或在它的啟發(fā)下而獲得的?；舅枷耄涸诿總€(gè)迭代點(diǎn)均沿著使目標(biāo)函數(shù)值下降最快的方向前進(jìn)，即負(fù)梯度方向，逐步走向最優(yōu)點(diǎn)。搜索方向取為：S(k)=-▽F(X(k))

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

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

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

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

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

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

搜索方向?yàn)椋?/p>

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

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

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

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

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

阻尼牛頓法保持了牛頓法的特點(diǎn)，且對(duì)初始點(diǎn)無特別要求。雖然計(jì)算量多了些，但實(shí)用性較好。2023/2/2523、阻尼牛頓法迭代步驟如下：（1）取初始點(diǎn)X(0),ε>0,令K=0.（2）計(jì)算▽f(X(k)).（3）若║▽f(X(k))║≤ε,停止,X*=X(k);否則轉(zhuǎn)（4）.（4）計(jì)算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)點(diǎn)，但它們最大的缺點(diǎn)是每次迭代都要計(jì)算二階導(dǎo)數(shù)矩陣Hessian矩陣及其逆陣H-1，此計(jì)算量比較繁瑣。此外，牛頓法還要求H(X)正定，否則H(X)為奇異陣，無法計(jì)算H-1,所以對(duì)于多變量復(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)造的一個(gè)n×n對(duì)稱方陣,即尺度矩陣。2023/2/254尺度矩陣A(k)的構(gòu)造，可從初始矩陣A(k)=E（單位矩陣）開始，它通過對(duì)公式

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，計(jì)算公式見書中表述。2023/2/256例：用DFP法解minf(X)=60-10x1-4x2+x12+x22-x1x2。初始點(diǎn)為X(0)=(0,0)T,ε=0.0001.解：（1）令K=0,（2）計(jì)算目標(biāo)函數(shù)的梯度▽f(X(0))

（3）搜索方向?yàn)?/p>

雖然此時(shí)搜索方向?yàn)樨?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(λ)為求極小值，將上式對(duì)λ求導(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）因此時(shí)K<n=2，所以計(jì)算△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按公式計(jì)算尺度矩陣

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))計(jì)算近似矩陣A(k+1)A(1)=A(0)+ΔA(0)=由此可見，它是一個(gè)對(duì)稱正定矩陣。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，新的迭代點(diǎn)為: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對(duì)比以二次函數(shù)為例：梯度法：每步以負(fù)梯度方向?yàn)樗阉鞣较?，要走很多步才能到達(dá)極值點(diǎn)附近。牛頓法：從初始點(diǎn)出發(fā)沿負(fù)梯度方向轉(zhuǎn)移角度一步即可到達(dá)極值點(diǎn)。共軛梯度法：第一步負(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個(gè)變量的優(yōu)化問題轉(zhuǎn)化為一系列一維最優(yōu)化問題來求解。設(shè)n維設(shè)計(jì)變量為

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)輪換法就是分別（輪換地）沿各個(gè)坐標(biāo)軸方向搜索最優(yōu)解2023/2/264

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

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

Si(k)=ei=1(i=1,2,…,n)2023/2/265坐標(biāo)輪換法的迭代步驟如下：（１）取初始點(diǎn)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）

檢驗(yàn)‖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,對(duì)x2尋優(yōu)得x2=2，此時(shí)f(X(1))=56，再固定x2=2，則f(x1)=56-12x1+x12，對(duì)x1尋優(yōu)得x1=6，此時(shí)f(X(2))=20，即X(2)=[6,2]T，轉(zhuǎn)下一輪。2023/2/267

第二輪迭代：

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

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

Si(0)=ei

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

、S2(0)

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