本章繼續(xù)討論無(wú)約束最優(yōu)化問(wèn)題minf(x)xRn.針對(duì)這類.由于不計(jì)算目標(biāo)函數(shù)的導(dǎo)數(shù)，因此又稱為直接方法.術(shù)人員的青睞；而其缺點(diǎn)是收斂速度比利用導(dǎo)數(shù)的方法要慢，收斂性質(zhì)不易證明等.§8.1單純形調(diào)優(yōu)法(SimplexMethod)W.Spendy,G.R.HextF.R.Himsworth(1962)提出的，后經(jīng)J.Nelden和R.Mend(1965)作出改進(jìn).nnRnn1個(gè)仿射無(wú)關(guān)向量的凸包，通俗地理解為Rn中具有n1個(gè)頂點(diǎn)的多面體，如果該多面體的各棱長(zhǎng)彼此相等，則稱為正規(guī)單純形.例如，在R2中，三角形就是單純形，正三角形就是正規(guī)單純形.Rn.x0和正數(shù)l，取xix0(

2n11)lel2

e，i1,2,,n， (8.1.1)n2 ii其中e1,1,,1)T是分量均為1ne0,0,10,0)T為第i個(gè)分量為1其i余分量均為0的n維單位向量.顯然，對(duì)每個(gè)i(1in，有i 02

l 2 l2 2 2(n11)ln2||(n11)ln2

e ei||2n[( 1)2(n11)n]l,2n1而對(duì)任意i,j(1ijn2n122||xixj||2||lele||2l2，22i j由此可知，由(8.1.1)確定的n1個(gè)點(diǎn)確實(shí)是n維正規(guī)單純形.更簡(jiǎn)單的n維單純形，即對(duì)于任意給定初始點(diǎn)x0和正數(shù)l，取ixix0le，i1,2,,n， (8.1.2)i其中ei的定義同(8.1.1).單純形調(diào)優(yōu)法的基本思想就是按（8.1.2）取特殊單純形作為初始單純形，然后每次迭代直到搜索到滿意的極小點(diǎn)為止.小棱長(zhǎng).我們?cè)谙旅娼o出具體算法.單純形調(diào)優(yōu)法）步1x0和初始步長(zhǎng)l，按（8.1.2）nx1x2,xn，置1，122，容許誤差0.2：計(jì)算f(xii12,nxhxl滿足：f(xh)maxf(xi)，f(xl)minf(xi)；0in 0in步3：計(jì)算非最大值點(diǎn)的重心x1 xi和反射點(diǎn)nihxrx(xxh，f(xrf(xl，則計(jì)算延伸點(diǎn)xex(xxh)，若f(xe)f(xlxhxexhxr6；4f(xr)maxf(xi)xhxr6；ih5f(xrf(xhxhxr，計(jì)算收縮點(diǎn)xcx(xhx)，f(xcf(xhxhxc，否則減小棱長(zhǎng)，置xixl1(xixl)，i0,1,,n，il；2

1nn1i0

f(xi)，如果nn)f]2n1

1/2

，xargminf(xi2.0in§8.2模式搜索法(PatternSearchMethod)R.HookeA.Jeeves1961年提出的，對(duì)于變量數(shù)目較少的無(wú)約束最優(yōu)化問(wèn)題，這是一種程序簡(jiǎn)單而又比較有效的方法.f(x的下降方向，后者是利用發(fā)現(xiàn)的函數(shù)變化規(guī)律循著有利方向?qū)ふ逸^好的點(diǎn)，可看成是一種加速.下面先對(duì)算法過(guò)程做一些說(shuō)明，再給出具體算法.x0x0,0x0，步長(zhǎng)收縮參數(shù)01，初始步長(zhǎng)0，也可以對(duì)不同坐標(biāo)方向給出不同步長(zhǎng)1,2,,n.探測(cè)移動(dòng)：在當(dāng)前迭代點(diǎn)xk，從xk,0出發(fā)，依次沿坐標(biāo)方向找下降點(diǎn)，首先看第i個(gè)坐f(xk,i1e)f(xk,i1xk,ixk,i1e，否則，ii iiii我們?cè)賮?lái)看看第i個(gè)坐標(biāo)反方向函數(shù)值是否下降，若f(xk,i1e)f(xk,i1iiiixk,ixk,i1exk,ixk,i1，并縮小關(guān)于第i坐標(biāo)的搜索步長(zhǎng)，即置iii12,nii模式移動(dòng)：xk,nxk，則置xk1xk,n，xk1,0xk1(xk1xk,0)，kk1，再進(jìn)行探測(cè)移動(dòng)一次.f(xk,nf(xk，則這時(shí)分兩種情況討論：如果xk,nxkxk,0xk,0xkxk,nxk，則前面的模式移動(dòng)及之后的探測(cè)移動(dòng)均失敗，這時(shí)，縮小步長(zhǎng)，置iii12,n.i終止準(zhǔn)則：如果maxi1in

xk.一個(gè)近似.因此這個(gè)方法的收斂速度較慢.8.2（模式搜索法）1 1x0x0,0x01

,,n

01，容許誤差0，置k0.2：對(duì)于i12,n，若iif(xk,i1e)f(xk,i1)ii則iixk,ixk,i1eii否則若iif(xk,i1e)f(xk,i1)ii則iixk,ixk,i1eii否則3f(xk,nf(xk)，則置

xk,ixk,i1，置ii；xk1xk,nxk1,0xk1xk1xk,0，kk12；步4xk,nxk，則置xk,0xk；i步5 若maxi1in

xk，否則置

ii，i12,n，轉(zhuǎn)2.§8.3Rosenbrok法Rosenbrok在1960年提出一種直接最優(yōu)化法.該方法在每一輪沿n個(gè)正交單位方向進(jìn)行n個(gè)正交單位方向作為下一輪搜索方向.由于該方法的特點(diǎn)是在每一輪迭代之后要進(jìn)行搜索方向的旋轉(zhuǎn)，故又稱旋轉(zhuǎn)方向法，旋轉(zhuǎn)方向的目的是為了加速收斂速度.標(biāo)函數(shù)下降時(shí)才收縮.而旋轉(zhuǎn)方向法是事先給定一個(gè)步長(zhǎng)放大因子1和步長(zhǎng)收縮因子01，沿給定的軸向搜索，無(wú)論目標(biāo)函數(shù)值是否下降，步長(zhǎng)總是要改變.y出發(fā)沿某軸向做探測(cè)移動(dòng)時(shí)，若探測(cè)成功，則下一次沿此方向探測(cè)的步長(zhǎng)增加倍，若探測(cè)失敗，則取原步長(zhǎng)的倍.由當(dāng)前迭代點(diǎn)xkxk1xk作為參考點(diǎn)y,反復(fù)地沿平行于作為軸向的n個(gè)正交單位方向d1d2,dn做變步長(zhǎng)的軸向探測(cè)移動(dòng)，直到某xk1y.為提高求解效率，Rosenbork法當(dāng)軸向探測(cè)不能繼續(xù)時(shí)，就要進(jìn)行一次各軸向的旋轉(zhuǎn)，由此得到新的n個(gè)正交單位向量作為下一輪迭代的一組軸方向.在直接方法中，我們依據(jù)直觀感覺(jué)認(rèn)為，經(jīng)過(guò)一輪探測(cè)移動(dòng)后，方向xk1xk應(yīng)該是n個(gè)正交單位向量時(shí)要把方向xk1xk放在首位.而Rosenborkxkxk1進(jìn)行的都是探測(cè)移動(dòng)，因此xk1xkdd.....d，11 22 nn注意到dd,d兩兩正交，其中xk1xk)Td，i12,n.下面給出具體算法.1 2 n i i8.3（Rosenbrok法）1 x0，初始搜索方向標(biāo)準(zhǔn)正交向量組d1

,,dn

，如取坐標(biāo)軸正方向ee,e，初始步長(zhǎng)0,0,,0，步長(zhǎng)收縮因子01，步長(zhǎng)放大因子12 n 1 2 k1，容許誤差0，置k0.2yxkzy；3：對(duì)于i12,n，若if(ykd)f(yii i iyyki否則

，置kk，i i

f(z，則

置kk；zy3；否則fyf(xk，則xk1y5，6；5：若||xk1xk||xk17；步6 若maxk，則停止迭代，輸出xk，否則置zy，轉(zhuǎn)步3.k 1in i步7 進(jìn)行軸向旋轉(zhuǎn).計(jì)算(xk1xk)Td，i1,2,,n，利用Schmidt正交化過(guò)i ij12,n，令pn

j0

pj,

j1，j d,

j

i jq,

j2 ii

j qTq iij i1 iidq||q||，k1k，置kk12.j j j j j12，步長(zhǎng)放大因子[23.Davies,SwannCampey后，得到了修正旋轉(zhuǎn)法的收斂性質(zhì).§8.4Powell法Powell方法是Powell（1964）提出來(lái)的，它是目前在無(wú)約束最優(yōu)化的直接搜索方法中Powell方法具有二次終止性.最簡(jiǎn)單最古老的直接方法是坐標(biāo)輪換法(CyclicCoordinateMethod)，它的基本思想是在kxkxk,0xk，argminf(xk,i1e)，xk,ixk,i1e，i1,2,,n，i R i iixk1xk,n..一個(gè)明顯的遺漏就是沒(méi)有考慮可能的高效率方向dxk1xk.針對(duì)這一問(wèn)題，Powell提出了如下改進(jìn)算法.8.4（原始Powell法）1x0n個(gè)線性無(wú)關(guān)的向量d1d1,d1，容許誤差0，置k1.1 2 n2xk,0xk1，對(duì)于i12,n，求解minf(xk,i1dk)，R i得最優(yōu)解xk,ixk,i1dk；i iin1步3：置dk xk,nxk,0n1minf(xk,ndk)，得最優(yōu)解

n1

Rxkxk,n

n1

n1di i1k步4：若||xkxk1||xk，否則置dk1dki12,di i1kkk12.下面討論P(yáng)owell方法的二次終止性，設(shè)f(x)1xTGxrTxc， (8.4.1)2其中Gn階對(duì)稱正定矩陣.定理84.1設(shè)x0,1Rnx01，dRn定函數(shù)(8.4.1)xi出發(fā)沿方向dzii0,1z1z0與方向d是G共軛的.證由精確線搜索可知，0f(z0TdGz0r)Td0f(z1)TdGz1r)Td，兩式相減可得(z1z0TGd0.8.4.2設(shè)d1d2

,,dk

是一組Gx0x1Rn是任意兩個(gè)點(diǎn)，且kx018.4.1，若從xi出發(fā)依次沿這kxiMzii0,1，則向量組kd1,d2

,,dk

z1z0是GMk是由d1d2,dk生成的子空間.5.1.1證明中的(5.1.3)式可知，ii i i 0f(z0TdGz0r)Td0f(z1)Td(Gz1r)Tdi12,k，對(duì)應(yīng)兩式相減可得(z1z0TGd0i1ii i i 定理84.38..1n則Powell方法至多經(jīng)過(guò)n輪迭代就可達(dá)到極小點(diǎn).n1n證根據(jù)Powell算法替換搜索方向的規(guī)律從點(diǎn)x1,n出發(fā)沿方向d1 d2n1nx1x2,0，如果d2d2d2x2,n1出發(fā)沿方向d2d1

精確線1 2 n

n n1x2,n8.4.1可知，d2x1,nx1,0與向量d2x2,nx2,0是G共n n1軛的.kdkdk,dkdk

xk,nxk,0的前n個(gè)向量線性無(wú)關(guān)，1 2 n n1nk2且后面nk2

,,dk,dk

是G共軛的.n n1在第k1xk1,0xk，搜索方向依次為dk1dk1,dk1dkn n11 2 n n1dk,dkdk1xk1,nxk1,0，如果它們前nxk1,0xk和點(diǎn)2 n1 n1xk1,nxk,nk1xk1,nk出發(fā)依次沿同一組G共軛方向dk dk1

,,dkdk1,dk

dk1nk2

nk1

n

n1 nn18.4.2dk1xk1,nxk1,0與上述Gn1G共軛.從而定理得證，即Powell方法具有二次終止性.但是，原始Powell方法有一個(gè)致命缺陷，就是在某輪迭代中所產(chǎn)生的n個(gè)搜索方向有可n至一直迭代下去也達(dá)不到極小點(diǎn).為了克服上述缺陷，Powell自己將其方法做了某些改進(jìn)，克服了原始Powell方法可能出現(xiàn)的退化情形，但改進(jìn)后的方法一般不具有二次終止性，收斂速度比原始Powell方法慢些，但仍不失為無(wú)約束最優(yōu)化問(wèn)題直接方法中最有效的方法之一.改進(jìn)的Powell方法不僅保證了新產(chǎn)生的搜索方向的線性無(wú)關(guān)性，而且盡可能讓它們趨向G共軛.為了理解這個(gè)方法的基本思想，我們下面考察一個(gè)向量組趨向共軛的判定條件.條件.設(shè)qq,q

是Rn中的n個(gè)單位向量，記Q(q q

q，則1 2

1 2qTq qTq qTq 1 qTq

n qTq11 12

n

12 1nqTq qTq

qTq 1 qTqQTQ

21 22

n

21

n. (8.4.2) qTq

q

qTq 1n1 n

nn

n1 n2 由于QTQ是半正定的，其特征值均非負(fù)，故由特征值的性質(zhì)及幾何平均數(shù)不超過(guò)算術(shù)平均數(shù)的事實(shí)，我們有

n

111n|Q|2|QTQ|

1 2 n

1，(8.4.3)12 n

n n

1，即QTQI，亦即qq,q是1 2 nRn中的n個(gè)正交單位向量.

1 2 n行列式|Q|具有如下幾何解釋：在平面R2|Q||qq|是以qq為相鄰邊的1 2 1 2q2，且|Q|接近于1對(duì)應(yīng)向量qq接近正交；在三維空間R3|Q||qqq|是以qqq為1 2 1 2 3 1 2 3q1q2q3積1，且|Q|接近于1對(duì)應(yīng)向量q1q2q3接近正交.根據(jù)上面的討論分析，對(duì)Rn中的n個(gè)非零向量qq,q

，我們以判別式det(

,

,,

1 2 nqn )

qn||2det(q1,q2,,qn)/(||q1||2||q2||2||qn||2)， (8.4.4)來(lái)衡量向量組q1q2,qn的正交程度，如果q1q2,qn含有零向量，則0.由于對(duì)稱正定矩陣G可以分解為G

TG G，故向量d1d2關(guān)于G共軛等價(jià)于向量Gd和Gd正交.Rn中的n個(gè)非零向量qq,q

，我們以判別式1 2

q1

, q2

,,

1 2 nqn )

(8.4.5)來(lái)衡量向量組q1q2,qn的共軛程度，如果q1q2,qn含有零向量，則0.顯然，在判別式(8.4.5)中總有1，且1的充分必要條件是向量組q1q2,qn是G共軛的.如果直接利用判別式(8.4.5)來(lái)判斷n1個(gè)搜索方向d1,dndn1中共軛程度最好的n.為此，我們尋找一個(gè)更為簡(jiǎn)單的判別條件，下面通過(guò)觀察平面向量來(lái)總結(jié)規(guī)律.ddR2x0dx1，1 2 12 x1出發(fā)沿dx2x0出發(fā)沿dx2x02 ..為書(shū)寫方qqq分別為ddd的在GqTGq1，i123.1 2 3 1 2 3 i i由上面迭代點(diǎn)的產(chǎn)生過(guò)程可見(jiàn)，存在,x2x0qq，也存在滿足1 2 11 22 3x2x0q，由此得q)q)q

，且有33 3 1 3 1 2 3 21,2det(G)det(q1,q2)， (8.4.6) det(G)det(q,q)det(

G)det(q,1q2q)2 ，(8.4.7)1,3 1 3

1 1 2 1,23 3 3

G)det(q,q)det(G)det(q,1q2q)1 . (8.4.8)2,3

2 3 2 1

1,23 3 3|1|,|2|和|3|的大小比較.注意到x0出發(fā)沿q精確線搜索得到的最優(yōu)步長(zhǎng)，即有1f(x0)Tq

11

0T 10 1 1

f(x)(x x)qTGq 1 1 11[f(x1)f(x0)1(x1x0)TG(x1x0)]1 21[f(x1)f(x0)12qTGq]1[f(x1)f(x0)]1，(8.4.9) 211 1 21由此解得同理可得

1 1122[f(x0)f(x1)]. (8.