機械優(yōu)化設計第四節(jié)無約束-坐標輪換法3-5

坐標輪換法的基本思想它是無約束多維函數(shù)的優(yōu)化方法中最簡單的一種，它將一個無約束n維優(yōu)化問題轉(zhuǎn)化為依次沿著相應的n個坐標軸方向的一維優(yōu)化問題來求解。2.3、坐標輪換法1.基本思想(原理)：二維迭代過程：推廣到n維迭代過程個變量固定不動只變化第一個變量著第一個變量即由初始點沿進行一維搜索，得到好點(2)保持除外的個變量不變，沿第二變量進行一維搜索。得到好點(1)先將的方向此時的搜索方向為

（3）如此沿方向(即坐標方向),且將前一次一維搜索的極小點作為本次一維搜索的起始點，依次進行一維搜索后，完成一輪迭代。為起始（4）若未收斂則以前一次的末點點，進行下一輪的循環(huán)，如此一輪一輪迭代下去，直到滿足收斂準則，逼近最優(yōu)點為止。2.迭代計算步驟1)取初始點作為第一輪的起點

精度迭代終止置個坐標軸方向矢量為單位坐標矢量沿第個坐標方向，用一維搜索方法求最優(yōu)迭代步長和各分量式中

為第輪迭代中沿第坐標方向為第輪迭代中沿第坐標方向的最優(yōu)步長（通過一維優(yōu)化求出最優(yōu)解）2)按照上式公式進行迭代計算，式中k為迭代輪數(shù)的序號，取k＝1，2，…，為該輪中一維搜索的序號，依次取i＝1，2，…，n。步長通過一維優(yōu)化方法求得。

3)按點距準則判斷是否收斂（采用迭代準則是一輪迭代的始點與終點之間的點距，而不能按某搜索方向的前后迭代點）都滿足迭代終止并輸出最優(yōu)解否則令返回步驟(2)坐標輪換法的流程圖：入口給定沿方向一維搜索求是否是否出口特點：簡單易行，但由于它只能輪流沿幾個坐標方向前進，因而效率低下，特別是維數(shù)較高n>10或目標函數(shù)性質(zhì)不好的情況下收斂速度慢。本方法的收斂效率在很大程度上取決于目標函數(shù)等值線的形狀。當橢圓簇的長短軸與坐標軸斜交，迭代次數(shù)將大大增加，收斂速度很緩慢。目標函數(shù)

等值線為橢圓簇其長短軸與坐標軸平行或同圓簇等值線收斂效率高速度快，若目標函數(shù)等值線出現(xiàn)脊線時沿著坐標軸方向搜索均不能使函數(shù)值有所下降，算法中將失效，這類函數(shù)對坐標輪換法來說是病態(tài)函數(shù)。搜索過程的幾種儲況a)搜索有效b)搜索低效c)搜索無效例：用坐標輪換法求目標函數(shù)給定初始點精度要求解：作第一輪迭代計算沿方向進行一維搜索的無約束最優(yōu)解：求最步長即極小化此問題可用某種一維優(yōu)化方法求出

在這里用微分學(解析法)求導解出:令一階導數(shù)為零可得

以

為起點沿

方向一維搜索

求最步長：

得

對于第一輪終止條件檢驗

繼續(xù)進行第二輪迭代計算以下各輪列于下表

迭代輪數(shù)k

1

5

4.5

6.73

2

2.25

1.125

2.516

迭代輪數(shù)k

3

0.563

0.282

0.623

4

0.141

0.071

0.158

5

0.035

0.018

0.04

計算第五輪的有

近似優(yōu)化解為：

2.4、共軛方向法

1、共軛方向坐標輪換法的收斂速度很慢，原因在于其搜索方向總是平行于坐標軸，不適應函數(shù)變化情況如圖所示若把一輪的起點

與末點

連起來形成

一個新的搜索方向,

與

有何關(guān)系。如圖所示，設給定兩個平行方向

,從兩個任意初始點分別，顯然分別是兩條平行線與函數(shù)等值線的相切點.

沿這兩個平行方向進行一維搜索求得極小點

二維函數(shù)的共軛方向與連結(jié)二切點構(gòu)成向量。

即

則可以證明若函數(shù)

矩陣為正定矩陣則方向

的海色與

滿足下式

具有這樣性質(zhì)的方向，即是共軛方向如圖所示，同心橢圓簇具有這樣一個特點，就是二條任意平行線的切點的連線必通過橢圓族的中心。共軛方向的定義：

