演示文稿第六節(jié)無約束優(yōu)化方法鮑威爾當(dāng)前1頁，總共46頁。第六節(jié)無約束優(yōu)化方法鮑威爾ppt課件當(dāng)前2頁，總共46頁?！?.5坐標(biāo)輪換法一.坐標(biāo)輪換法：1.基本思想：每次搜索只允許一個(gè)變量變化，其余變量保持不變，即沿坐標(biāo)方向輪流進(jìn)行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量（其余變量視為常量）的優(yōu)化問題，因此又稱這種方法為變量輪換法。此種方法只需目標(biāo)函數(shù)的數(shù)值信息而不需要目標(biāo)函數(shù)的導(dǎo)數(shù)。當(dāng)前3頁，總共46頁。計(jì)算步驟:⑴任選初始點(diǎn),確定搜索方向第一輪的起點(diǎn)，置n個(gè)坐標(biāo)軸方向矢量為單位坐標(biāo)矢量§4.5坐標(biāo)輪換法當(dāng)前4頁，總共46頁。⑵迭代計(jì)算k為迭代輪數(shù)的序號(hào)，取k=1，2，……；i為該輪中一維搜索的序號(hào)，取i=1，2，……n步長(zhǎng)α一般通過一維優(yōu)化方法求出其最優(yōu)步長(zhǎng)。⑶判斷是否中止迭代如滿足，迭代中止，并輸出最優(yōu)解最優(yōu)解否則，令k←k+1返回步驟（2）§4.5坐標(biāo)輪換法

應(yīng)該是一輪迭代的始點(diǎn)和終點(diǎn)，不是某搜索方向的前后迭代點(diǎn)。當(dāng)前5頁，總共46頁。坐標(biāo)輪換法的流程圖當(dāng)前6頁，總共46頁。例:用坐標(biāo)輪換法求下列目標(biāo)函數(shù)的無約束最優(yōu)解。

給定初始點(diǎn)，精度要求ε=0.1解：做第一輪迭代計(jì)算沿e1方向進(jìn)行一維搜索式中，為第一輪的起始點(diǎn)，取當(dāng)前7頁，總共46頁。按最優(yōu)步長(zhǎng)原則確定最優(yōu)步長(zhǎng)α1，即極小化此問題可由某種一維優(yōu)化方法求出α1:

以為新起點(diǎn)，沿e2方向一維搜索以最優(yōu)步長(zhǎng)原則確定α2，即為極小化當(dāng)前8頁，總共46頁。對(duì)于第一輪按終止條件檢驗(yàn)計(jì)算5輪后，有故近似優(yōu)化解為當(dāng)前9頁，總共46頁?！?.5

坐標(biāo)輪換法

3.方法評(píng)價(jià)：

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

受目標(biāo)函數(shù)的性態(tài)影響很大。如圖a)所示，二次就收斂到極值點(diǎn)；如圖b)所示，多次迭代后逼近極值點(diǎn)；如圖c)所示，目標(biāo)函數(shù)等值線出現(xiàn)山脊（或稱陡谷），若搜索到A點(diǎn)，再沿兩個(gè)坐標(biāo)軸以±t0步長(zhǎng)測(cè)試，目標(biāo)函數(shù)值均上升，計(jì)算機(jī)判斷A點(diǎn)為最優(yōu)點(diǎn)。事實(shí)上發(fā)生錯(cuò)誤。當(dāng)前10頁，總共46頁。

鮑威爾方法是直接搜索法中一個(gè)十分有效的算法。該算法是沿著逐步產(chǎn)生的共軛方向進(jìn)行搜索的，因此本質(zhì)上是一種共軛方向法?！?.6

鮑威爾方法

當(dāng)前11頁，總共46頁。一、共軛方向的生成§4.6

鮑威爾方法

為兩個(gè)極小點(diǎn)根據(jù)梯度與等值面之間關(guān)系可知當(dāng)前12頁，總共46頁。一、共軛方向的生成§4.6

鮑威爾方法

對(duì)于二次函數(shù)，兩點(diǎn)處的梯度可表示為代入到公式：當(dāng)前13頁，總共46頁。一、共軛方向的生成§4.6

鮑威爾方法

結(jié)論：從不同的點(diǎn)出發(fā)沿某一方向分別對(duì)函數(shù)作兩次一維搜索，得到兩個(gè)極小點(diǎn)，那么這兩個(gè)極小點(diǎn)的連線方向與該方向?qū)共軛當(dāng)前14頁，總共46頁。二、鮑威爾基本算法

鮑威爾基本算法的搜索過程（二維）當(dāng)前15頁，總共46頁。二、鮑威爾基本算法

鮑威爾基本算法的搜索過程（三維）當(dāng)前16頁，總共46頁。

