8無(wú)約束最優(yōu)化的直接法

1、第八章無(wú)約束最優(yōu)化的直接法本章主要內(nèi)容：坐標(biāo)輪換法及其收斂性模式搜索法及其收斂性旋轉(zhuǎn)方向法、Powell 法。教學(xué)目的及要求：掌握坐標(biāo)輪換法并理解其收斂性，掌握模式搜索法并理解其收 斂性；了解旋轉(zhuǎn)方向法、Powell法。教學(xué)重點(diǎn)：Powell法.教學(xué)難點(diǎn)：Powell法.教學(xué)方法：?jiǎn)l(fā)式.教學(xué)手段：多媒體演示、演講與板書(shū)相結(jié)合.教學(xué)時(shí)間：6學(xué)時(shí).教學(xué)內(nèi)容：§8.1坐標(biāo)輪換法考慮無(wú)約束最優(yōu)化問(wèn)題(8.1.1)min f (x),其中 x Rn, f ： R算法8-1 （坐標(biāo)輪換法）Step1選取初始數(shù)據(jù).選取初始點(diǎn)Xg，給定允許誤差Step2進(jìn)行一維搜索.從xk 1出發(fā)，沿坐標(biāo)軸方向e

2、k0M1進(jìn)行一維搜索,M0求k1和Xk，使得f (Xk 1k g) min f (Xk 1Xkxk 1 k 1d Step3 檢查迭代次數(shù).若k n，轉(zhuǎn)Step4;否則，令k : k 1，返回Step2.Step4檢查是否滿足終止準(zhǔn)則.若| xn xo，迭代終止，得Xn為問(wèn)題（8.1.1）的近似最優(yōu)解；否則，令x0: xn,k: 1，返回Step2.定理8.1.2設(shè)f : RnR具有一階連續(xù)偏導(dǎo)數(shù)，xo Rn，記f(X。)，且水平集S(f,)有界若Xk是用坐標(biāo)輪換法求解問(wèn)題(8.1.1)產(chǎn)生的點(diǎn)列，且在每次一維搜索中所得到的最優(yōu)解都是唯一的，則(1) 當(dāng)Xk為有窮點(diǎn)列時(shí)，其最后一個(gè)點(diǎn)是f的平穩(wěn)

3、點(diǎn)；f的平(2) 當(dāng)xk為無(wú)窮點(diǎn)列時(shí)，它必有極限點(diǎn)，并且其任一極限點(diǎn)都是 穩(wěn)點(diǎn).例1用坐標(biāo)輪換法求解問(wèn)題(8.1.3)2 2min f (x) Xix2 3x1 x1x2，其中x (X1,X2)T .取初始點(diǎn)x(0)(0,0) T，允許誤差0.1 .解從點(diǎn)x(0)出發(fā)沿©進(jìn)行一維搜索x(0)ei0，將2 2X1,X2 0代入 f (x) X1X2 3X1X1X2中，易得0 »(，) x(0)0e(| ,0)T ；從點(diǎn)x出發(fā)沿e2進(jìn)行一維搜索，得13,x(2)X 4X(2) X(0)(3 3)T .(2,4)；再?gòu)狞c(diǎn)x(2)出發(fā)沿e1進(jìn)行一維搜索，得(15 3)tM)；從點(diǎn)x

4、出發(fā)沿e2進(jìn)行一維搜索，得3 3，XX3e24x x(2).J5 %(亍材；再?gòu)狞c(diǎn)x出發(fā)沿e1進(jìn)行一維搜索，得3(5)432,x x 金Q3 15、t(32 韋)；從點(diǎn)X出發(fā)沿e2進(jìn)行一維搜索，得3(6)(5)5,X X64x(6)x5e (-63,-63)t ；32 64再?gòu)狞c(diǎn)x(6)出發(fā)沿e進(jìn)行一維搜索,3(7)(6)6 128，x x6ei(255 63)t ；(128,64)；從點(diǎn)x出發(fā)沿e2進(jìn)行一維搜索，得7 為 x(8)x(7)x(8)x(6)7e2255 255t() ；12856'迭代終止，得問(wèn)題(8.1.3)的近似最優(yōu)解為(8),255 255 tx (,) 128