設A為

階實對稱正定矩陣,而

為

維空間

中的兩個非零向量，如果滿足

則稱向量

關(guān)于對稱正定矩陣A是共軛的或關(guān)于A共軛共軛方向的性質(zhì)1)設A為

階實對稱正定矩陣,

為對A共軛的n個非零向量，則這n個向量是線形無關(guān)的2)在n維空間中互相共軛的非零向量的個數(shù)不超過n。即:共軛向量的個數(shù)最多等于n(單位坐標向量系是一組線性無關(guān)的共軛向量的最簡單例子，且它們也是正交向量系)。3)設A為

階實對稱正定矩陣，

是關(guān)于A的

個互相共軛的非零向量。對于正定二次函數(shù)

的極小化尋優(yōu)問題，從任何初始點出發(fā)依次沿

方向經(jīng)

次一維搜索即可收斂到極

小點

這種性質(zhì)表明這種迭代方法具有二次收斂性。對于二元二次正定函數(shù)

為共軛方向，若

為起始點,分別沿方向作（經(jīng)過

兩個共軛方向的一維搜索得到極小點）一維搜索即可到達二元二次正定函數(shù)的極小點。明確了共軛方向的概念，再來證明

設二元函數(shù)在極值點

附近的二次泰勒近似展開

式為

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

故有

由于兩平行方向

為等值線的切線,其切點分別為

故方向

應垂直于

處的梯度方向.為目標函數(shù)

在

方向的極小點兩點目標函數(shù)的梯度

都與

矢量

正交即有

即有所以在兩式相減的

而

故由上式可得

推演到n維函數(shù)即在n維空間中可以同時構(gòu)成n個關(guān)于H的共軛方向

對于對稱正定二次n維函數(shù)從任意初始點

出發(fā)順序沿著這個線性無關(guān)的方向進行一維搜索就得到目標函數(shù)的極小點

(可以證明)。因而說共軛方向法具有有限步收斂的特性通常稱具有這種性質(zhì)的方法為二次收斂法.但對于非二次n維目標函數(shù)經(jīng)過有限步共軛方向一維搜索，不一定就能達到極小點。

在這種情況下，可取其二次泰勒近似式加以討論。當進行一輪次迭代還未取得極小點時可作為新的初始點再進行第二輪迭代。共軛方向的基本原理首先采用坐標輪換法進行第一輪迭代，然后以第一輪迭代的最末一個極小點和初始點相連構(gòu)成一個新方向，并以此新方向為最末一個方向而去掉第一個方向得到第二輪迭代的方向.如此進行下去。直到求得問題的最小點。現(xiàn)以二維問題來說明

算法步驟⑴令循環(huán)次數(shù)

取初始點

初始搜索方向為坐標方向

⑵從出發(fā)依次沿

和

進行一維搜索得到第一次循環(huán)的極小點⑶構(gòu)造新方向

沿

進行一維方向搜索得到第k次循環(huán)的極小點⑷取下次循環(huán)的初始點

去掉原來的第一方向

構(gòu)造新的搜索方向

令轉(zhuǎn)(2)繼續(xù)迭代直到滿足收斂條件，迭代計算結(jié)束即某輪中初始點與末端點之間的距離達到預期的精度要求。同理,對于n維二次目標函數(shù)共軛方向的構(gòu)成和迭代過程與上述2維二次目標函數(shù)共軛方向相類似。x1x3x2e1e2e3X0(1)S1e2e3S1X1(1)X2(1)X3(1)X0(2)X1(2)X2(2)X3(2)X0(3)S2e3S1S2S3X1(3)X2(3)X3(3)X0(4)第1輪第2輪第3輪對于正定二次n維函數(shù)，從任意的初始點出發(fā)，沿著這n個共軛方向進行一維搜索，就可以得到目標函數(shù)的極小點。因此，對于二次函數(shù)來說，經(jīng)過n步搜索就可以達到函數(shù)的極小點。對于非二次n維函數(shù)，可以用二階泰勒級數(shù)將函數(shù)在極小點附近展開，省略去高于二次的項后可以得到函數(shù)的二次近似，同樣按照二次函數(shù)構(gòu)成共軛方向。

共軛方向法具有二次收斂性

n維二次函數(shù)原始共軛方向的構(gòu)成步驟

第1環(huán)搜索

依次沿一組線性無關(guān)的初始基本方向組

（坐標軸方向）進行一維優(yōu)化搜索，以初始點

和終點

的連線作為第1環(huán)的新生方向

