第三章一維優(yōu)化方法

1、1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定 進(jìn)退法進(jìn)退法 3.2一維搜索的最優(yōu)化方法一維搜索的最優(yōu)化方法3.2.1 格點(diǎn)法格點(diǎn)法3.2.2 黃金分割法黃金分割法3.2.3 二次插值法二次插值法2第三章第三章 一維優(yōu)化方法一維優(yōu)化方法 用數(shù)值迭代法求解一元函數(shù)的極小點(diǎn)和極小值方法稱為一維搜用數(shù)值迭代法求解一元函數(shù)的極小點(diǎn)和極小值方法稱為一維搜索優(yōu)化方法。索優(yōu)化方法。多維優(yōu)化問(wèn)題常常是通過(guò)一系列的一維優(yōu)化方法來(lái)實(shí)現(xiàn)的。因當(dāng)搜多維優(yōu)化問(wèn)題常常是通過(guò)一系列的一維優(yōu)化方法來(lái)實(shí)現(xiàn)的。因當(dāng)搜索方向索方向 確定后，新設(shè)計(jì)點(diǎn)確定后，新設(shè)計(jì)點(diǎn) 總是位于過(guò)點(diǎn)總是位于過(guò)點(diǎn) 的的 方向上。步長(zhǎng)方向上。步長(zhǎng) 不同不同, 得

2、到的設(shè)計(jì)點(diǎn)和相應(yīng)的函數(shù)值得到的設(shè)計(jì)點(diǎn)和相應(yīng)的函數(shù)值就不同，即只有一個(gè)就不同，即只有一個(gè) 變量。變量。)()()1(KKKSXX)(KS)(KS)(KX3ox1x2( )kX(1)kX*x( )kS(1)( )( )( )kkkkX= X+S由前基本迭代公式由前基本迭代公式:( )k待求待求已知已知(1)( )()minminkkkkF X=F X+Smin( )f這種在給定方向上確定最優(yōu)步長(zhǎng)的過(guò)程這種在給定方向上確定最優(yōu)步長(zhǎng)的過(guò)程, ,稱一維優(yōu)稱一維優(yōu)化。化。 稱為最優(yōu)步長(zhǎng)稱為最優(yōu)步長(zhǎng) min( )f x( )k41x( )F x2x( )fo*X( )fO*n維問(wèn)題維問(wèn)題一系列一系列一維優(yōu)化

3、問(wèn)題一維優(yōu)化問(wèn)題53.1 3.1 搜索區(qū)間的確定搜索區(qū)間的確定x( )f xo單峰函數(shù)單峰函數(shù) a*xb用盡量少的計(jì)算量用盡量少的計(jì)算量,盡快確盡快確定包含定包含x* 的區(qū)間的區(qū)間a, b 關(guān)鍵關(guān)鍵找三點(diǎn)找三點(diǎn): :“高高- -低低- -高高”一維搜索最優(yōu)化過(guò)程可分為兩步一維搜索最優(yōu)化過(guò)程可分為兩步: :1 1、確定極小點(diǎn)所在的初始搜索區(qū)間、確定極小點(diǎn)所在的初始搜索區(qū)間aa，bb2 2、在區(qū)間、在區(qū)間aa，bb中搜索極小點(diǎn)。中搜索極小點(diǎn)。 采用某種方法將此區(qū)間逐步縮小，使其達(dá)到包含極小點(diǎn)采用某種方法將此區(qū)間逐步縮小，使其達(dá)到包含極小點(diǎn)x*在內(nèi)在內(nèi) 的很小鄰域（的很小鄰域（ ） 63.1 3.1

4、 搜索區(qū)間的確定（進(jìn)退法）搜索區(qū)間的確定（進(jìn)退法）ox( )f x1x2x3x1x3xa2xb函數(shù)為函數(shù)為yf(x), 給定初始點(diǎn)給定初始點(diǎn)x1,選定恰當(dāng)?shù)某跏疾介L(zhǎng)為選定恰當(dāng)?shù)某跏疾介L(zhǎng)為h0 一、試探搜索一、試探搜索由于最小點(diǎn)由于最小點(diǎn)x*的位置是未知的的位置是未知的，所以首先要試探最小點(diǎn)，所以首先要試探最小點(diǎn)x*位于初始點(diǎn)位于初始點(diǎn)x1的左方的左方或右方，然后再確定是前進(jìn)還是后退或右方，然后再確定是前進(jìn)還是后退111,( )xyf x21022,()xxhyf x比較比較y1、y2大小大小 21,yy前進(jìn)前進(jìn)21,yy后退后退二、前進(jìn)搜索二、前進(jìn)搜索0,2hhhh3233,( )xxhyf

