一維搜索的最優(yōu)方法(黃金分割法)課件

1、一維搜索的最優(yōu)方法(黃金分割法) 一元函數(shù)的極小值問題，就是一維最優(yōu)化問題，其數(shù)值迭代方法亦稱為一維搜索方法。 一維搜索最優(yōu)化是優(yōu)化方法中最簡(jiǎn)單、最基本的方法。 主要方法有：0.618法、牛頓法、二次插值法等。一維搜索的最優(yōu)方法(黃金分割法)迭代計(jì)算的基本格式迭代計(jì)算的基本格式( )(1)( )( )kkkkXXS4 41 1 一維搜索的搜索區(qū)間一維搜索的搜索區(qū)間一、一維搜索的概念一、一維搜索的概念k)k) S（顯然，搜索方向和步長因子構(gòu)成決定了每最優(yōu)一次迭代化算法好的修正量，它們是壞的重要因素。一維搜索的最優(yōu)方法(黃金分割法)k)k)k)k)(1)( )k)k)( )( )k)k)k) SX

2、S ()()() ()kkkkffff （假定給定了搜索方向，從點(diǎn)出發(fā)沿方向進(jìn)行搜索，要確定步長，使得記（ ）即確定步長，就是單變量函數(shù) （ ）的搜索問題。稱為一維搜索問題。XXSXXS( )k)k)min ()kf （ ）XS一維搜索的最優(yōu)方法(黃金分割法)在極小點(diǎn)附近，函數(shù)呈現(xiàn)在極小點(diǎn)附近，函數(shù)呈現(xiàn)“大小大大小大”xy( )yf xxy( )yf x一維搜索的思路一維搜索的思路（1）確定極小點(diǎn)）確定極小點(diǎn)*所在的區(qū)所在的區(qū)間間a, b，在此區(qū)間內(nèi)，函數(shù)呈，在此區(qū)間內(nèi)，函數(shù)呈現(xiàn)現(xiàn)“大小大大小大”變化趨勢(shì)。變化趨勢(shì)。搜速區(qū)間搜速區(qū)間。ab（2）在）在a, b內(nèi)找內(nèi)找*將區(qū)將區(qū)間長度逐步縮短。間

3、長度逐步縮短。0.618法與二次插值法就是解法與二次插值法就是解決第二個(gè)步驟的方法決第二個(gè)步驟的方法一維搜索的最優(yōu)方法(黃金分割法)在極小點(diǎn)附近，函數(shù)呈現(xiàn)在極小點(diǎn)附近，函數(shù)呈現(xiàn)“大小大大小大”xy( )yf xxy( )yf x一維搜索的最優(yōu)方法(黃金分割法) 基本思想 從一點(diǎn)出發(fā)，按一定的步長，試圖確定出函數(shù)值呈現(xiàn)出”高低高“的三個(gè)點(diǎn)。一個(gè)方向不成功，就退回來沿相反方向搜索。 具體作法：二、確定搜索區(qū)間的進(jìn)退法二、確定搜索區(qū)間的進(jìn)退法00000000000 0,hhhh 給出初始點(diǎn)，初始步長若（ ）（）,則下一步仍然從點(diǎn)出發(fā)，沿反方向搜索，直到目標(biāo)函數(shù)上升就停止。這樣就可以得到一個(gè)搜索區(qū)間。

4、一維搜索的最優(yōu)方法(黃金分割法)進(jìn)退法步驟0step1. 0()h給定初始值。給定初始點(diǎn)，初始步長。(1)(2)(1)(2)0112step2. ()( )( )()2hffffff1令，。計(jì)算（），（）令（），（）3(3)3(3)2123232132step3. ()()f,f ,ffhffffffffffhff33若，。計(jì)算（）令（）(1) 若，則a,b=，(2) 若，則 2hh前進(jìn)運(yùn)算， ，計(jì)算（），令（止算返停計(jì)）(2)(3)(1)(3)(2)(1)(3)(2)(2)(3)1( )回重新開始。一維搜索的最優(yōu)方法(黃金分割法)進(jìn)退試算法步驟進(jìn)退試算法步驟3(3)2113213231ste

5、p4. -; ()hh,;,;fffffffffhffff3若在步2中，后退運(yùn)算 以為起始點(diǎn)，重排順序+。計(jì)算（），令（）(1) 若，步長反號(hào)，反方向a,搜索。則(1)(1)(3)(2)(1)(3)(2)(2)(3)3(3)312132 1(),f ,( )ffffffhff3b=，(2) 若，則 2hh， ，計(jì)算（），令（）停止計(jì)算。返回重新開始。(3)(2)(2)(1)(3)(2)(2)(3)一維搜索的最優(yōu)方法(黃金分割法)例4.1 用進(jìn)退法確定函數(shù)2710 01(),f aaah0的一維優(yōu)化初始搜索區(qū)間a,b。設(shè)初始點(diǎn)初始步長。一維搜索的最優(yōu)方法(黃金分割法)12122133231 a.

