第四章 2011修改--無(wú)約束最優(yōu)化的直接方法

1、min( )nxRfx1 單純形單純形：Rn中的單純形指具有n+1個(gè)頂點(diǎn)的多面體，若各棱長(zhǎng)彼此相等，則稱為正規(guī)單純形。如：在R2中，三角形就是單純形，正三角形就是正規(guī)單純形。（正三角形是R2中周長(zhǎng)一定包圍面積最大的布點(diǎn)方式） 結(jié)論： 對(duì)于任意給定初始點(diǎn)z1和正數(shù)l，按如下公式取定的單純形是一個(gè)以為z 1頂點(diǎn)棱長(zhǎng)為l的Rn中的正規(guī)單純形：v 1= z 1 , v i = z1+z(i) i=2,3,4n+1其中n 維向量z(i)=q q,pi-1,q qT如:z(2)=p,q qT.z(n+1)=q,q pT.其中(11)2(1 1)2lpnnnlqnn 22ijvvlij，21 ivv 222

2、22111 1ivvzz izz ipnq221 ivvl 22222222 ( ) 11ijvvz iz jz iz jz i z jz i z jllpq pqnqpq pqnq 1,101nhiiivnv00()01rhvvvv為反射系數(shù),常取zhviv0v brvlvlvev0vvzivhv a00()chvvvvhi 21)(orocvvvvivhvrvlv divhvrvlv eivhvrvlv c1,1, 2, 312liivvvil in!1*111,11niiniivnvfnfeffnii211222121654,minxxxxf0128 , 9,1 0 , 1 1,8 ,

3、1 1TTTxxx2018,102Tihixxx0122101200m a x1 2 5,m i n4 5,hlffffxxffffxx4344, 8,8Txxrxxfx43fxfx1434,8,13Txxfx0 ,12220 ,121 ,1ma x ,6 5,mi n ,8llffffxxffffxx0120128 , 9,4 , 8,8 , 1 14 5 ,8 ,6 5TTTxxxfff336,9,13Thxxxxfx313fx013343416 , 8 .524 , 6,42 , 3 .5,8TThTlxxxxxxxfxxxrxxfxfn 這個(gè)方法由兩類移動(dòng)所構(gòu)成，一類是這個(gè)方法由兩類移

4、動(dòng)所構(gòu)成，一類是探測(cè)性移動(dòng)探測(cè)性移動(dòng)，另一類是，另一類是模模式性移動(dòng)式性移動(dòng)；前者為了揭示函數(shù)變化規(guī)律，探測(cè)函數(shù)；前者為了揭示函數(shù)變化規(guī)律，探測(cè)函數(shù)f (x)下降方向，下降方向，后者是利用發(fā)現(xiàn)的函數(shù)變化規(guī)律循著有利方向（也可看作近似梯度后者是利用發(fā)現(xiàn)的函數(shù)變化規(guī)律循著有利方向（也可看作近似梯度方向）尋找較好的點(diǎn)，可看成一種加速。下面先對(duì)算法過(guò)程做一些方向）尋找較好的點(diǎn)，可看成一種加速。下面先對(duì)算法過(guò)程做一些說(shuō)明，再給出算法過(guò)程。說(shuō)明，再給出算法過(guò)程。n 給定初始點(diǎn)給定初始點(diǎn) x0 和步長(zhǎng)和步長(zhǎng) （也可對(duì)不同坐標(biāo)方向給出不同步（也可對(duì)不同坐標(biāo)方向給出不同步長(zhǎng)長(zhǎng): ，以向量，以向量 =( ) i=

5、 1,2,3 ,n 描述步長(zhǎng)）描述步長(zhǎng)）n 探測(cè)性移動(dòng)探測(cè)性移動(dòng)：從迭代點(diǎn)出發(fā)，依次沿坐標(biāo)方向找下降點(diǎn)，為標(biāo)：從迭代點(diǎn)出發(fā)，依次沿坐標(biāo)方向找下降點(diǎn)，為標(biāo)出點(diǎn)與坐標(biāo)方向之間的關(guān)系，采用記號(hào)出點(diǎn)與坐標(biāo)方向之間的關(guān)系，采用記號(hào) 表示第表示第 k 次迭代按坐次迭代按坐標(biāo)方向標(biāo)方向 ei 在探測(cè)性移動(dòng)時(shí)得到的點(diǎn)。在探測(cè)性移動(dòng)時(shí)得到的點(diǎn)。iiik ,110,1 ,ekkkk0,1,0kkff,1,011kke0,1,kkff,1,01 1kke,1,011kke0,1 ,kkff, 0kk,k i,1,1k ik iiik ik iieff若不 變,1,1,()()01k ik ik ik iiifff若

6、,1,1,-()()k ik iiik ik ik iiefff若不 變,1,0kkff,1,0kk11（如各分量減半）重新開(kāi)始探測(cè)性移動(dòng)。若 充分小，則終止。 上式對(duì)上式對(duì)i=1，2，n 進(jìn)行。求出進(jìn)行。求出 若此若此 則完成了探則完成了探測(cè)性移動(dòng)，再開(kāi)始模式移動(dòng)。若測(cè)性移動(dòng)，再開(kāi)始模式移動(dòng)。若 則再進(jìn)行探測(cè)性移動(dòng)。再則再進(jìn)行探測(cè)性移動(dòng)。再進(jìn)行探測(cè)性移動(dòng)時(shí)，若步長(zhǎng)進(jìn)行探測(cè)性移動(dòng)時(shí)，若步長(zhǎng) ： 時(shí)，則認(rèn)為時(shí)，則認(rèn)為 即為近似極即為近似極小小值點(diǎn)（這是因?yàn)橹迭c(diǎn)（這是因?yàn)?而而 時(shí)，必將有時(shí)，必將有 很小很小接近于接近于0）nk,0 .,knk0 .,knk0 . k0 .,knk)(kf1111

7、1111( ),( )kkkkkkkkif yfyiif yf若則令一次迭代完成。若則令并將步長(zhǎng) 縮小 下面再看模式移動(dòng)（Pattern Move）記 從 出發(fā)，沿方向 以步長(zhǎng) 求出新的試驗(yàn)點(diǎn) 即 然后再?gòu)?出發(fā)進(jìn)行一次探測(cè)性移動(dòng)，得到點(diǎn) 這時(shí)有：1kl0 .,1knkkkkkP11112(1)kkkkkkkl Pl1+k1k1ky1+k模式移動(dòng)方向可以看作梯度方向的一個(gè)近似，因而本方法也可以看作是最速下降的一個(gè)近似。因此這個(gè)方法的收斂速度較慢。特別是在最優(yōu)點(diǎn)附近，但當(dāng)變量個(gè)數(shù)較少時(shí)，此方法可能是有用的。此方法也可以與其它方法結(jié)合使用，以便在最優(yōu)化過(guò)程開(kāi)始階段找到一個(gè)較好的初始點(diǎn)。)()(11

8、kkfyfi0kk1k21kk1k11kky1k)()(11kkfyfii1ky1k12kk1k0,kk( ),fza 二算 法 過(guò) 程 ：已 知 目 標(biāo) 函 數(shù)步 長(zhǎng) 向 量個(gè)nTn. 1.0 .),.,(2112,.neee不 同 方 向 ， 不 妨 取 為控 制 誤 差,:0 .10kz。選定初始點(diǎn)ikkzziaa,00:,:0 .1.2 .2探測(cè)位移。1,.1.1.0:)()()( :),()()( .:).()(.3.2ikikikzzzfzfzfzzzfzfzfzzzfzf，則若則若則若0.11.11.2 .2 . :.-: ,:k iiik iiik izez zezzz0000

9、3,2.2,.5.2:1.4.2轉(zhuǎn)，若則返回若niniii0,111102,:1).()(.6轉(zhuǎn)則若kkzDzfDfkkkk。轉(zhuǎn)。否則轉(zhuǎn)則若00,0,1,0,04,5:.3knkknkknkzzzzzz。轉(zhuǎn)則則終止，否則最優(yōu)解若0,*01.2.:,|.|.4aaazzank01015 .2-:.2.kkkzzzzD從出 發(fā) 再 做 探 測(cè) 移 動(dòng) 。即 類 似 于步 ， 得 出0,11111.2:,:1:).()(轉(zhuǎn)則若kkzzzfDfkkkk2112221212-4-2),(minxxxxxxxf+=例：求解：00 , 0100()( (1 , 1 )(1 , 0 ) )( 2 , 1 )6

10、(,)(1 , 1 )3zfzefffzf從出發(fā)做探測(cè)性移動(dòng)：由于21,1)1 ,0(,)0,1(,)1 ,1(21210=TTTeez取解：0 ,10 ,120 ,10 ,120110 ,20 ,1110(2 ,1).()(2 , 2 )4()(2 ,1)6 .()(2 , 0 )4(, )(2 ,1),()6 .TTzfzeffzffzeffzzzzfzzz 故但故 ，以 上 完 成 一 次 探 測(cè) 性 移 動(dòng) ， 因可 開(kāi) 始 模 式 移 動(dòng) 。110111221122 (2 ,1)(1,1)(3,1),:()(),TTTkzzzzeeeefzfz令再 從出 發(fā) 做 探 測(cè) 性 移 動(dòng)

11、。由 于 沿探 測(cè) 得 到 點(diǎn) 的 函 數(shù) 值 均大 于則 :1111111111,21,01(3,1) ,()()7()(3,1) , ()1,(3,1) ,(3,1)1(1,1)(0.5, 0.5) .2TTTTTTDzfDfzfzzDzkzzzza 而故 令與 前 面 算 法 描 述 有 點(diǎn) 不 同令從開(kāi) 始 第 二 次 迭 代 。首 先 進(jìn) 行 探 測(cè) 性 移 動(dòng) ， 求 得仍 然 為。 因 而 將 步 長(zhǎng) 縮 小 一 半 進(jìn) 行 探 測(cè) ， 即令 ：這 樣 有。再進(jìn)行模式移動(dòng)，取5 . 7-)()5 . 1 , 3(.) 1 , 3()5 . 1 , 3(220, 12, 1zfzz

12、zTTT1,21,02222122(3,1.5)(3,1) .(3,1.5)()7.523 2()7,10.5TTTTzzzf zzzzf zz 取，。再進(jìn)行模式移動(dòng)，（ ，）。再?gòu)某霭l(fā)做探測(cè)性移動(dòng)。（取的結(jié)果如下，若，則多做一步)2222232(4, 2) ,()-8()-7()()(4, 2)TTDfDfzfDfzzz得 到 : 。 從 而 得 新 迭 代 點(diǎn) :，開(kāi)始迭代，則總有若再?gòu)模?032,33zzzz*(4,2) .Tz 可以不斷縮小步長(zhǎng)，因此最優(yōu)解為)(az)(bz1x2x*zz（0）)1(z1x2x1x2xP0P0p1*z)(bz)(az)(oz)1(z （2） P0. Pm

13、-1 是互為Q共軛的向量系，mn. （3）z 1 ,z 2是任意的兩個(gè)不同點(diǎn)，則若分別從z 1 ,z 2 出發(fā)依次沿方向P。 作直線搜索，最后得到直線搜索的極小點(diǎn)分別設(shè)為 設(shè)P= ，那么P 與 是互為Q 的共軛的.定理一： 若（1）二次函數(shù)f(z)= 中的Q對(duì)稱正定。121CZbQZzTT11.mPP11.mPP*2*1,zz*2*1zz 這就是說(shuō)，由 z (0) 出發(fā)，依次沿方向P0, P1 求極小，便得到最優(yōu)點(diǎn)。而我們?cè)诮榻B共軛梯度法及共軛方向時(shí)，也具有這一性質(zhì)?？梢宰C明此種P0 P1方向是共軛方向。 對(duì)于n維情形。我們?cè)诘谌乱呀?jīng)證明過(guò)有下邊結(jié)論：下面我們看一個(gè)具體例子：例:f( ) 解