5、x比較比較y y2 2、y y3 3大?。捍笮。?23,yya, b確定確定23,yy繼續(xù)前進(jìn)繼續(xù)前進(jìn)置換點(diǎn)號(hào)置換點(diǎn)號(hào)12122323,xxyyxxyy7由前：由前：ox( )f x1x2x3x1x3xa2xb三、后退搜索三、后退搜索比較比較y y1 1、y y2 2大小大小 21,yy前進(jìn)前進(jìn)21,yy后退后退0,2-hhhh3233,( )xxhyf x比較比較y y2 2、y y3 3大小：大?。?23,yya, b確定確定23,yy繼續(xù)后退繼續(xù)后退12122121,xxyyxxyy置換點(diǎn)號(hào)1x2x置換點(diǎn)號(hào)12122323,xxyyxxyy89例題例題3.1 試用進(jìn)退法確定函數(shù)試用進(jìn)退法

6、確定函數(shù)f(x)=x2- -6x+9的一維優(yōu)化搜索區(qū)間的一維優(yōu)化搜索區(qū)間a，b。設(shè)初始點(diǎn)。設(shè)初始點(diǎn)x10，初始步長(zhǎng)，初始步長(zhǎng)h0=1。解：按流程圖解：按流程圖3.4，計(jì)算過(guò)程如下：，計(jì)算過(guò)程如下： 由于由于y y2 2yyy3 3，再作前進(jìn)搜索，再作前進(jìn)搜索， x x1 1x x2 2=1=1，y y1 1y y2 2=4=4 x x2 2x x3 3=3=3，y y2 2y y3 3=0=0 h h2h=42h=4 x x3 3x x2 2+h=7+h=7，y y3 3f(xf(x3 3)=16)=16 再比較再比較y y2 2與與y y3 3，有，有y y2 2yy3 3，則取，則取 a

7、ax x1 1=1=1，b bx x3 3=7=7 103.2 3.2 一維搜索的最優(yōu)化方法一維搜索的最優(yōu)化方法 逐漸縮小搜索區(qū)間逐漸縮小搜索區(qū)間 3.2.1 格點(diǎn)法格點(diǎn)法x( )f xo在區(qū)間在區(qū)間a，b的內(nèi)部取的內(nèi)部取n個(gè)個(gè)內(nèi)等分點(diǎn)：內(nèi)等分點(diǎn)： x1，x2，xn區(qū)間區(qū)間a，b被分成被分成(n+1)等等分，各分點(diǎn)的坐標(biāo)為分，各分點(diǎn)的坐標(biāo)為: 1,2,.,1kb axakknn ab1xnx2x1mxmx1mx1mymy1my1212, ., .,nnxxxyyy計(jì)算計(jì)算找出找出minmin,1,2,.,kyknyab新區(qū)間新區(qū)間新區(qū)間新區(qū)間11,mmaxbx*11:?:mmmyesxxxxn