6、 0 10 1 4b. 2 0 2 12 1 ()()()., ffhffffhffcffh1012232解： 按順序進(jìn)行計(jì)算，有比較作前進(jìn)運(yùn)算比較再作前進(jìn)運(yùn)算132323 4 2 0 2(),()() ffffhff12234 一維搜索的最優(yōu)方法(黃金分割法)231132323122313 2 24 0 2 18 ,=2.,(),()().,.dffhffffhffeffffab 21223比較再作前進(jìn)運(yùn)算248 此時(shí)有，故即初始搜索區(qū)間為2,8.一維搜索的最優(yōu)方法(黃金分割法)基本思路：逐步縮小搜索區(qū)間，直至最小點(diǎn)存在的區(qū)間達(dá)到允許的誤差范圍為止。一、消去法的基本原理12121212 (

7、)()( )()( )(*( )() , ,()()(,),(a babfff aa bff設(shè)一元函數(shù)的起始搜索區(qū)間為是函數(shù)的極小點(diǎn)。 將在搜索區(qū)間內(nèi)任取兩點(diǎn)、。且計(jì)算、。與進(jìn)行比較，可能出現(xiàn)三種情況：( )4 42 2 黃金分割法（黃金分割法（0.6180.618法）法） 一維搜索的最優(yōu)方法(黃金分割法)1222 1 ( )()()()( )()().(,ffba這況丟點(diǎn)內(nèi)在種情下，可以掉部分，而最小必定在。1( )a()f()fab*a*1( )a2()a2()ab一維搜索的最優(yōu)方法(黃金分割法)1211 2 ( )()( )( )()()(). ,), ffab在這種情況下，可以丟掉部分

8、，而最小點(diǎn)必定在內(nèi)。1( )a()f()fab*a*1( )a2()a2()ab一維搜索的最優(yōu)方法(黃金分割法)121212 3 ( )()( )()( )()( )()(). ,), ,ffab在這種情況下，可以丟掉部分，也可以丟掉(部分，而最小點(diǎn)必定在內(nèi)。因此這種情況可以并入上面的任意一種情況。()fab*1( )a2()a122121 1 2 ()()()()()()( )()().,()()().,ffaffb取區(qū)間；取區(qū)間。一維搜索的最優(yōu)方法(黃金分割法)二、二、0.618的由來的由來11 .,（ ）（2）在a,b中位置對(duì)稱2. 每次縮短的區(qū)間縮短率不變，減少計(jì)算量。Lab(1)(2

9、)L1= LL1= L211LLLLL1= LL 2=()L(2)ab(1)L 2=() L1210 0 618.一維搜索的最優(yōu)方法(黃金分割法)Lab(1)(2)L1= LL1= L0 618.L1= LL 2=()L(2)b(1)L 2=() La (1)數(shù)學(xué)家華羅庚運(yùn)用黃金分割法提出一種可以盡可能減少做試數(shù)學(xué)家華羅庚運(yùn)用黃金分割法提出一種可以盡可能減少做試驗(yàn)次數(shù)、盡快地找到最優(yōu)方案的方法驗(yàn)次數(shù)、盡快地找到最優(yōu)方案的方法優(yōu)選法優(yōu)選法一維搜索的最優(yōu)方法(黃金分割法)三、三、0.618法的迭代過程及算法框圖法的迭代過程及算法框圖1212121212(1) a,b 0 618 0 618 ( )

10、()( )()( )()( )().().()()()(), ()bbaabaffffff在初始區(qū)間內(nèi)取兩個(gè)計(jì)算點(diǎn)和，其值分別為計(jì)算和，令一維搜索的最優(yōu)方法(黃金分割法)22121121211211122 a. 0 618 b. ()()()( )()( )( )(), ,.(),(), ,ffbaa bbaff bbaffffa則丟掉區(qū)間(部分，取為新區(qū)間在計(jì)算中作置換較數(shù)縮區(qū)間：則丟掉區(qū)間比比函函值值，小小搜搜索索1112122122 0 618 )( )( )()( )()(), , ,.(),()ba baff abaff部分，取為新區(qū)間在計(jì)算中作置換：一維搜索的最優(yōu)方法(黃金分割法)

11、3 2*( )-b aab判斷迭代終止條件當(dāng)縮短的區(qū)間距離小于某一個(gè)預(yù)先規(guī)定的精度，即時(shí)，終止迭代。一般取區(qū)間的中點(diǎn)作為最優(yōu)解。一維搜索的最優(yōu)方法(黃金分割法)黃金分割法計(jì)算框圖黃金分割法計(jì)算框圖否停是2*ab111222 0 618 0 618 ()()()().()().()()bbaafafabaafaf12 ?ff比較函數(shù)值。121212220 618( )()( )()(),.()()aa aaffabaaf af, ,a b初始條件： -?b a212121110 618()()()()(),.(),()ab aaffbbaafaf是否一維搜索的最優(yōu)方法(黃金分割法)例例 用用0.

12、6180.618法求一元函數(shù)法求一元函數(shù)2271 a,b0 5,0.50.15()fa的極小點(diǎn)。初始搜索區(qū)間為 .，取迭代精度 。11122212 (1) a,b 0 6180 118 0.854 0 6180 118 109 (2) ( )( )()().().,().().,()bbaffabaffffb在初始區(qū)間內(nèi)取點(diǎn)并計(jì)算函數(shù)值。.比較函數(shù)值，解：縮短搜索區(qū)間11212220 5 0 1180 50 1180 618 0 118 1.09 0 618 ( )( )()()(). ,.-.(.).()() ab afabaff 判斷迭代終止條件: 繼續(xù) ，新點(diǎn)0.264,縮短-1.125

13、一維搜索的最優(yōu)方法(黃金分割法)1211212 (3) 0 5 0 1180 50 1180 382 0 264 1.125 ( )( )()(). ,.-.ffbab af比較函數(shù)值，縮短搜索區(qū)間 判斷迭代終止條件 : ，新點(diǎn) 繼續(xù)縮短2212220 618 (4) 0 118 0 3540 3540 1180 236 ()()()(.()().,.-.abaffffabb a0.354,-1.103 比較函數(shù)值，縮短搜索區(qū)間 判斷迭代終止條件: 繼短續(xù)縮121110 264 1.125 0 618 )( )( ).()()fbbaff，新點(diǎn)0.208,-1.120一維搜索的最優(yōu)方法(黃金分

14、割法)121(5) 0 50 28 10 0 3540 3540 2080 14562( ),.-. ().ffbb aaab比較函數(shù)值，縮短搜索區(qū)間0.208 判斷迭代終 迭代停止。取 止 理論解條件: 一維搜索的最優(yōu)方法(黃金分割法)22212E(0)T(0)Tmin()(- 3) + (- 4) + 52,3 2,3,XfXxxSX對(duì)下列優(yōu)化問題設(shè)例：搜索方向 做一維搜索 （ 1） 轉(zhuǎn) 化 為 一 維 搜 速 問 題 ；（ 2） 用 進(jìn) 退 法 確 定 初 始 搜 速 區(qū) 間 ； （ 3） 用 0.618法 確 定 初 始 搜主 要 步 驟 ：速 區(qū) 間 ；一維搜索的最優(yōu)方法(黃金分割法

15、)4-3 4-3 牛頓法牛頓法基本思想：基本思想：在極小點(diǎn)附近，將目標(biāo)函數(shù)做二階在極小點(diǎn)附近，將目標(biāo)函數(shù)做二階Taylor展開，展開，得二次多項(xiàng)式，用該多項(xiàng)式的極小點(diǎn)近似原問題的極小點(diǎn)。得二次多項(xiàng)式，用該多項(xiàng)式的極小點(diǎn)近似原問題的極小點(diǎn)。(0)(0)(0)(0)(0)(0)2( ) =()+()(0 5()(xxf xfxx- x)fxx- x)對(duì)初始點(diǎn)（極小點(diǎn)的估計(jì)）： .(0)(0)(0)(0)(0)(0)( )0()()()() ()xfxfxx- xfxx= xfx令 ，有 0新的極小點(diǎn)(0)(1)1(0)2(1)(0)(1)()() ()()fxfxx= xxxfxfx（ ）（ ）令

16、一維搜索的最優(yōu)方法(黃金分割法)(k)(k+1)(k)(k)()()fxx= xfx一般迭代格式(0)(k) f xxf xfxxxxx設(shè) ( )存在連續(xù)二階導(dǎo)數(shù)， 滿足()0； ()0初始點(diǎn)接近 ，由牛頓法產(chǎn)生的 迭代序列收斂于 結(jié)論。：一維搜索的最優(yōu)方法(黃金分割法)(0)(k)(k)(k)(k+1)(k)(k)0 0()() 1x,k2 f xxxfxx= xfxkk21） 給定初始點(diǎn)，允許誤差） 若()，迭代停止，得 否則，進(jìn)行下一步3）計(jì)計(jì)算步驟算 ，轉(zhuǎn)步 ）：注意點(diǎn)：初始迭代點(diǎn)的選擇很重要，要靠近極小點(diǎn)，否則可注意點(diǎn)：初始迭代點(diǎn)的選擇很重要，要靠近極小點(diǎn)，否則可 能不收斂。能不收斂

17、。 需計(jì)算一、二階導(dǎo)數(shù)，計(jì)算兩增大，實(shí)用可能不方便。需計(jì)算一、二階導(dǎo)數(shù)，計(jì)算兩增大，實(shí)用可能不方便。一維搜索的最優(yōu)方法(黃金分割法)1432E0 m in()34121 2fxxxxx.x（）例 ， 迭 代 兩 次思考思考：實(shí)際問題如何得到初始迭代點(diǎn)？實(shí)際問題如何得到初始迭代點(diǎn)？一維搜索的最優(yōu)方法(黃金分割法)割線法：割線法：導(dǎo)數(shù)的近似計(jì)算。導(dǎo)數(shù)的近似計(jì)算。(k)xxy(k-1)x( )y= f x切線斜率割線斜率(k)(k1)(k)(k)(k1)()()()f xf xfxxx(k)(k1)(k)(k)(k1)()()()fxfxfxxx一維搜索的最優(yōu)方法(黃金分割法)割線法割線法(k)(k

18、1)(k+1)(k)(k)(k1)()()()()f xf xx= xfxfx一般迭代格式不需計(jì)算導(dǎo)數(shù)，但收斂速度較牛頓法慢。1432E0 m in()34121 2fxxxxx.x（）例 ， 迭 代 兩 次一維搜索的最優(yōu)方法(黃金分割法)4-3 4-3 二次插值法二次插值法P( ) , , xa ba b基本設(shè)函數(shù)在內(nèi)呈現(xiàn)“大小大”單峰變化在上以低次（二次或三次）插值多項(xiàng)式來逼近原目標(biāo)函數(shù)，求得多項(xiàng)式的極值點(diǎn)，逐步縮短搜速區(qū)間。反復(fù)計(jì)算，直至給定精度。此法應(yīng)想。思用較廣：一維搜索的最優(yōu)方法(黃金分割法)(1)xy( )y= f xab(2)(3)1f2f3f( )y= P x(1)(2)(3

19、)(1)(2)(3)ab在a,b中設(shè)定三點(diǎn)，和123123f , f , f ,fff對(duì)應(yīng)有 且P一維搜索的最優(yōu)方法(黃金分割法)2012xaa xa x構(gòu)造二次多項(xiàng)式P( )(1)(1)(1)20121(2)(2)(2)20122(3)(3)(3)20123(i=0,1,2)()()(1)()aaaafaaafaaafi由插值條件確定待定的P()P()P()(1)xy( )y= f xab(2)(3)1f2f3f( )y= P x一維搜索的最優(yōu)方法(黃金分割法)121(1)(3)1P2P2202C12Cxxaa xaa求P( )極小點(diǎn)，P( )311(3)(1)(2)(1)2112(2)(3

20、)C()()CCffff/其中，一維搜索的最優(yōu)方法(黃金分割法)(2)PP2(1)(1)(3)(2)(2)P1132 2P 1 ff, f = f , f = f ,f = f（ ），( )fy1fP(1)(2)Pf(3)yx2f3f(1)(2)(3)一維搜索的最優(yōu)方法(黃金分割法)(2)PP2(1)(2)(2)(3)(3)P1P32 33 3 ff, f = f , f = f ,f = f（ ），( )fy1fP(1)(2)Pf(3)yx2f3f(1)(2)(3)一維搜索的最優(yōu)方法(黃金分割法)(2)Pf x比較與兩點(diǎn)， ( )的大??；縮短搜索區(qū)間。(2)PP2(1)(1)(2)(3)(2)P1 ff,（ ），(2)PP2(1)(2)(2)(3)(3)P3 ff,（ ），一維搜索的最優(yōu)方法(黃金分割法)注意點(diǎn)注意點(diǎn)(1)(2)(3)1223 -; 1- ff , ff) 三個(gè)試探點(diǎn) 且大 小 大241242122 2442ffff（ ）（ ）（ ）（ ）) 迭代中止條件 記與 是前一次迭代的插值函數(shù)極小點(diǎn)與極小值； 記與 是本次迭代的插值函數(shù)極小點(diǎn)與極小值。、是給定的精度 若 - 或 -一維搜索的最優(yōu)方法(黃金分割法)20,