14、：取 沿方向 求極小得點(diǎn)在從 出發(fā)沿方向 求極小，得點(diǎn)又從 出發(fā)沿方向 求極小，得點(diǎn) 于是那么此方向應(yīng)與 P0 是共軛的。事實(shí)上也是這樣，因?yàn)椋?1,xx2122212xxxx(22Tz 。， ）Tp），（。10Taz) 1 , 2()()(aZ1(1,0)Tp 1(0.25,1)Tz 1z0(0,1)Tp Tbz)125. 0 ,25. 0()(pzzab)875. 0,75. 1()()(2114Q可見(jiàn)從不同起點(diǎn)沿同一方向進(jìn)行直線搜索可以產(chǎn)生共軛方向。Powell方向正是基于這一思想而產(chǎn)生的。他的辦法是沿著n個(gè)坐標(biāo)方向依次求極小值，這樣經(jīng)過(guò)n次以后所得到的n個(gè)新方向就是相互共軛的。這是po

15、well方法的原始方案，過(guò)程如下： 已知目標(biāo)函數(shù)f(z).給定z0,.21neee. . . 1,:,:01njpekjj。0410( 1.75, 0.85)0121Tp Qp 故,020:,:kkj zz。11,1,3+=jjjkjkptzz。中其)(min)(1,11,jjkjjjktpzfptzfjj : 14。1, 0, 07:, (11 ):jjknknknkppjnxxpxx。若則 最優(yōu)解 ,0k nkzznkzz,*終止否則轉(zhuǎn)。7。6。5若轉(zhuǎn)若. nj nj。6轉(zhuǎn)30kk:1轉(zhuǎn)2沿 作直線搜索npnnnnkskpppppppzlz.,:.,),(21110,1 但是，原始但是，原

16、始 powell 方法有一個(gè)主要的缺點(diǎn)，即這樣更換方法有一個(gè)主要的缺點(diǎn)，即這樣更換方向所產(chǎn)生的方向所產(chǎn)生的n個(gè)向量有時(shí)可能是近似線性相關(guān)的，從而使個(gè)向量有時(shí)可能是近似線性相關(guān)的，從而使其真的極小點(diǎn)可能被漏掉。為克服這些缺點(diǎn)，其真的極小點(diǎn)可能被漏掉。為克服這些缺點(diǎn)，powell自己自己將其方法做了某些改進(jìn)，但改進(jìn)后的方法一般不是二次終將其方法做了某些改進(jìn)，但改進(jìn)后的方法一般不是二次終結(jié)的了，即對(duì)于結(jié)的了，即對(duì)于n元二次函數(shù)元二次函數(shù)f(z)求極小點(diǎn)，即使求極小點(diǎn)，即使n次迭代也次迭代也不一定能找到極小點(diǎn)。但修正的不一定能找到極小點(diǎn)。但修正的powell方法能克服出現(xiàn)退方法能克服出現(xiàn)退化的情形，盡

17、管收斂速度比原始的化的情形，盡管收斂速度比原始的Powell方法慢些，但仍方法慢些，但仍不失為無(wú)約束極小值直接優(yōu)化方法中最有效的一個(gè)不失為無(wú)約束極小值直接優(yōu)化方法中最有效的一個(gè)。其過(guò)程如下：其過(guò)程如下：已知已知f(z),取及取及n個(gè)初始搜索方向，不防取個(gè)初始搜索方向，不防取給定控制誤差，較大的正數(shù)給定控制誤差，較大的正數(shù)M。Zneee.2110 :,:,1ojjk epjn0,20:,-:,k jj zM 11,1,3+=jjjkjkoptzzo4: )()(,)()(1,1,jkjkjkjkzfzfzfzf)(min)(1,11,jjkjjjktpzfptzf其中Jj:1否則J,不變，轉(zhuǎn) 5

18、jjo :15o6若轉(zhuǎn)7； 若轉(zhuǎn)3。nj nj o7若則最優(yōu)解否則轉(zhuǎn)8oknkzz,nkzz,*)-2 (),(),(8,3,2,1oknknkokozzffzffzffo11,:1,:1,kkzzknk轉(zhuǎn)2。o10若轉(zhuǎn)11否則轉(zhuǎn)12231221321)(21)(2(fffffffo9若轉(zhuǎn)11 ，若則轉(zhuǎn)10,13ff 3ffo12令,:1,:),11( ,:)(min)(.,1,*,*,1,kkpppnjpptpzfptzfptzzzzpnjjnknknkkoknk轉(zhuǎn)2解：取 初始方向 第一輪Tz) 1 , 1 (0TTpp) 1 , 0(,) 1, 1 (211221 ,02,010,01

19、,00,00:,)0 , 1 (),()1 , 1 (),(:PPPZLZPZLZZZTSTS2221)(minxxzf例：用原始powell方法求解無(wú)約束問(wèn)題：再沿加速方向 進(jìn)行直線搜索，即Toozzp) 1, 0(2,2222,01)(minttpzf則 則完成一輪迭代0*tTzptzz) 0 , 1 (2 , 02*2 , 01TSTSPZLZZPZLZZZ)0 , 1 (),()0 , 1 (),(:21 , 12, 1110, 11 , 10, 11TTopp) 1,(,) 1 , 0(21（線形相關(guān)）第二輪，有兩個(gè)搜索方向 這樣原始powell法導(dǎo)出任一第k輪迭代點(diǎn)z始終停留在非最

20、優(yōu)點(diǎn) 處而原向量最優(yōu)點(diǎn)為可見(jiàn)原始powell方法失效。Toz), 1 (1Tz)0 , 0(* 修正的目的在于保證 線性無(wú)關(guān)。關(guān)于其證明過(guò)程從略，參見(jiàn) computer Journal, vol.7. p154162.1964nppp.21 由迭代過(guò)程可以看出：在某些時(shí)候一組n個(gè)方向不變，因此當(dāng)n很大時(shí)，powell修正方案接近于輪換坐標(biāo)法。因而收斂速度慢，根據(jù)經(jīng)驗(yàn)，powell方法適應(yīng)的范圍大體上可限制在問(wèn)題中的變量在20個(gè)以下，當(dāng)然，計(jì)算機(jī)速度快時(shí)，問(wèn)題維數(shù)也可以提高。例：給定初始點(diǎn) 則211222121242),(minxxxxxxxfTz) 1 , 1 (03)(0zf因 因此5 .

21、0)()(, 4)()(2 , 01 , 01 , 00 , 0zfzfzfzf4, 1j5 . 7)(,)5 . 1 , 3(212,21 , 02, 0oTzfpzz故21,0)(,7-2-2)1 , 3()()1 , 3(7-)(,)4, 3(2,221 ,02,01 ,010,01 ,0ttFtttftFttpzzzfpzzTT故2,0)(,34)1 ,1()()1 ,1()1 , 1(,)1 ,0(,)0, 1(,210,01 ,000,021ttFtttftFttpZZZZppTTTT取故令 并從 出發(fā)沿方向P求極小，得 完成一次迭代。而且下一次迭代的兩個(gè)搜索方向?yàn)椋?Tzzp)