鮑威爾基本算法的步驟：

1）第一輪基本方向組取單位坐標(biāo)矢量系e1、e2、

e3

、…、en，沿這些方向依次作一維搜索，然后將始末兩點(diǎn)相連作為新生方向。

2）再沿新生方向作一維搜索，完成第一輪的迭代。以后每輪的基本方向組是將上輪的第一個(gè)方向淘汰，上輪的新生方向補(bǔ)入本輪的最后而構(gòu)成：

d2k

,

d3k,……dnk

,

dk當(dāng)前17頁，總共46頁。

鮑威爾基本算法的缺陷：

可能在某一輪迭代中出現(xiàn)基本方向組為線性相關(guān)的矢量系的情況。如第k輪中，產(chǎn)生新的方向：

dk=xnk-x0k=1kd1k+2kd2k+???+nkdnk

式中，d1k、d2k、

???、

dnk為第k輪基本方向組矢量，1k

、2k、???、nk為各方向的最優(yōu)步長(zhǎng)。

若在第k輪的優(yōu)化搜索過程中出現(xiàn)1k=0，則方向dk表示為d2k、

d3k

、???、

dnk的線性組合，以后的各次搜索將在降維的空間進(jìn)行，無法得到n維空間的函數(shù)極小值，計(jì)算將失敗。

當(dāng)前18頁，總共46頁。鮑威爾基本算法的退化x1x2x31=02e23e3S1如圖所示為一個(gè)三維優(yōu)化問題的示例，設(shè)第一輪中1=0

，則新生方向與e2、e3共面，隨后的各環(huán)方向組中，各矢量必在該平面內(nèi)，使搜索局限于二維空間，不能得到最優(yōu)解。e2e3S1當(dāng)前19頁，總共46頁。三、鮑威爾修正算法

在某輪已經(jīng)取得的n+1個(gè)方向中，選取n個(gè)線性無關(guān)的并且共軛程度盡可能高的方向作為下一輪的基本方向組

鮑威爾修正算法的搜索方向的構(gòu)造：在第k輪的搜索中，x0k

為初始點(diǎn)，搜索方向?yàn)閐1k、d2k

、

???、

dnk，產(chǎn)生的新方向?yàn)閐k

，此方向的極小點(diǎn)為xk。沿dk方向移動(dòng)得到點(diǎn)

xn+1k=2xnk-x0k

，稱之為x0k對(duì)xnk的映射點(diǎn)。

計(jì)算x0k

、

x1k、???、xnk、xk、xn+1k

各點(diǎn)的函數(shù)值，記作：

F1=F(x0k)

F2=F(xnk)

F3=F(xn+1k)=F(xm-1k)-F(xmk)

是第k輪方向組中，依次沿各方向搜索函數(shù)下降值當(dāng)前20頁，總共46頁。鮑威爾算法的方向淘汰(F3)(F2)(F1)反射點(diǎn)函數(shù)最大下降量△m始點(diǎn)終點(diǎn)當(dāng)前21頁，總共46頁。為了構(gòu)造第k+1輪基本方向組，采用如下判別式：

按照以下兩種情況處理：

1)

上式中至少一個(gè)不等式成立，則第k+1輪的基本方向仍用老方向組d1k、d2k、

???、

dnk。k+1輪的初始點(diǎn)取

x0k+1=xnkF2<F3

x0k+1=xn+1kF2F3

當(dāng)前22頁，總共46頁。2）兩式均不成立，則淘汰函數(shù)值下降最大的方向，并用第k輪的新生方向補(bǔ)入k+1輪基本方向組的最后，即k+1輪的方向組為d1k、d2k

、???、dm-1k、dm+1k、???、dnk、

dk

。(F3)(F2)(F1)反射點(diǎn)始點(diǎn)終點(diǎn)函數(shù)最大下降量△m當(dāng)前23頁，總共46頁。k+1輪的初始點(diǎn)取:

x0k+1=xk

xk是第k輪沿dk方向搜索的極小點(diǎn)。

(F3)(F2)(F1)反射點(diǎn)函數(shù)下降量△始點(diǎn)終點(diǎn)dk方向極小點(diǎn)當(dāng)前24頁，總共46頁。四、修正算法的迭代步驟及流程圖Powell算法的步驟如下：⑴

任選初始迭代點(diǎn)，選定迭代精度ε，取初始基本方向組為單位坐標(biāo)矢量系其中，i=1，2……n

然后令k=1（輪數(shù)）開始迭代⑵

