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

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

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

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

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

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

6、確定函數(shù)f(x)=x2- -6x+9的一維優(yōu)化搜索區(qū)間的一維優(yōu)化搜索區(qū)間a，b。設(shè)初始點。設(shè)初始點x10，初始步長，初始步長h0=1。解：按流程圖解：按流程圖3.4，計算過程如下：，計算過程如下： 由于由于y y2 2yyy3 3，再作前進搜索，再作前進搜索， 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 格點法格點法x( )f xo在區(qū)間在區(qū)間a，b的內(nèi)部取的內(nèi)部取n個個內(nèi)等分點：內(nèi)等分點： x1，x2，xn區(qū)間區(qū)間a，b被分成被分成(n+1)等等分，各分點的坐標為分，各分點的坐標為: 1,2,.,1kb axakknn ab1xnx2x1mxmx1mx1mymy1my1212, ., .,nnxxxyyy計算計算找出找出minmin,1,2,.,kyknyab新區(qū)間新區(qū)間新區(qū)間新區(qū)間11,mmaxbx*11:?:mmmyesxxxxn

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

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

10、程得兩個根取其正根為解此方程得兩個根取其正根為 =0.6180339887=0.6180339887 0)(2lLLl01)()(2LlLl012215 15問題問題2:如何取點如何取點?0a0b1x2x1y2y1b2x1x1a2a2y1y2b取點規(guī)則取點規(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終止準則終止準則: :( )( )kkba2a0a0b1x2x1y2y1b2x1x1a2y1y2b( )( )*2()kkabxff x17例題例題3.3試用黃金分割法求目標函數(shù)試用黃金分割法求目標函數(shù)f(x)=x2-6x+9的最優(yōu)解。給定初始區(qū)間的最優(yōu)解。給定初始區(qū)間1，7，收斂精度，收斂精度0.4。解：第一次區(qū)間縮短：解：第一次區(qū)間縮短： 計算兩內(nèi)點及對應(yīng)函數(shù)值：計算兩內(nèi)點及對應(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ù)值比較，可見作函數(shù)值比較，可見y1

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

13、目標函數(shù)利用一個低次插值多項式來逼近原目標函數(shù), ,然然后求該多項式的極小點后求該多項式的極小點, ,并以此作為目標函數(shù)的近似極并以此作為目標函數(shù)的近似極小點小點, ,反復使用此法反復使用此法, ,逐次擬合逐次擬合, ,直到滿足給定的精直到滿足給定的精度為止度為止. . 常用的插值多項式為二次或三次多項式常用的插值多項式為二次或三次多項式, ,分別稱為二分別稱為二次插值法或三次插值法。次插值法或三次插值法。一、二次插值函數(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三個插值結(jié)點三個插值結(jié)點的信息按下列線性方程組確定的信息按下列線性方程組確定3.2.3 二次插值法二次插值法20( )f x1P3P2Pa1xb3x 2x*xf(x)搜索區(qū)間為搜索區(qū)間為a，b取點取點x1、x2、x3，構(gòu)成二次函數(shù)，構(gòu)成二次函數(shù)2130.5xxx開始時開始時:計算計算112233(),(),()ff xff xff x得三點得三點: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)的極小點的極小點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ù)的極小點：求二次插值函數(shù)的極小點： 222222231312123231312123*1 ()()()22()()()PBxxfxxfxxfAxxfxxxfxxf 3113121211223()()() ()ffcxxffxxccxx令令1132*12Pcxxcx( )20p xxAB令令23二、二、區(qū)間區(qū)間的的縮短縮短*22ppxxff*22ppxxff*22ppxxff*22ppxxff24區(qū)間區(qū)間的的縮短程序框圖縮短程序框圖25三、終止準則三、終止準則 ( )f x1P3P2Pa1xb3x 2x*(1)Px( )p x*(1)Pf1x3x2x*(1)*(2)*(1)*(*), ., .kkPPPPxxxxx*( )*(1)kkPPxx*( )kPxx2627在流程圖中有兩個判別框的內(nèi)容需稍加說明。其一是在流程圖中有兩個判別框的內(nèi)容需稍加說明。其一是c2=0？若成？若成立，即：立，即：或?qū)懽骰驅(qū)懽鬟@說明三個插值結(jié)點這說明三個插值結(jié)點P1(x1，f1)、P2(x2，f2)、P3(x3，f3)在同一條直在同一條直線上