8、o再分格點(diǎn)再分格點(diǎn)區(qū)間縮短率: = 新區(qū)間長(zhǎng)度老區(qū)間長(zhǎng)度21n11格點(diǎn)法特點(diǎn)：格點(diǎn)法特點(diǎn)： 程序簡(jiǎn)單，但計(jì)算效率較低，即在一定精度要求下程序簡(jiǎn)單，但計(jì)算效率較低，即在一定精度要求下計(jì)算函數(shù)值的次數(shù)較多，因而不宜用于維數(shù)較高的計(jì)算函數(shù)值的次數(shù)較多，因而不宜用于維數(shù)較高的復(fù)雜問(wèn)題中。復(fù)雜問(wèn)題中。 12(1)(2)()()f af a與與(1)(2)aa與與(1)(2)()()f af a第一種情況：第一種情況：可丟掉可丟掉 部分部分(2)(, ab基本思想基本思想:逐步縮小搜索區(qū)間逐步縮小搜索區(qū)間,直至最小點(diǎn)存在的范圍達(dá)到允許的直至最小點(diǎn)存在的范圍達(dá)到允許的 誤差范圍為止誤差范圍為止.取中間點(diǎn)為極

9、小點(diǎn)取中間點(diǎn)為極小點(diǎn).在在a,b內(nèi)任取兩點(diǎn)內(nèi)任取兩點(diǎn) , 且且 計(jì)算函數(shù)值計(jì)算函數(shù)值: 進(jìn)行比較可得進(jìn)行比較可得:3.2.2 黃金分割法黃金分割法(1)(2),aaab13(1)(2)()()f af a(1)(2)()()f af a第二種情況：第二種情況：第三種情況：第三種情況：可丟掉可丟掉 部分部分(1) ,)a a問(wèn)題問(wèn)題1:= =?問(wèn)題問(wèn)題2:如何取點(diǎn)如何取點(diǎn)?14(1)(2),:.aa在在區(qū)區(qū)間間中中的的位位置置相相對(duì)對(duì)邊邊界界對(duì)對(duì)稱稱縮縮小小后后保保留留點(diǎn)點(diǎn)在在新新區(qū)區(qū)間間中中的的位位置置與與丟丟去去點(diǎn)點(diǎn)在在原原區(qū)區(qū)間間中中原原的的位位置置相相當(dāng)當(dāng)則則LlllL由此得由此得解此方

