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

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

應(yīng)該是一輪迭代的始點和終點，不是某搜索方向的前后迭代點。第四頁，共四十四頁，2022年，8月28日坐標(biāo)輪換法的流程圖第五頁，共四十四頁，2022年，8月28日例:用坐標(biāo)輪換法求下列目標(biāo)函數(shù)的無約束最優(yōu)解。

給定初始點，精度要求ε=0.1解：做第一輪迭代計算沿e1方向進行一維搜索式中，為第一輪的起始點，取第六頁，共四十四頁，2022年，8月28日按最優(yōu)步長原則確定最優(yōu)步長α1，即極小化此問題可由某種一維優(yōu)化方法求出α1:

以為新起點，沿e2方向一維搜索以最優(yōu)步長原則確定α2，即為極小化第七頁，共四十四頁，2022年，8月28日對于第一輪按終止條件檢驗計算5輪后，有故近似優(yōu)化解為第八頁，共四十四頁，2022年，8月28日§4.5

坐標(biāo)輪換法

3.方法評價：

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

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

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

鮑威爾方法

第十頁，共四十四頁，2022年，8月28日一、共軛方向的生成§4.6

鮑威爾方法

為兩個極小點根據(jù)梯度與等值面之間關(guān)系可知第十一頁，共四十四頁，2022年，8月28日一、共軛方向的生成§4.6

鮑威爾方法

對于二次函數(shù)，兩點處的梯度可表示為代入到公式：第十二頁，共四十四頁，2022年，8月28日一、共軛方向的生成§4.6

鮑威爾方法

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

鮑威爾基本算法的搜索過程（二維）第十四頁，共四十四頁，2022年，8月28日二、鮑威爾基本算法

鮑威爾基本算法的搜索過程（三維）第十五頁，共四十四頁，2022年，8月28日

鮑威爾基本算法的步驟：

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

e3

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

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

d2k

,

d3k,……dnk

,

dk第十六頁，共四十四頁，2022年，8月28日

鮑威爾基本算法的缺陷：

可能在某一輪迭代中出現(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ù)極小值，計算將失敗。

第十七頁，共四十四頁，2022年，8月28日鮑威爾基本算法的退化x1x2x31=02e23e3S1如圖所示為一個三維優(yōu)化問題的示例，設(shè)第一輪中1=0

，則新生方向與e2、e3共面，隨后的各環(huán)方向組中，各矢量必在該平面內(nèi)，使搜索局限于二維空間，不能得到最優(yōu)解。e2e3S1第十八頁，共四十四頁，2022年，8月28日三、鮑威爾修正算法

在某輪已經(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ù)下降值第十九頁，共四十四頁，2022年，8月28日鮑威爾算法的方向淘汰(F3)(F2)(F1)反射點函數(shù)最大下降量△m始點終點第二十頁，共四十四頁，2022年，8月28日為了構(gòu)造第k+1輪基本方向組，采用如下判別式：

按照以下兩種情況處理：

1)

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

???、

dnk。k+1輪的初始點取

x0k+1=xnkF2<F3

x0k+1=xn+1kF2F3

第二十一頁，共四十四頁，2022年，8月28日2）兩式均不成立，則淘汰函數(shù)值下降最大的方向，并用第k輪的新生方向補入k+1輪基本方向組的最后，即k+1輪的方向組為d1k、d2k

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

dk

。(F3)(F2)(F1)反射點始點終點函數(shù)最大下降量△m第二十二頁，共四十四頁，2022年，8月28日k+1輪的初始點取:

x0k+1=xk

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

(F3)(F2)(F1)反射點函數(shù)下降量△始點終點dk方向極小點第二十三頁，共四十四頁，2022年，8月28日四、修正算法的迭代步驟及流程圖Powell算法的步驟如下：⑴

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

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

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

確定k+1輪的基本方向組和起始點（即取老方向組）當(dāng)F2＜F3當(dāng)F2≥F3令k←k+1，返回步驟⑵第二十七頁，共四十四頁，2022年，8月28日⑺

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

單形替換法方法

第三十七頁，共四十四頁，2022年，8月28日§4.7

單形替換法方法

設(shè)x5稱為x1點相對于x4點的反射點x4為x2點、x3點連線的中點取第三十八頁，共四十四頁，2022年，8月28日§4.7

單形替換法方法

五種情況：1）如果構(gòu)成新的單純形x2x3x6如果構(gòu)成新的單純形x2x3x5第三十九頁，共四十四頁，2022年，8月28日§4.7

單形替換法方法

五種情況：2）構(gòu)成新的單純形x2x3x5第四十頁，共四十四頁，2022