5、256其實(shí)問(wèn)題(8.1.3)的最優(yōu)解為(2,1)t .§ .2模式搜索法算法8-2 (模式搜索法)Step1選取初始數(shù)據(jù)選取初始點(diǎn)X。，初始步長(zhǎng)° 0,給定收縮因子(0,1)，給定允許誤差0,令k 0 .Step2確定參考點(diǎn).令y Xk, j 1 .Step3 進(jìn)行正軸向探測(cè).從點(diǎn)y出發(fā)，沿ej作正軸向探測(cè)：若f(ykej)f(y)，令 y:yk，轉(zhuǎn) Step5；否則，轉(zhuǎn) Step4.Step4 進(jìn)行負(fù)軸向探測(cè).從點(diǎn)y出發(fā)，沿ej作負(fù)軸向探測(cè)：若f(ykej)f(y)，令 y:yk，轉(zhuǎn) Step5；否則，轉(zhuǎn) Step5.Step5檢驗(yàn)探測(cè)次數(shù).若j n，令j : j 1，返

6、回Step3;否貝U，令xk 1 轉(zhuǎn) Step6.Step6進(jìn)行模式移動(dòng).若f區(qū)i)f (xj,從點(diǎn)Xki出發(fā)沿加速方向Xki Xk作模式移動(dòng)，令 y 2Xki Xk, ki k,k ： k 1, j 1，返回 Step3;否貝U,轉(zhuǎn) Step7.Step7檢查是否滿足終止準(zhǔn)則.若k，迭代終止，得問(wèn)題(8.1.1 )的近似最優(yōu)解為Xk;否則，轉(zhuǎn)Step8.Step8縮短步長(zhǎng).若Xk 1 Xk，令k 1 k,k: k 1，返回Step2;否則， 令Xk 1 Xk, k 1 k, k: k 1，返回 Step2.定理8.2.1設(shè)f ：RnR是具有一階連續(xù)偏導(dǎo)數(shù)的凸函數(shù)，Xo Rn，記f(Xo)，并

7、且水平集S(f,)有界.若Xk為由模式搜索法求解問(wèn)題(8.1.1) 產(chǎn)生的點(diǎn)列，貝U Xk必存在極限，且其任一極限點(diǎn)都是問(wèn)題(8.1.1)的最優(yōu)解.§8.3旋轉(zhuǎn)方向法算法8-3 (旋轉(zhuǎn)方向法)Step1選取初始數(shù)據(jù).選取初始點(diǎn)X0，初始單位正交方向組d1,d2,L ,dn (可 取d1,d2,L ,dn為坐標(biāo)軸方向久倉(cāng)丄©)給定初始步長(zhǎng) (V,丄，丁， 收縮因子(0,1)，放大因子 1，允許誤差0,令k 0 .Step2確定參考點(diǎn).取參考點(diǎn)y Xk，并令z Xk, j 1.Step3 進(jìn)行軸向探測(cè).若 f(y(k)dj) f(y)，令 y: y(k)dj, (k):(k)，

8、轉(zhuǎn) Step4；否則，令(k) :(k)，轉(zhuǎn) Step4.Step4檢驗(yàn)探測(cè)次數(shù).若j n，令j : j 1，返回Step3;否則，轉(zhuǎn)Step5.Step5判斷探測(cè)是否結(jié)束.若f(y) f (z)，令z y, j 1，返回Step3;若 f (y)f(z), f(y) f (Xk)，令 Xk 1 y，轉(zhuǎn) Step6;若 f (y) f(z) f(xQ，轉(zhuǎn) Step7.Step6檢查是否滿足終止準(zhǔn)則.若Xk 1 Xk，迭代終止，Xk 1為問(wèn)題(8.1.1)的近似最優(yōu)解；否則，轉(zhuǎn) Step8.Step7檢驗(yàn)步長(zhǎng)大小若對(duì)一切j 1,2,L , n.(k) j,迭代終止，Xk為問(wèn)題（8.1.1）的近似

9、最優(yōu)解；否則，令z y, j 1，返回Step3.1, 2,L , n，利Pjdj，n0,i di，0.(8.3.1)Pj,j 1,qjPjTqi PjTi 1 qi Pijdj, j 2.構(gòu)造新的單位正交方向djqj,j 1,2丄(8.3.2)(831)d1,d2,L ,dn，并令Step8進(jìn)行軸向旋轉(zhuǎn).計(jì)算各軸向移動(dòng)的步長(zhǎng)的代數(shù)和:dj dj, (k1)j(k),j 1,2,L , n,k: k 1，返回Step2.§8.4 Powell 法算法 8-4 （Powell 法）Step1選取初始數(shù)據(jù).選取初始點(diǎn)X）， n個(gè)線性無(wú)關(guān)的初始搜索方向d0,d1,L ,dn 1，給定允許誤

10、差0,令k 0.Step2進(jìn)行基本搜索.令y° Xk，依次沿d°,d1,L ,dn 1進(jìn)行一維搜索.對(duì)一 切j 1,2丄，n,記f （Yj 1j 1dj 1） min f 厲 1dj J，yj yj 1j 1dj 1 .Step3檢查是否滿足終止準(zhǔn)則.取加速方向 dn Yn Y0，若II dn|，迭代 終止，得Yn為問(wèn)題的近似最優(yōu)解；否則，轉(zhuǎn) Step4.Step4確定搜索方向按f(ym) f(ymi) 0mjaxi f(yj) f(yj 1)( 84仃)確定m,若f(y。)2f(yn) f (2yn y。)2f(ym) f(ymi)(8.4.18)成立，轉(zhuǎn)Step5;否則

11、，轉(zhuǎn)Step6.Step5調(diào)整搜索方向從點(diǎn)yn出發(fā)沿方向dn作一維搜索求出n，使得f(ynndn) minf®.dn) 令Xk 1 ynndn，再令 dj : dj 1, j m,m 1,L ,n 1 , k: k 1，返回 Step2.Step6不調(diào)整搜索方向.令Xk 1 yn， k: k 1，返回Step2.例 2 用 Powell 法求解問(wèn)題(8.1.3): min f (x) x12 x22 3x1 x1x2，仍取初始點(diǎn)x(0)(0,0) T，初始搜索方向組do (0,1)T,d1 (1,0)T，給定允許誤差0.1.解第一次迭代：令y(0)x(0)(0,0)T，從點(diǎn)y(0)出

12、發(fā)沿d0進(jìn)行一維搜索，易得0 0, yy(0)0d0 (0,0)T ;接著從點(diǎn)y出發(fā)沿d1進(jìn)行一維搜索，得33 t1 2,y y1d1(2，。)由此有加速方向d2 yy® (|,0)T .因?yàn)閐23/2，所以要確定調(diào)整方向.由于 f(y(0) 0,f(y)0,f(y(2)9，4按(8.4.17)式有f(y)f(y(2) maxf(y(j) f(y(j1)| j 0,1，因此m 1，并且f(y(m) f(y(m 1) f(y)f(y(2)夕.4又因f(2yy)0,故(8418)式不成立于是，不調(diào)整搜索方向組，并令x(1)y(2)(|,0)T -第二次迭代：取y(0)x(,0)T，從點(diǎn)y(0)出發(fā)沿d0作一維搜索，得,3I23 (1)(0)3 3、t0 ，y y0d0(,)-4 2 4接著從點(diǎn)y出發(fā)沿方向d!作一維搜索，得315 3 t1 8，y y Q 塔訐-由此有加速方向(0)/33 Td2 y y(著)因?yàn)閐23苗/8，所以要確定調(diào)整方向因18964，f(y(0)故按(8417)式易知m9(1)45、匚，f(y) ,f(y)4160，并且f(y(m)f(y(m 1)f(y(0) f(y)916由于f(2y y(0)4516，因此(