無約束最優(yōu)化方法無約束最優(yōu)化方法無約束最優(yōu)化方法求解無約束最優(yōu)化問題minf(x)的數(shù)值迭代解法。構(gòu)成約束最優(yōu)化方法的基礎(chǔ)解法。無約束最優(yōu)化方法求解無約束最優(yōu)化問題minf(x)的數(shù)求解無約束最優(yōu)化問題的下降迭代解法具有統(tǒng)一的迭代格式，其基本問題是選擇搜索方向和在這些搜索方向上進(jìn)行一維搜索。由于構(gòu)成搜索方向的方式可以不同，從而形成了各種不同的無約束最優(yōu)化方法。求解無約束最優(yōu)化問題的下降迭代解法具有統(tǒng)一的迭代格式，其基本無約束優(yōu)化的直接搜索法

各種無約束優(yōu)化方法的區(qū)別就在于確定其搜索方向S(k)的方法不同，所以搜索方向的構(gòu)成問題是無約束優(yōu)化方法的關(guān)鍵。根據(jù)構(gòu)造搜索方向所使用的信息性質(zhì)的不同，無約束優(yōu)化方法可以分為兩類：

X(k+1)=X(k)+(k)

S(k)(k=0,1,2,…)

一類是只利用目標(biāo)函數(shù)值信息的無約束優(yōu)化方法，如坐標(biāo)輪換法、鮑威爾法，稱為直接搜索法；另一類是利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)信息的無約束優(yōu)化方法，如梯度法、牛頓法、共軛梯度法、變尺度法，稱為間接搜索法。無約束優(yōu)化的直接搜索法各種無約束優(yōu)化方法的區(qū)別

基本思想

坐標(biāo)輪換法（變量輪換法、交替法、降維法）

將n維無約束優(yōu)化問題轉(zhuǎn)化為n個沿坐標(biāo)軸方向ei(i=1,2,…,n)的一維優(yōu)化問題來求解，并記完成n次一維搜索為一輪。若一輪搜索后未得到滿足精度要求的最優(yōu)點，則繼續(xù)下一輪迭代搜索。如此反復(fù)，直至得到滿足精度要求的最優(yōu)點為止。在每一輪搜索中，每次迭代僅對n元函數(shù)的一個變量沿其坐標(biāo)軸方向進(jìn)行一維搜索，其余n-1個變量均保持不變，再依次輪換進(jìn)行一維搜索的坐標(biāo)軸，直至完成沿n個坐標(biāo)軸方向的n次一維搜索?；舅枷胱鴺?biāo)輪換法（變量輪換法、交替法、降維法）x1x2X0(1)X1(1)X2(1)

取初始點X(0)=X0(1)，x1坐標(biāo)軸方向的單位向量S1(1)=e1=[10]T，x2坐標(biāo)軸方向的單位向量S2(1)=e2=[01]T。

X1(1)=X0(1)+α1(1)S1(1)，X2(1)=X1(1)+α2(1)S2(1)x1x2X0(1)X1(1)X2(1)取初始點

判斷是否滿足迭代收斂準(zhǔn)則：||X2(1)–X0(1)||≤？

X1(1)=X0(1)+α1(1)e1(1)

=[x1(0)

x2(0)]T+α1(1)[10]T

X2(1)=X1(1)+α2(1)e2(1)=[x1(1)

x2(1)]T+α2(1)[01]T第一輪迭代搜索：

若滿足，則輸出最優(yōu)解，否則，繼續(xù)下一輪迭代搜索。判斷是否滿足迭代收斂準(zhǔn)則：