22、5 . 0 , 2 (0 , 02 , 09.7)(,)517,519(11zfzT2, 0z7)(, 5 . 7)(3)(, 7)(,) 5 . 0 , 2 (232 , 020 , 010 , 02 , 0zffzffzffzfzzzT又32)(2125. 1)(2221221321fffffff,13ff 因 且TZZ)517,519(10 , 1取12(0,1) ,(2,0.5)TTpp016.0)()(,08.0)()(2, 11 , 11 , 10, 1zfzfzfzfTzzzj)5024,25103(208.0,10,12,1又故TTTppzfzfffffzf)5.0,2(.)1

23、 ,0(996.7)(,)5097,2599(,3,996.7,9.7,3)(212213321搜索方向仍為：故令因996.7)(.)5097,2599(98.7)(.)1019,519(,2,12,11,1)1,1(21zfzzfzppTT求極小得：分別沿向量，于是仍按更換搜索方向進(jìn)行方法。在第二次迭代時(shí)若我們不用修正值為而此時(shí)近似解為極小值為易見(jiàn)原向題的極小點(diǎn)為powellzzTT99984.7)988.1 ,992.3(8,)2 , 4(*Tzzp)256,254(0 , 12, 1=此時(shí)已得極小點(diǎn)。），（求極小，即為點(diǎn)出發(fā)沿則從Tpz242,1是共軛的。）關(guān)于（注意2111)6,4(,

24、)5.0,2(21QppT99984.7)(.)250497,250998(9992.7)(.)5099,2599(996.7)(.)5097,2599(,2,22,21,21,20,20,221zfzzfzzfzppTTT求極小得依次沿 Rosenbrock在1960年提出一種直接最優(yōu)化法。此法的每一輪迭代采用變步長(zhǎng)的軸向移動(dòng)。然后再利用軸向的旋轉(zhuǎn)來(lái)產(chǎn)生一組新的方向作為下一輪迭代的軸向。由于方法特點(diǎn)是在每一輪迭代之后要進(jìn)行軸向的旋轉(zhuǎn)，故而叫作旋轉(zhuǎn)方向法旋轉(zhuǎn)方向法，旋轉(zhuǎn)方向的目的是為了加速收斂速度。 前面Hook-Jeeves 模式搜索法中，軸向移動(dòng)的步長(zhǎng)在一定階段保持不變，只在適當(dāng)條件時(shí)才做

25、縮減。 但在Rosenbrock法中，軸向移動(dòng)的步長(zhǎng)在探測(cè)過(guò)程中獨(dú)立地隨時(shí)變化。即探測(cè)成功增加步長(zhǎng)，失敗則減小步長(zhǎng)，具體做法是：4.4 Rosenbrock法 （旋轉(zhuǎn)方向法）1kzkzkznddd.211kz 事先給定一個(gè)步長(zhǎng)增大系數(shù) 和步長(zhǎng)縮減系數(shù) 若從一個(gè)參考點(diǎn)出發(fā)沿平行與某軸向作探測(cè)成功時(shí)則下一次沿此方向探測(cè)的步長(zhǎng)增加 倍，若失敗，則取原步長(zhǎng)的 倍。10111 12 2.kkn nzzddd由于第k輪迭代中沿平行于每一軸向的各方向都移動(dòng)過(guò)，因而 令njj1, 011122222.nnnnnnnddddddddd利用 gram-smith 正交化方法得方向組標(biāo)準(zhǔn)正交化為新的 作為下一輪迭代軸向。其算法過(guò)程為：nddd,.,21nddd,.,2111 取初點(diǎn) ，標(biāo)準(zhǔn)正交化向量組 初始