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

第六節(jié)無約束優(yōu)化方法鮑威爾第一頁，共四十四頁，編輯于2023年，星期一§4.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ù)。第二頁，共四十四頁，編輯于2023年，星期一計(jì)算步驟:⑴任選初始點(diǎn),確定搜索方向第一輪的起點(diǎn)，置n個(gè)坐標(biāo)軸方向矢量為單位坐標(biāo)矢量§4.5坐標(biāo)輪換法第三頁，共四十四頁，編輯于2023年，星期一⑵迭代計(jì)算k為迭代輪數(shù)的序號(hào)，取k=1，2，……；i為該輪中一維搜索的序號(hào)，取i=1，2，……n步長α一般通過一維優(yōu)化方法求出其最優(yōu)步長。⑶判斷是否中止迭代如滿足，迭代中止，并輸出最優(yōu)解最優(yōu)解否則，令k←k+1返回步驟（2）§4.5坐標(biāo)輪換法

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

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

以為新起點(diǎn)，沿e2方向一維搜索以最優(yōu)步長原則確定α2，即為極小化第七頁，共四十四頁，編輯于2023年，星期一對于第一輪按終止條件檢驗(yàn)計(jì)算5輪后，有故近似優(yōu)化解為第八頁，共四十四頁，編輯于2023年，星期一§4.5

坐標(biāo)輪換法

3.方法評價(jià)：

方法簡單，容易實(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步長測試，目標(biāo)函數(shù)值均上升，計(jì)算機(jī)判斷A點(diǎn)為最優(yōu)點(diǎn)。事實(shí)上發(fā)生錯(cuò)誤。第九頁，共四十四頁，編輯于2023年，星期一

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

鮑威爾方法

第十頁，共四十四頁，編輯于2023年，星期一一、共軛方向的生成§4.6

鮑威爾方法

為兩個(gè)極小點(diǎn)根據(jù)梯度與等值面之間關(guān)系可知第十一頁，共四十四頁，編輯于2023年，星期一一、共軛方向的生成§4.6

鮑威爾方法

對于二次函數(shù)，兩點(diǎn)處的梯度可表示為代入到公式：第十二頁，共四十四頁，編輯于2023年，星期一一、共軛方向的生成§4.6

鮑威爾方法

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

鮑威爾基本算法的搜索過程（二維）第十四頁，共四十四頁，編輯于2023年，星期一二、鮑威爾基本算法

鮑威爾基本算法的搜索過程（三維）第十五頁，共四十四頁，編輯于2023年，星期一

鮑威爾基本算法的步驟：

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

e3

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

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

d2k

,

d3k,……dnk

,

dk第十六頁，共四十四頁，編輯于2023年，星期一

鮑威爾基本算法的缺陷：

可能在某一輪迭代中出現(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的線性組合，以后的各次搜索將在降維的空間進(jìn)行，無法得到n維空間的函數(shù)極小值，計(jì)算將失敗。

第十七頁，共四十四頁，編輯于2023年，星期一鮑威爾基本算法的退化x1x2x31=02e23e3S1如圖所示為一個(gè)三維優(yōu)化問題的示例，設(shè)第一輪中1=0

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

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

按照以下兩種情況處理：

1)

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

???、

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

x0k+1=xnkF2<F3

x0k+1=xn+1kF2F3

第二十一頁，共四十四頁，編輯于2023年，星期一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第二十二頁，共四十四頁，編輯于2023年，星期一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)第二十三頁，共四十四頁，編輯于2023年，星期一四、修正算法的迭代步驟及流程圖Powell算法的步驟如下：⑴

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

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

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

確定k+1輪的基本方向組和起始點(diǎn)（即取老方向組）當(dāng)F2＜F3當(dāng)F2≥F3令k←k+1，返回步驟⑵第二十七頁，共四十四頁，編輯于2023年，星期一⑺

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

單形替換法方法

第三十七頁，共四十四頁，編輯于2023年，星期一§4.7

單形替換法方法

設(shè)x5稱為x1點(diǎn)相對于x4點(diǎn)的反射點(diǎn)x4為x2點(diǎn)、x3點(diǎn)連線的中點(diǎn)取第三十八頁，共四十四頁，編輯于2023年，星期一§4.7

單形替換法方法

五種情況：1）如果構(gòu)成新的單純形x2x3x6如果構(gòu)成新的單純形x2x3x5第三十九頁，共四十四頁，編輯于2023年，星期一§4.7

單形替換法方法

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