Xi(k)=Xi-1(k)+αi(k)ei(k)(k—迭代輪次，i—k輪迭代的第i次一維搜索

αi(k)—一維搜索求得的最優(yōu)步長）||Xn(k)–X0(k)||≤？

計算步驟與算法框圖1）任選初始點X(0)=X0(1)

=[x1(0)

x2(0)…

xn(0)

]T

，給定迭代收斂精度，i=1，k=1。

2）置n個坐標(biāo)軸方向向量為單位向量，即e1=[10…0

]T，e2=[010…0

]T

，…

，en=[0…0

1]T。Xi(k)=Xi-1(k)+αi(k)ei(k)||3）按如下迭代計算公式進(jìn)行迭代計算

Xi(k)=Xi-1(k)+αi(k)ei(k)(k—迭代輪次，i—k輪迭代的第i次一維搜索

i=1，2，…，n）4）判斷是否滿足迭代收斂準(zhǔn)則||Xn(k)–X0(k)||≤？若滿足，則輸出最優(yōu)解:X

*=Xn(k)，f

*=f(X

*)否則，令X0(k+1)=Xn(k)，kk+1，返回3）。3）按如下迭代計算公式進(jìn)行迭代計算Xi(k)=X單純形替換法

基本思想

通過計算出若干點處的函數(shù)值，對其大小進(jìn)行比較，可以看出函數(shù)值變化的大致趨勢，從而可以尋求使函數(shù)值下降的搜索方向。在n維空間中，由n+1個不同點順序相連，就可以構(gòu)成一個具有n+1個頂點的多面體——稱之為單純形。計算函數(shù)在這n+1個頂點的函數(shù)值，并進(jìn)行比較，據(jù)此來確定有利的搜索方向和步長，找到一個比較好的點來取代單純形中較差的那個頂點，從而組成了一個新的單純形，并用之取代原來的單純形。如此下去，新單純形不斷地向目標(biāo)函數(shù)的極小點靠近，直到搜索到極小點為止。單純形替換法基本思想通過計算出若

計算步驟

1）構(gòu)造初始單純形選初始點X0，和步長h。從X0出發(fā)沿各坐標(biāo)軸方向分別走步長h，得到n個頂點Xi(i=1,2,…,n)，與X0構(gòu)成初始單純形。X0x2x1X1X2計算步驟1）構(gòu)造初始單純形X0x2x1X12）計算各頂點的函數(shù)值

fi=f(Xi)(i=0,1,2,…,n)3）比較函數(shù)值大小，確定最好點XL

、最差點XH和次差點XG，即:

fL=f(XL)=min{fi:

i=0,1,2,…,n}

fH=f(XH)=max{fi:

i=0,1,2,…,n}fG=f(XG)=max{fi:

i=0,1,2,…,n;i≠H}4）檢驗是否滿足迭代收斂條件|(fH

–

fL)/fL|≤

?2）計算各頂點的函數(shù)值3）比較函數(shù)值大

若滿足，則結(jié)束迭代計算，并輸出

X

*=XL

和f

*=

fL

否則，轉(zhuǎn)下一步。5）計算除XH點外的各點的“重心”Xn+1，即Xn+1=(∑Xi

–XH)/n

計算反射點：Xn+2=2Xn+1–XH和

fn+2=f(Xn+2)

當(dāng)fL≤fn+2<fG

時，以Xn+2代替XH，fn+2

代替fH

，構(gòu)造新的單純形，然后返回到3）。若滿足，則結(jié)束迭代計算，并輸出否則，轉(zhuǎn)下一步。X0x2x1X1X2XHXLXGXn+1Xn+26）擴(kuò)張：當(dāng)fn+2<fL時，取擴(kuò)張點Xn+3，即Xn+3=Xn+1+(Xn+2

–Xn+1)(=1.2～2.0)并計算fn+3=f(Xn+3)。若fn+3<fn+2，則以Xn+3代替XH，fn+3代替fH

，構(gòu)造一個新的單純形；否則，以Xn+2代替XH，fn+2

代替fH，構(gòu)造新的單純形；然后返回到3）。Xn+3X0x2x1X1X2XHXLXGXn+1Xn+26）擴(kuò)7）收縮：當(dāng)fn+2≥fG時，則需收縮。若fn+2<fH，則取收縮點Xn+4：

Xn+4=Xn+1+(Xn+2

–Xn+1)（

=0.5）

fn+4=f(Xn+4)

否則，以XH代替上式中的Xn+2，計算收斂點Xn+4：Xn+4=Xn+1+(XH

–Xn+1)fn+4=f(Xn+4)7）收縮：當(dāng)fn+2≥fG時，則需收縮。X0x2x1X1X2XHXLXGXn+1Xn+2Xn+3

若fn+4<fH，則以Xn+4代替XH，fn+4代替fH

，形成新的單純形，然后返回到3）；否則轉(zhuǎn)下一步8）。Xn+4Xn+4X0x2x1X1X2XHXLXGXn+1Xn+2Xn+38）縮邊：將單純形向XL縮邊，可以將各向量

(Xi

–XL)(i=0,1,2,…,n)的長度都縮小一半，即

Xi=XL+0.5

(Xi

–XL)=0.5

(Xi

+XL)(i=0,1,2,…,n)形成新的單純形，然后返回到2）。8）縮邊：將單純形向XL縮邊，可以將各向量鮑威爾（Powell）法

基本思想

它是直接利用函數(shù)值來構(gòu)造共軛搜索方向的一種共軛搜索方向法，又稱鮑威爾共軛方向法或方向加速法。由于對于n維正定二次函數(shù)，共軛搜索方向具有n次收斂的特性，所以鮑威爾法是直接搜索法中十分有效的一種算法，一般認(rèn)為對于維數(shù)n≤20的目標(biāo)函數(shù)它是成功的。鮑威爾法是在研究具有正定對稱矩陣H的二次函數(shù)的極小化問題時形成的，其基本思想是在不用函數(shù)導(dǎo)數(shù)信息的前提下，在迭代過程中逐次構(gòu)造關(guān)于H的共軛方向。鮑威爾（Powell）法基本思想

共軛方向的生成

設(shè)是X(k)和X(k+1)為從不同點出發(fā)，沿同一方向進(jìn)行一維搜索而得到的兩個極小點。S(j)S(j)S(k)X(k)X(k+1)▽f(X(k))▽f(X(k+1))[S(j)]T▽f(X(k))=0[S(j)]T▽f(X(k+1))=0共軛方向的生成設(shè)是X(k)和

具有正定對稱矩陣H的二次函數(shù)

f(X)=0.5XTH

X

+BT

X+C

在X(k)和X(k+1)兩點處的梯度可以表示為▽f(X(k))=H

X(k)

+B（1）▽f(X(k+1))=H

X(k+1）

+B（2）（2）－（1）得▽f(X(k+1))－▽f(X(k))=H

(

X(k+1)

－X(k))（3）（3）式兩邊同時左乘[S(j)]T得[S(j)]T[▽f(X(k+1))－▽f(X(k))]=[S(j)]TH

(X(k+1)－X(k))=0具有正定對稱矩陣H的二次函數(shù)▽f(X(k)即[S(j)]TH

(X(k+1)－X(k))=0若取S(k)=X(k+1)－X(k)

那么，S(k)和S(j)關(guān)于H共軛，即

[S(j)]TH

S(k)=0

這說明：

沿S(j)方向分別對函數(shù)做兩次一維搜索，得到兩個極小點X(k)和X(k+1)，該兩點的連線方向S(k)與S(j)是關(guān)于H共軛的方向。即[S(j)]TH(XX(k)x1x2X

*S(j)X(k+1)S(k)X(k)x1x2X*S(j)X(k+1)S(k)

上述生成共軛方向的方法完全可以推廣到n維優(yōu)化問題中，即在n維空間中，按上述方法可以生成n個相互共軛的搜索方向。

鮑威爾法的基本原理和迭代過程1）采用坐標(biāo)輪換法順次沿n個坐標(biāo)軸方向進(jìn)行一維搜索，然后以初始點X(0)和終點Xn(1)構(gòu)成一個新的方向S(1)

，并以此方向為搜索方向再作一維搜索得到極小點Xn+1(1)。2）取始點X0(2)=Xn+1(1)，并去掉原搜索方向組中的第一個方向S1(1)=e1，而將第一輪構(gòu)成的新搜索方向S(1)作為最末一個方向，以此組成第二輪迭代的n個方向。上述生成共軛方向的方法完全可以推廣到n維優(yōu)化

依此進(jìn)行下去，直到獲得滿足迭代收斂精度要求的近似極小點為止。根據(jù)這一原理構(gòu)造的迭代算法稱為鮑威爾基本算法。X1

(1)X

*S1(1)X0

(1)S2(1)S(1)x1x2X2

(1)X3

(1)X1

(2)X2

(2)S(2)依此進(jìn)行下去，直到獲得滿足迭代收斂精度要求的近似極小點為止

鮑威爾基本算法的缺點

鮑威爾基本算法僅具有理論意義，不要說對于一般的函數(shù)，就是對于二次函數(shù)，它也可能失效。因為在迭代過程中的n個搜索方向有時會變成線性相關(guān)，而不能形成共軛方向，從而張不成n維空間，導(dǎo)致隨后的迭代搜索在降維（“退化”）的空間中進(jìn)行，可能求不到極小點，故需進(jìn)行改進(jìn)。

那么，為什么會產(chǎn)生這種情況呢？又該如何去改進(jìn)呢？鮑威爾基本算法的缺點鮑威爾基本算法僅

鮑威爾條件及鮑威爾修正算法

鮑威爾基本算法中，每一輪迭代都是用連接始點和終點所產(chǎn)生的新搜索方向去機械地替換原方向組中的第一個搜索方向，而不做任何的“好壞”判斷，這正是產(chǎn)生向量線性相關(guān)而發(fā)生“退化”的根本原因所在。為了避免這種“退化”現(xiàn)象的發(fā)生，鮑威爾對這一基本算法進(jìn)行了修正。即在每一輪產(chǎn)生新的搜索方向S(k)后，首先判斷原搜索方向組是否可以直接用作下一輪迭代的搜索方向組，若可以，則仍用之，否則，還要進(jìn)一步判斷原搜索方向組中哪個方向上函數(shù)值下降量最大或貢獻(xiàn)最大，然后再用新搜索方向替換這個貢獻(xiàn)最大的搜索方向，以保證逐次生成共軛方向，即每一輪迭代的搜索方向組線性無關(guān)。鮑威爾條件及鮑威爾修正算法鮑威爾基本

對第k輪迭代，記f

1=f(X0(k))f

2=f(Xn(k))f

3=f(2Xn(k)-X0(k))

及△m(k)=max{f(Xi-1(k))-f(Xi(k)),i=1,2,…,n}，并記Sm(k)為與△m(k)相對應(yīng)的搜索方向，

S(k)=Xn(k)-X0(k)

對第k輪迭代，記

鮑威爾條件：

若f

3<f

1,且(f1-2f2+f3)(f1-f2-△m(k))2<0.5△m(k)(f1-f3)2同時成立，則用S(k)替代Sm(k)

；否則，仍用原搜索方向組。這就是鮑威爾修正算法，通常所說的鮑威爾算法就是指這一修正算法。

鮑威爾算法的計算步驟及算法框圖1）任選初始點X(0)=X0(1)

，給定迭代收斂精度1,2

。取初始基本方向組為單位坐標(biāo)向量系，即Si(1)=ei(i=1,2,…,n),并置迭代輪次k=1。鮑威爾條件：若f3<2）從X0(k)出發(fā)，依次沿Si(k)(i=1,2,…,n)作一維搜索，得n個極小點Xi(k)(i=1,2,…,n),構(gòu)造新的搜索方向S(k)=Xn(k)-X0(k)，并沿此方向進(jìn)行一維搜索得極小點Xn+1(k)

。3）判斷迭代終止條件||Xn+1(k)–X0(k)||≤1

？或|f(Xn+1(k))

–f(X0(k))|≤2

|f(Xn+1(k))

|

？若滿足，則終止迭代并輸出最優(yōu)解：

X

*=Xn+1(k)

和f

*=

f(X

*)否則，則繼續(xù)下面的迭代計算。2）從X0(k)出發(fā)，依次沿Si(k)(i=14）計算f(Xi(k))(i=1,2,…,n)，并求△m(k)=max{f(Xi-1(k))-f(Xi(k)),i=1,2,…,n}=fm-1-fm及與之對應(yīng)的兩個點Xm-1(k)和Xm(k)(1≤m≤n),則第k輪迭代中貢獻(xiàn)最大的方向為

Sm(k)=Xm(k)–Xm-1(k)5）確定映射點X(k)=2Xn(k)–X0(k)，并計算f(X

(k))

，記f1=f(X0(k)),f2=f(Xn(k))及f3=f(X(k))檢驗鮑威爾條件，若滿足，則轉(zhuǎn)下一步，否則轉(zhuǎn)第7）步。4）計算f(Xi(k))(i=1,6）置第k+1輪迭代的出發(fā)點和搜索方向組

X0(k+1)=Xn+1(k)Si(k+1)(i=1,2,…,n)

即{S1(k),…,Sm-1(k),S(k),Sm+1(k),…,Sn(k)}并置kk+1，返回第2）步。7）置第k+1輪迭代的出發(fā)點和搜索方向組若f2

<

f3

，X0(k+1)=Xn(k)；否則，X0(k+1)=X(k)。

Si(k+1)=Si(k)(i=1,2,…,n)

并置kk+1，返回第2）步。6）置第k+1輪迭代的出發(fā)點和搜索方向組7）置第

無約束最優(yōu)化方法無約束最優(yōu)化方法無約束最優(yōu)化方法求解無約束最優(yōu)化問題minf(x)的數(shù)值迭代解法。構(gòu)成約束最優(yōu)化方法的基礎(chǔ)解法。無約束最優(yōu)化方法求解無約束最優(yōu)化問題minf(x)的數(shù)求解無約束最優(yōu)化問題的下降迭代解法具有統(tǒng)一的迭代格式，其基本問題是選擇搜索方向和在這些搜索方向上進(jìn)行一維搜索。由于構(gòu)成搜索方向的方式可以不同，從而形成了各種不同的無約束最優(yōu)化方法。求解無約束最優(yōu)化問題的下降迭代解法具有統(tǒng)一的迭代格式，其基本無約束優(yōu)化的直接搜索法

各種無約束優(yōu)化方法的區(qū)別就在于確定其搜索方向S(k)的方法不同，所以搜索方向的構(gòu)成問題是無約束優(yōu)化方法的關(guān)鍵。根據(jù)構(gòu)造搜索方向所使用的信息性質(zhì)的不同，無約束優(yōu)化方法可以分為兩類：

X(k+1)=X(k)+(k)

S(k)(k=0,1,2,…)

一類是只利用目標(biāo)函數(shù)值信息的無約束優(yōu)化方法，如坐標(biāo)輪換法、鮑威爾法，稱為直接搜索法；另一類是利用目標(biāo)函數(shù)的一階或二階導(dǎo)數(shù)信息的無約束優(yōu)化方法，如梯度法、牛頓法、共軛梯度法、變尺度法，稱為間接搜索法。無約束優(yōu)化的直接搜索法各種無約束優(yōu)化方法的區(qū)別

基本思想

坐標(biāo)輪換法（變量輪換法、交替法、降維法）

將n維無約束優(yōu)化問題轉(zhuǎn)化為n個沿坐標(biāo)軸方向ei(i=1,2,…,n)的一維優(yōu)化問題來求解，并記完成n次一維搜索為一輪。若一輪搜索后未得到滿足精度要求的最優(yōu)點，則繼續(xù)下一輪迭代搜索。如此反復(fù)，直至得到滿足精度要求的最優(yōu)點為止。在每一輪搜索中，每次迭代僅對n元函數(shù)的一個變量沿其坐標(biāo)軸方向進(jìn)行一維搜索，其余n-1個變量均保持不變，再依次輪換進(jìn)行一維搜索的坐標(biāo)軸，直至完成沿n個坐標(biāo)軸方向的n次一維搜索?；舅枷胱鴺?biāo)輪換法（變量輪換法、交替法、降維法）x1x2X0(1)X1(1)X2(1)

取初始點X(0)=X0(1)，x1坐標(biāo)軸方向的單位向量S1(1)=e1=[10]T，x2坐標(biāo)軸方向的單位向量S2(1)=e2=[01]T。

X1(1)=X0(1)+α1(1)S1(1)，X2(1)=X1(1)+α2(1)S2(1)x1x2X0(1)X1(1)X2(1)取初始點

判斷是否滿足迭代收斂準(zhǔn)則：||X2(1)–X0(1)||≤？

X1(1)=X0(1)+α1(1)e1(1)

=[x1(0)

x2(0)]T+α1(1)[10]T

X2(1)=X1(1)+α2(1)e2(1)=[x1(1)

x2(1)]T+α2(1)[01]T第一輪迭代搜索：

若滿足，則輸出最優(yōu)解，否則，繼續(xù)下一輪迭代搜索。判斷是否滿足迭代收斂準(zhǔn)則：

Xi(k)=Xi-1(k)+αi(k)ei(k)(k—迭代輪次，i—k輪迭代的第i次一維搜索

αi(k)—一維搜索求得的最優(yōu)步長）||Xn(k)–X0(k)||≤？

計算步驟與算法框圖1）任選初始點X(0)=X0(1)

=[x1(0)

x2(0)…

xn(0)

]T

，給定迭代收斂精度，i=1，k=1。

2）置n個坐標(biāo)軸方向向量為單位向量，即e1=[10…0

]T，e2=[010…0

]T

，…

，en=[0…0

1]T。Xi(k)=Xi-1(k)+αi(k)ei(k)||3）按如下迭代計算公式進(jìn)行迭代計算

Xi(k)=Xi-1(k)+αi(k)ei(k)(k—迭代輪次，i—k輪迭代的第i次一維搜索

i=1，2，…，n）4）判斷是否滿足迭代收斂準(zhǔn)則||Xn(k)–X0(k)||≤？若滿足，則輸出最優(yōu)解:X

*=Xn(k)，f

*=f(X

*)否則，令X0(k+1)=Xn(k)，kk+1，返回3）。3）按如下迭代計算公式進(jìn)行迭代計算Xi(k)=X單純形替換法

基本思想

通過計算出若干點處的函數(shù)值，對其大小進(jìn)行比較，可以看出函數(shù)值變化的大致趨勢，從而可以尋求使函數(shù)值下降的搜索方向。在n維空間中，由n+1個不同點順序相連，就可以構(gòu)成一個具有n+1個頂點的多面體——稱之為單純形。計算函數(shù)在這n+1個頂點的函數(shù)值，并進(jìn)行比較，據(jù)此來確定有利的搜索方向和步長，找到一個比較好的點來取代單純形中較差的那個頂點，從而組成了一個新的單純形，并用之取代原來的單純形。如此下去，新單純形不斷地向目標(biāo)函數(shù)的極小點靠近，直到搜索到極小點為止。單純形替換法基本思想通過計算出若

計算步驟

1）構(gòu)造初始單純形選初始點X0，和步長h。從X0出發(fā)沿各坐標(biāo)軸方向分別走步長h，得到n個頂點Xi(i=1,2,…,n)，與X0構(gòu)成初始單純形。X0x2x1X1X2計算步驟1）構(gòu)造初始單純形X0x2x1X12）計算各頂點的函數(shù)值

fi=f(Xi)(i=0,1,2,…,n)3）比較函數(shù)值大小，確定最好點XL

、最差點XH和次差點XG，即:

fL=f(XL)=min{fi:

i=0,1,2,…,n}

fH=f(XH)=max{fi:

i=0,1,2,…,n}fG=f(XG)=max{fi:

i=0,1,2,…,n;i≠H}4）檢驗是否滿足迭代收斂條件|(fH

–

fL)/fL|≤

?2）計算各頂點的函數(shù)值3）比較函數(shù)值大

若滿足，則結(jié)束迭代計算，并輸出

X

*=XL

和f

*=

fL

否則，轉(zhuǎn)下一步。5）計算除XH點外的各點的“重心”Xn+1，即Xn+1=(∑Xi

–XH)/n

計算反射點：Xn+2=2Xn+1–XH和

fn+2=f(Xn+2)

當(dāng)fL≤fn+2<fG

時，以Xn+2代替XH，fn+2

代替fH

，構(gòu)造新的單純形，然后返回到3）。若滿足，則結(jié)束迭代計算，并輸出否則，轉(zhuǎn)下一步。X0x2x1X1X2XHXLXGXn+1Xn+26）擴(kuò)張：當(dāng)fn+2<fL時，取擴(kuò)張點Xn+3，即Xn+3=Xn+1+(Xn+2

–Xn+1)(=1.2～2.0)并計算fn+3=f(Xn+3)。若fn+3<fn+2，則以Xn+3代替XH，fn+3代替fH

，構(gòu)造一個新的單純形；否則，以Xn+2代替XH，fn+2

代替fH，構(gòu)造新的單純形；然后返回到3）。Xn+3X0x2x1X1X2XHXLXGXn+1Xn+26）擴(kuò)7）收縮：當(dāng)fn+2≥fG時，則需收縮。若fn+2<fH，則取收縮點Xn+4：

Xn+4=Xn+1+(Xn+2

–Xn+1)（

=0.5）

fn+4=f(Xn+4)

否則，以XH代替上式中的Xn+2，計算收斂點Xn+4：Xn+4=Xn+1+(XH

–Xn+1)fn+4=f(Xn+4)7）收縮：當(dāng)fn+2≥fG時，則需收縮。X0x2x1X1X2XHXLXGXn+1Xn+2Xn+3

若fn+4<fH，則以Xn+4代替XH，fn+4代替fH

，形成新的單純形，然后返回到3）；否則轉(zhuǎn)下一步8）。Xn+4Xn+4X0x2x1X1X2XHXLXGXn+1Xn+2Xn+38）縮邊：將單純形向XL縮邊，可以將各向量

(Xi

–XL)(i=0,1,2,…,n)的長度都縮小一半，即

Xi=XL+0.5

(Xi

–XL)=0.5

(Xi

+XL)(i=0,1,2,…,n)形成新的單純形，然后返回到2）。8）縮邊：將單純形向XL縮邊，可以將各向量鮑威爾（Powell）法

基本思想

它是直接利用函數(shù)值來構(gòu)造共軛搜索方向的一種共軛搜索方向法，又稱鮑威爾共軛方向法或方向加速法。由于對于n維正定二次函數(shù)，共軛搜索方向具有n次收斂的特性，所以鮑威爾法是直接搜索法中十分有效的一種算法，一般認(rèn)為對于維數(shù)n≤20的目標(biāo)函數(shù)它是成功的。鮑威爾法是在研究具有正定對稱矩陣H的二次函數(shù)的極小化問題時形成的，其基本思想是在不用函數(shù)導(dǎo)數(shù)信息的前提下，在迭代過程中逐次構(gòu)造關(guān)于H的共軛方向。鮑威爾（Powell）法基本思想

共軛方向的生成

設(shè)是X(k)和X(k+1)為從不同點出發(fā)，沿同一方向進(jìn)行一維搜索而得到的兩個極小點。S(j)S(j)S(k)X(k)X(k+1)▽f(X(k))▽f(X(k+1))[S(j)]T▽f(X(k))=0[S(j)]T▽f(X(k+1))=0共軛方向的生成設(shè)是X(k)和

具有正定對稱矩陣H的二次函數(shù)

f(X)=0.5XTH

X

+BT

X+C

在X(k)和X(k+1)兩點處的梯度可以表示為▽f(X(k))=H

X(k)

+B（1）▽f(X(k+1))=H

X(k+1）

+B（2）（2）－（1）得▽f(X(k+1))－▽f(X(k))=H

(

X(k+1)

－X(k))（3）（3）式兩邊同時左乘[S(j)]T得[S(j)]T[▽f(X(k+1))－▽f(X(k))]=[S(j)]TH

(X(k+1)－X(k))=0具有正定對稱矩陣H的二次函數(shù)▽f(X(k)即[S(j)]TH

(X(k+1)－X(k))=0若取S(k)=X(k+1)－X(k)

那么，S(k)和S(j)關(guān)于H共軛，即

[S(j)]TH

S(k)=0

這說明：

沿S(j)方向分別對函數(shù)做兩次一維搜索，得到兩個極小點X(k)和X(k+1)，該兩點的連線方向S(k)與S(j)是關(guān)于H共軛的方向。即[S(j)]TH(XX(k)x1x2X

*S(j)X(k+1)S(k)X(k)x1x2X*S(j)X(k+1)S(k)

上述生成共軛方向的方法完全可以推廣到n維優(yōu)化問題中，即在n維空間中，按上述方法可以生成n個相互共軛的搜索方向。

鮑威爾法的基本原理和迭代過程1）采用坐標(biāo)輪換法順次沿n個坐標(biāo)軸方向進(jìn)行一維搜索，然后以初始點X(0)和終點Xn(1)構(gòu)成一個新的方向S(1)

，并以此方向為搜索方向再作一維搜索得到極小點Xn+1(1)。2）取始點X0(2)=Xn+1(1)，并去掉原搜索方向組中的第一個方向S1(1)=e1，而將第一輪構(gòu)成的新搜索方向S(1)作為最末一個方向，以此組成第二輪迭代的n個方向。上述生成共軛方向的方法完全可以推廣到n維優(yōu)化

依此進(jìn)行下去，直到獲得滿足迭代收斂精度要求的近似極小點為止。根據(jù)這一原理構(gòu)造的迭代算法稱為鮑威爾基本算法。X1

(1)X

*S1(1)X0

(1)S2(1)S(1)x1x2X2

(1)X3

(1)X1

(2)X2

(2)S(2)依此進(jìn)行下去，直到獲得滿足迭代收斂精度要求的近似極小點為止

鮑威爾基本算法的缺點

鮑威爾基本算法僅具有理論意義，不要說對于一般的函數(shù)，就是對于二次函數(shù)，它也可能失效。因為在迭代過程中的n個搜索方向有時會變成線性相關(guān)，而不能形成共軛方向，從而張不成n維空間，導(dǎo)致隨后的迭代搜索在降維（“退化”）的空間中進(jìn)行，可能求不到極小點，故需進(jìn)行改進(jìn)。

那么，為什么會產(chǎn)生這種情況呢？又該如何去改進(jìn)呢？鮑威爾基本算法的缺點鮑威爾基本算法僅

鮑威爾條件及鮑威爾修正算法

鮑威爾基本算法中，每一輪迭代都是用連接始點和終點所產(chǎn)生的新搜索方向去機械地替換原方向組中的第一個搜索方向，而不做任何的“好壞”判斷，這正是產(chǎn)生向量線性相關(guān)而發(fā)生“退化”的根本原因所在。為了避免這種“退化”現(xiàn)象的發(fā)生，鮑威爾對這一基本算法進(jìn)行了修正。即在每一輪產(chǎn)生新的搜索方向S(k)后，首先判斷原搜索方向組是否可以直接用作下一輪迭代的搜索方向組，若可以，則仍用之，否則，還要進(jìn)一步判斷原搜索方向組中哪個方向上函數(shù)值下降量最大或貢獻(xiàn)最大，然后再用新搜索方向替換這個貢獻(xiàn)最大的搜索方向，以保證逐次生成共軛方向，即每一輪迭代的搜索方向組線性無關(guān)。鮑威爾條件及鮑威爾修正算法鮑威爾基本

對第k輪迭代，記f

1=f(X0(k))f

2=f(Xn(k))f

3=f(2Xn(k)-X0(k))

及△m(k)=max{f(Xi-1(k))-f(Xi(k)),i=1,2,…,n}，并記Sm(k)為與△m(k)相對應(yīng)的搜索方向，

S(k)=Xn(k)-X0(k)