沿諸方向依次進(jìn)行n次一維搜索，確定各步長(zhǎng)當(dāng)前25頁，總共46頁。得到點(diǎn)陣i=1，2……n構(gòu)成新生方向沿方向進(jìn)行一維搜索求得優(yōu)化步長(zhǎng)(3)計(jì)算各迭代點(diǎn)的函數(shù)值，找出相鄰點(diǎn)函數(shù)值差最大者（1≤m≤n）及與之相對(duì)應(yīng)的兩個(gè)點(diǎn)和，并以表示兩點(diǎn)的連線方向。當(dāng)前26頁，總共46頁。（4）關(guān)鍵點(diǎn)函數(shù)值（5）判斷是否滿足迭代終止條件。則可結(jié)束迭代，最優(yōu)解為停止計(jì)算。否則，繼續(xù)進(jìn)行下步。當(dāng)前27頁，總共46頁。檢驗(yàn)鮑威爾判別條件是否成立若至少其中之一成立轉(zhuǎn)下步，否則轉(zhuǎn)步驟⑺⑹

確定k+1輪的基本方向組和起始點(diǎn)（即取老方向組）當(dāng)F2＜F3當(dāng)F2≥F3令k←k+1，返回步驟⑵當(dāng)前28頁，總共46頁。⑺

確定k+1輪的方向組和起始點(diǎn)令k←k+1，返回步驟⑵當(dāng)前29頁，總共46頁。例試用鮑威爾修正算法求目標(biāo)函數(shù)的最優(yōu)解。已知初始點(diǎn)，迭代精度ε=0.001解：第一輪迭代計(jì)算沿第一坐標(biāo)方向e1進(jìn)行一維搜索α1=2當(dāng)前30頁，總共46頁。以為起點(diǎn)，改沿第二坐標(biāo)軸方向e2進(jìn)行一維搜索α2=0.5構(gòu)成新方向當(dāng)前31頁，總共46頁。沿d1方向進(jìn)行一維搜索得極小點(diǎn)與極小值計(jì)算點(diǎn)距需進(jìn)行第二輪迭代計(jì)算當(dāng)前32頁，總共46頁。第二輪迭代計(jì)算首先確定上輪中的最大函數(shù)下降量及其相應(yīng)方向映射點(diǎn)及其函數(shù)值當(dāng)前33頁，總共46頁。檢查鮑威爾條件于是可知鮑威爾條件兩式均不成立。第二輪取基本方向組和起始點(diǎn)為當(dāng)前34頁，總共46頁。沿e2方向作一維搜索得以為起點(diǎn)沿d1方向一維搜索得當(dāng)前35頁，總共46頁。構(gòu)成新生方向沿d2方向一維搜索得檢查迭代終止條件需再作第三輪迭代計(jì)算。當(dāng)前36頁，總共46頁。根據(jù)具體情況來分析，d1，d2實(shí)際上為共軛方向，見下圖。本題又是二次函數(shù)，有共軛方向的二次收斂性，上面結(jié)果就是問題的最優(yōu)解?？梢灶A(yù)料，如果做第三輪迭代，則一定各一維搜索的步長(zhǎng)為零，必有故得最優(yōu)解當(dāng)前37頁，總共46頁。在不計(jì)算導(dǎo)數(shù)的情況下，先算出若干點(diǎn)處的函數(shù)值，從它們之間的大小關(guān)系中也可以看出函數(shù)變化的大概趨勢(shì)，為尋求函數(shù)的下降方向提供依據(jù)。原理：利用單純形的頂點(diǎn)，計(jì)算其函數(shù)值并加以比較，從中確定有利的搜索方向和步長(zhǎng)，找到一個(gè)較好的點(diǎn)取代單純形中較差的點(diǎn)，組成新的單純形來代替原來的單純形。使新單純形不斷的向目標(biāo)函數(shù)的極小點(diǎn)靠近，直到搜索到極小點(diǎn)位置§4.7

單形替換法方法

當(dāng)前38頁，總共46頁。§4.7

單形替換法方法

設(shè)x5稱為x1點(diǎn)相對(duì)于x4點(diǎn)的反射點(diǎn)x4為x2點(diǎn)、x3點(diǎn)連線的中點(diǎn)取當(dāng)前39頁，總共46頁?！?.7

單形替換法方法

五種情況：1）如果構(gòu)成新的單純形x2x3x6如果構(gòu)成新的單純形x2x3x5當(dāng)前40頁，總共46頁?！?.7

單形替換法方法

五種情況：2）構(gòu)成新的單純形x2x3x5當(dāng)前41頁，總共46頁?！?.7

單形替換法方法

五種情況：3）如果構(gòu)成新的單純形x2x3x7如果構(gòu)成新的單純形x2x3x5當(dāng)前42頁，總共46頁。§4.7

單形替換法方法

五種情況：4）如果構(gòu)成新的單純形x2x3x8當(dāng)前43頁，總共46頁。§4.7