10、程得兩個(gè)根取其正根為解此方程得兩個(gè)根取其正根為 =0.6180339887=0.6180339887 0)(2lLLl01)()(2LlLl012215 15問(wèn)題問(wèn)題2:如何取點(diǎn)如何取點(diǎn)?0a0b1x2x1y2y1b2x1x1a2a2y1y2b取點(diǎn)規(guī)則取點(diǎn)規(guī)則:120.382()0.618()xab axab a 右圖示右圖示,第一次區(qū)間縮短第一次區(qū)間縮短:120.382()0.618()xab axab a 第二次區(qū)間縮短第二次區(qū)間縮短:100.618LL2110.382() xxxab a20100.3820.6180.618LLLL0L100.618LL00.382 L200.382LL

11、16終止準(zhǔn)則終止準(zhǔn)則: :( )( )kkba2a0a0b1x2x1y2y1b2x1x1a2y1y2b( )( )*2()kkabxff x17例題例題3.3試用黃金分割法求目標(biāo)函數(shù)試用黃金分割法求目標(biāo)函數(shù)f(x)=x2-6x+9的最優(yōu)解。給定初始區(qū)間的最優(yōu)解。給定初始區(qū)間1，7，收斂精度，收斂精度0.4。解：第一次區(qū)間縮短：解：第一次區(qū)間縮短： 計(jì)算兩內(nèi)點(diǎn)及對(duì)應(yīng)函數(shù)值：計(jì)算兩內(nèi)點(diǎn)及對(duì)應(yīng)函數(shù)值： x1=a+0.382(b-a)=3.292，y1=f(x1)=0.085264 x2=a+0.618(b-a)=4.708，y2=f(x2)=2.917264 作函數(shù)值比較，可見(jiàn)作函數(shù)值比較，可見(jiàn)y1

12、 第二次區(qū)間縮短第二次區(qū)間縮短: 置換置換： x2x1=3.292，y2y1=0.085 264 增補(bǔ)增補(bǔ): x1=a(1)+0.382(b(1)- -a(1)2.416456， y1=f(x1)=0.340524 2a0a0b1x2x1y2y1b2x1x1a2y1y2b18各次縮短區(qū)間的計(jì)算數(shù)據(jù)見(jiàn)表各次縮短區(qū)間的計(jì)算數(shù)據(jù)見(jiàn)表3.2。第六次區(qū)間縮短的端點(diǎn)。第六次區(qū)間縮短的端點(diǎn)a(6)2.750 917，b(6)3.085 305，b(6)-a(6)0.334 388，滿足精度要求，終止計(jì)算。，滿足精度要求，終止計(jì)算。取最優(yōu)解為取最優(yōu)解為:19基本原理基本原理: :利用一個(gè)低次插值多項(xiàng)式來(lái)逼近原

13、目標(biāo)函數(shù)利用一個(gè)低次插值多項(xiàng)式來(lái)逼近原目標(biāo)函數(shù), ,然然后求該多項(xiàng)式的極小點(diǎn)后求該多項(xiàng)式的極小點(diǎn), ,并以此作為目標(biāo)函數(shù)的近似極并以此作為目標(biāo)函數(shù)的近似極小點(diǎn)小點(diǎn), ,反復(fù)使用此法反復(fù)使用此法, ,逐次擬合逐次擬合, ,直到滿足給定的精直到滿足給定的精度為止度為止. . 常用的插值多項(xiàng)式為二次或三次多項(xiàng)式常用的插值多項(xiàng)式為二次或三次多項(xiàng)式, ,分別稱為二分別稱為二次插值法或三次插值法。次插值法或三次插值法。一、二次插值函數(shù)的構(gòu)成一、二次插值函數(shù)的構(gòu)成：p(x)=Axp(x)=Ax2 2+Bx+C +Bx+C 式中式中A A、B B、C C為待定系數(shù)，為待定系數(shù)，可由可由P P1 1、P P2

14、2、P P3 3三個(gè)插值結(jié)點(diǎn)三個(gè)插值結(jié)點(diǎn)的信息按下列線性方程組確定的信息按下列線性方程組確定3.2.3 二次插值法二次插值法20( )f x1P3P2Pa1xb3x 2x*xf(x)搜索區(qū)間為搜索區(qū)間為a，b取點(diǎn)取點(diǎn)x1、x2、x3，構(gòu)成二次函數(shù)，構(gòu)成二次函數(shù)2130.5xxx開(kāi)始時(shí)開(kāi)始時(shí):計(jì)算計(jì)算112233(),(),()ff xff xff x得三點(diǎn)得三點(diǎn):111122133(,),(,),(,)P xfP xfP xf作插值函數(shù)作插值函數(shù)p(x)2( )p xxAxBC211112111221113()()()p xxxfp xxxABCABCABCfp xxxf解方程組，得待定系數(shù)解

15、方程組，得待定系數(shù)A、B、C *Px( )p x*Pf求求p(x)的極小點(diǎn)的極小點(diǎn)x*P ，與，與x2比較比較區(qū)間縮短區(qū)間縮短1x3x2xx1=ax3=b21一、二次插值函數(shù)的構(gòu)成一、二次插值函數(shù)的構(gòu)成 2( )p xxAxBC解方程組，得待定系數(shù)解方程組，得待定系數(shù)A、B、C 231312123122331()()()()()()xxfxxfxxfxAxxxxx 222222231312123122331()()()()()()xxfxxfxxBfxxxxxx322311313221123122331()()()()()()xxx x fxxx x fxx xCx fxxxxxx22求二次插

16、值函數(shù)的極小點(diǎn)：求二次插值函數(shù)的極小點(diǎn)： 222222231312123231312123*1 ()()()22()()()PBxxfxxfxxfAxxfxxxfxxf 3113121211223()()() ()ffcxxffxxccxx令令1132*12Pcxxcx( )20p xxAB令令23二、二、區(qū)間區(qū)間的的縮短縮短*22ppxxff*22ppxxff*22ppxxff*22ppxxff24區(qū)間區(qū)間的的縮短程序框圖縮短程序框圖25三、終止準(zhǔn)則三、終止準(zhǔn)則 ( )f x1P3P2Pa1xb3x 2x*(1)Px( )p x*(1)Pf1x3x2x*(1)*(2)*(1)*(*), ., .kkPPPPxxxxx*( )*(1)kkPPxx*( )kPxx2627在流程圖中有兩個(gè)判別框的內(nèi)容需稍加說(shuō)明。其一是在流程圖中有兩個(gè)判別框的內(nèi)容需稍加說(shuō)明。其一是c2=0？若成？若成立，即：立，即：或?qū)懽骰驅(qū)懽鬟@說(shuō)明三個(gè)插值結(jié)點(diǎn)這說(shuō)明三個(gè)插值結(jié)點(diǎn)P1(x1，f1)、P2(x2，f2)、P3(x3，f3)在同一條直在同一條直線上