第六節(jié)-無約束優(yōu)化方法鮑威爾

§4.5坐標輪換法一.坐標輪換法：1.基本思想：每次搜索只允許一個變量變化，其余變量保持不變，即沿坐標方向輪流進行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量（其余變量視為常量）的優(yōu)化問題，因此又稱這種方法為變量輪換法。此種方法只需目標函數(shù)的數(shù)值信息而不需要目標函數(shù)的導數(shù)。目前一頁\總數(shù)四十三頁\編于七點計算步驟:⑴任選初始點,確定搜索方向第一輪的起點，置n個坐標軸方向矢量為單位坐標矢量§4.5坐標輪換法目前二頁\總數(shù)四十三頁\編于七點⑵迭代計算k為迭代輪數(shù)的序號，取k=1，2，……；i為該輪中一維搜索的序號，取i=1，2，……n步長α一般通過一維優(yōu)化方法求出其最優(yōu)步長。⑶判斷是否中止迭代如滿足，迭代中止，并輸出最優(yōu)解最優(yōu)解否則，令k←k+1返回步驟（2）§4.5坐標輪換法

應該是一輪迭代的始點和終點，不是某搜索方向的前后迭代點。目前三頁\總數(shù)四十三頁\編于七點坐標輪換法的流程圖目前四頁\總數(shù)四十三頁\編于七點例:用坐標輪換法求下列目標函數(shù)的無約束最優(yōu)解。

給定初始點，精度要求ε=0.1解：做第一輪迭代計算沿e1方向進行一維搜索式中，為第一輪的起始點，取目前五頁\總數(shù)四十三頁\編于七點按最優(yōu)步長原則確定最優(yōu)步長α1，即極小化此問題可由某種一維優(yōu)化方法求出α1:

以為新起點，沿e2方向一維搜索以最優(yōu)步長原則確定α2，即為極小化目前六頁\總數(shù)四十三頁\編于七點對于第一輪按終止條件檢驗計算5輪后，有故近似優(yōu)化解為目前七頁\總數(shù)四十三頁\編于七點§4.5

坐標輪換法

3.方法評價：

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

受目標函數(shù)的性態(tài)影響很大。如圖a)所示，二次就收斂到極值點；如圖b)所示，多次迭代后逼近極值點；如圖c)所示，目標函數(shù)等值線出現(xiàn)山脊（或稱陡谷），若搜索到A點，再沿兩個坐標軸以±t0步長測試，目標函數(shù)值均上升，計算機判斷A點為最優(yōu)點。事實上發(fā)生錯誤。目前八頁\總數(shù)四十三頁\編于七點

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

鮑威爾方法

目前九頁\總數(shù)四十三頁\編于七點一、共軛方向的生成§4.6

鮑威爾方法

為兩個極小點根據(jù)梯度與等值面之間關(guān)系可知目前十頁\總數(shù)四十三頁\編于七點一、共軛方向的生成§4.6

鮑威爾方法

對于二次函數(shù)，兩點處的梯度可表示為代入到公式：目前十一頁\總數(shù)四十三頁\編于七點一、共軛方向的生成§4.6

鮑威爾方法

結(jié)論：從不同的點出發(fā)沿某一方向分別對函數(shù)作兩次一維搜索，得到兩個極小點，那么這兩個極小點的連線方向與該方向?qū)共軛目前十二頁\總數(shù)四十三頁\編于七點二、鮑威爾基本算法

鮑威爾基本算法的搜索過程（二維）目前十三頁\總數(shù)四十三頁\編于七點二、鮑威爾基本算法

鮑威爾基本算法的搜索過程（三維）目前十四頁\總數(shù)四十三頁\編于七點

鮑威爾基本算法的步驟：

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

e3

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

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

d2k

,

d3k,……dnk

,

dk目前十五頁\總數(shù)四十三頁\編于七點

鮑威爾基本算法的缺陷：

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

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

式中，d1k、d2k、

???、

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

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

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

d3k

、???、

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

目前十六頁\總數(shù)四十三頁\編于七點鮑威爾基本算法的退化x1x2x31=02e23e3S1如圖所示為一個三維優(yōu)化問題的示例，設第一輪中1=0

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

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

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

為初始點，搜索方向為d1k、d2k

、

???、

dnk，產(chǎn)生的新方向為dk

，此方向的極小點為xk。沿dk方向移動得到點

xn+1k=2xnk-x0k

，稱之為x0k對xnk的映射點。

計算x0k

、

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

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

F1=F(x0k)

F2=F(xnk)

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

是第k輪方向組中，依次沿各方向搜索函數(shù)下降值目前十八頁\總數(shù)四十三頁\編于七點鮑威爾算法的方向淘汰(F3)(F2)(F1)反射點函數(shù)最大下降量△m始點終點目前十九頁\總數(shù)四十三頁\編于七點為了構(gòu)造第k+1輪基本方向組，采用如下判別式：

按照以下兩種情況處理：

1)

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

???、

dnk。k+1輪的初始點取

x0k+1=xnkF2<F3

x0k+1=xn+1kF2F3

目前二十頁\總數(shù)四十三頁\編于七點2）兩式均不成立，則淘汰函數(shù)值下降最大的方向，并用第k輪的新生方向補入k+1輪基本方向組的最后，即k+1輪的方向組為d1k、d2k

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

dk

。(F3)(F2)(F1)反射點始點終點函數(shù)最大下降量△m目前二十一頁\總數(shù)四十三頁\編于七點k+1輪的初始點取:

x0k+1=xk

xk是第k輪沿dk方向搜索的極小點。

(F3)(F2)(F1)反射點函數(shù)下降量△始點終點dk方向極小點目前二十二頁\總數(shù)四十三頁\編于七點四、修正算法的迭代步驟及流程圖Powell算法的步驟如下：⑴

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

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

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

確定k+1輪的基本方向組和起始點（即取老方向組）當F2＜F3當F2≥F3令k←k+1，返回步驟⑵目前二十六頁\總數(shù)四十三頁\編于七點⑺

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

單形替換法方法

目前三十六頁\總數(shù)四十三頁\編于七點§4.7

單形替換法方法

設x5稱為x1點相對于x4點的反射點x4為x2點、x3點連線的中點取目前三十七頁\總數(shù)四十三頁\編于七點§4.7

單形替換法方法

五種情況：1）如果構(gòu)成新的單純形x2x3x6如果構(gòu)成新的單純形x2x3x5目前三十八頁\總數(shù)四十三頁\編于七點§4.7

單形替換法方法

五種情況：2）構(gòu)成新的單純形x2x3x5目前三十九頁\總數(shù)四十三頁\編于七點§4.7

單形替換法方法

五種情況：3）如果構(gòu)成新的單純形x2x3x7如果構(gòu)成新的單純形x2x3x5目前四十頁\總數(shù)四十三頁\編于七點§4.7

單形替換法方法

五種情況：4）如果構(gòu)成新的單純形x2x3x8目前四十一頁\總數(shù)四十三頁\編于七點§4.7

單形替換法方法

五種情況：5），構(gòu)成新的單純形x3x9x11

目前四十二頁\總數(shù)四十三頁\編于七點無約束優(yōu)化問題的評價準則