，再沿方向

搜索得到第1環(huán)的極小點

。

第

環(huán)搜索以第

環(huán)的極小點

作為初始點，以第

環(huán)的新生方向

取代第1個方向

，即

，構(gòu)成第

環(huán)搜索基本方向組,

進行一維最優(yōu)化搜索。以初始點

和終點

的連線作為第

環(huán)的新生方向

，再沿方向

搜索得到第

環(huán)的極小點

。

第n環(huán)搜索當搜索環(huán)數(shù)

時，完成一輪迭代。在一輪迭代過程中的新生方向構(gòu)成了

個共軛方向。對于正定二次函數(shù)

，經(jīng)過一輪迭代的極小點

就是函數(shù)的極小點

。而對于n維非二次函數(shù)來說，一般要經(jīng)過若干輪迭代才能達到極小點。2.5、鮑威爾法------powell共軛方向法共軛方向法的基本要求是，各方向組的向量

應該是線性無關(guān)的.然而很不理想的是

上述方法高次迭代時所產(chǎn)生的新方向可能出現(xiàn)線性相關(guān)，從而導致計算不能收斂到真正的極小點而失敗。為此1964年鮑威爾提出了對共軛方向法的改進方法。例如在進行某輪搜索時，由于在第一個分量這個特定的方向搜索沒有進展而迭代點的收斂基本為零，則可能形成兩個搜索方向基本上成為共線。以后的各次搜索在維數(shù)下降了的空間進行，真正的極小點可能被漏掉，這種現(xiàn)象稱為“退化”新的一輪搜索中，迭代方向組成為線性相關(guān)，從而導致計算不能收斂到真正的極小點而失敗。以避免新產(chǎn)生的方向組中的各方向出現(xiàn)線性相關(guān)的情形，保證新方向組比前一方向組具有更好的共軛性質(zhì)。為此powell提出了是否用方向來組成新的搜索方向組的判別條件powell提出了在每輪獲得新方向之后在組成新的方向組時不一屢去掉前一輪的第一個方向而去有選擇地去掉其中某一個方向在powell法中判斷是否用新的方向替換原方向組中某一方向的判別準則按下式是否同時滿足來進行處理判別條件：式中k輪中起始點的函數(shù)值k輪方向組一維搜索終點的函數(shù)值為對的映射點函數(shù)值k輪函數(shù)函數(shù)值下降最大值其對應的方向為若同時滿足判別準則（powell判別條件）則在輪循環(huán)中選用新方向?qū)⒀a入輪循環(huán)的基本方向組的最后并去掉方向即以構(gòu)成第輪循環(huán)的基本方向組并取第輪循環(huán)的初始點為(為第輪循環(huán)中沿新方向一維搜索求得的極小點);輪循環(huán)仍用原來的n個搜索方向此時初始點則應選取值較小者即當兩點中函數(shù)時取時取若不滿足判別準則（Powell判別條件）則在powell法解決了兩個關(guān)鍵問題①在每一輪迭代完成并產(chǎn)生共軛方向后，先對共軛方向的好壞進行判別，檢驗它是否與其它方向線性相關(guān)。若共軛方向不好則不用它作為下輪的迭代方向，而后采用原來的一組迭代方向。②若共軛方向好，則可用它替換前一輪迭代中使函數(shù)值下降最快的一個方向，而不一定替換第一個迭代方向。Powell法解決了兩個關(guān)鍵問題在第

環(huán)搜索時，首先，對于已經(jīng)獲得的

個共軛方向（包括新生方向）

好壞進行判斷，檢驗它是否與其他方向線性相關(guān)或接近線性相關(guān)。如果共軛方向不好(不滿足Powell判別式），則不用它作為下一環(huán)搜索的基本方向組，仍然選用上一環(huán)搜索的基本方向組，以保證能夠選取

個線性無關(guān)方向。如果共軛方向好(滿足Powell判別式），則用它替換上一環(huán)搜索的基本方向組中函數(shù)值下降最多的一個方向，不一定替換上一環(huán)搜索基本方向組的第1個方向，以加快搜索的收斂速度。powell算法的迭代步驟⑴給定初始點和允許誤差或⑵取n個坐標軸的單位向量為搜索方向置k=1(k為迭代輪組)⑶從出發(fā),分別沿作為一輪n次一維搜索,依次得n個極小點得到⑷計算各相鄰極小點目標函數(shù)值的差值，并找出其中的最大值及其相應的方向⑸計算映射點計算結(jié)果