優(yōu)化1-一維優(yōu)化問題

1、一維最優(yōu)化理論主講教師：范興朗E-mail： 一元函數(shù)的極小值問題，就是一維最優(yōu)化問題，其數(shù)值迭代方法亦稱為一維搜索方法。 一維搜索最優(yōu)化是優(yōu)化方法中最簡單、最基本的方法。 主要方法有：0.618法、牛頓法、二次插值法等。一維搜索的最優(yōu)化方法迭代計算的基本格式迭代計算的基本格式( )(1)( )( )kkkkXXS1 1 一維搜索的搜索區(qū)間一維搜索的搜索區(qū)間一、一維搜索的概念一、一維搜索的概念k)k) S（顯然，搜索方向和步長因子構(gòu)成決定了每最優(yōu)一次迭代化算法好的修正量，它們是壞的重要因素。k)k)k)k)(1)( )k)k)( )( )k)k)k) SXS ()()() ()kkkkffff

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

3、個步驟的方法決第二個步驟的方法在極小點附近，函數(shù)呈現(xiàn)在極小點附近，函數(shù)呈現(xiàn)“大小大大小大”xy( )yf xxy( )yf x 基本思想 從一點出發(fā)，按一定的步長，試圖確定出函數(shù)值呈現(xiàn)出”高低高“的三個點。一個方向不成功，就退回來沿相反方向搜索。 具體作法：二、確定搜索區(qū)間的進(jìn)退法二、確定搜索區(qū)間的進(jìn)退法00000000000 0,hhhh 給出初始點，初始步長若（ ）（）,則下一步仍然從點出發(fā)，沿反方向搜索，直到目標(biāo)函數(shù)上升就停止。這樣就可以得到一個搜索區(qū)間。進(jìn)退法步驟0step1. 0()h給定初始值。給定初始點，初始步長。(1)(2)(1)(2)0112step2. ()( )( )()

4、2hffffff1令，。計算（），（）令（），（）3(3)3(3)2123232132step3. ()()f,f ,ffhffffffffffhff33若，。計算（）令（）(1) 若，則a,b=，(2) 若，則 2hh前進(jìn)運算， ，計算（），令（止算返停計）(2)(3)(1)(3)(2)(1)(3)(2)(2)(3)1( )回重新開始。進(jìn)退試算法步驟進(jìn)退試算法步驟3(3)2113213231step4. -; ()hh,;,;fffffffffhffff3若在步2中，后退運算 以為起始點，重排順序+。計算（），令（）(1) 若，步長反號，反方向a,搜索。則(1)(1)(3)(2)(1)(3)

5、(2)(2)(3)3(3)312132 1(),f ,( )ffffffhff3b=，(2) 若，則 2hh， ，計算（），令（）停止計算。返回重新開始。(3)(2)(2)(1)(3)(2)(2)(3)例1 用進(jìn)退法確定函數(shù)2710 01(),f aaah0的一維優(yōu)化初始搜索區(qū)間a,b。設(shè)初始點初始步長。12122133231 a. 0 10 1 4b. 2 0 2 12 1 ()()()., ffhffffhffcffh1012232解： 按順序進(jìn)行計算，有比較作前進(jìn)運算比較再作前進(jìn)運算132323 4 2 0 2(),()() ffffhff12234 231132323122313 2

6、24 0 2 18 ,=2.,(),()().,.dffhffffhffeffffab 21223比較再作前進(jìn)運算248 此時有，故即初始搜索區(qū)間為2,8.基本思路：逐步縮小搜索區(qū)間，直至最小點存在的區(qū)間達(dá)到允許的誤差范圍為止。一、基本原理12121212 ( )()( )()( )(*( )() , ,()()(,),(a babfff aa bff設(shè)一元函數(shù)的起始搜索區(qū)間為是函數(shù)的極小點。 將在搜索區(qū)間內(nèi)任取兩點、。且計算、。與進(jìn)行比較，可能出現(xiàn)三種情況：( )2 2 黃金分割法（黃金分割法（0.6180.618法）法） 1222 1 ( )()()()( )()().(,ffba這況丟點

7、內(nèi)在種情下，可以掉部分，而最小必定在。1( )a()f()fab*a*1( )a2()a2()ab1211 2 ( )()( )( )()()(). ,), ffab在這種情況下，可以丟掉部分，而最小點必定在內(nèi)。1( )a()f()fab*a*1( )a2()a2()ab121212 3 ( )()( )()( )()( )()(). ,), ,ffab在這種情況下，可以丟掉部分，也可以丟掉(部分，而最小點必定在內(nèi)。因此這種情況可以并入上面的任意一種情況。()fab*1( )a2()a122121 1 2 ()()()()()()( )()().,()()().,ffaffb取區(qū)間；取區(qū)間。二

8、、二、0.618的由來的由來11 .,（ ）（2）在a,b中位置對稱2. 每次縮短的區(qū)間縮短率不變，減少計算量。Lab(1)(2)L1= LL1= L211LLLLL1= LL 2=()L(2)ab(1)L 2=() L1210 0 618.Lab(1)(2)L1= LL1= L0 618.L1= LL 2=()L(2)b(1)L 2=() La (1)數(shù)學(xué)家華羅庚運用黃金分割法提出一種可以盡可能減少做試數(shù)學(xué)家華羅庚運用黃金分割法提出一種可以盡可能減少做試驗次數(shù)、盡快地找到最優(yōu)方案的方法驗次數(shù)、盡快地找到最優(yōu)方案的方法優(yōu)選法優(yōu)選法三、三、0.618法的迭代過程及算法框圖法的迭代過程及算法框圖1

9、212121212(1) a,b 0 618 0 618 ( )()( )()( )()( )().().()()()(), ()bbaabaffffff在初始區(qū)間內(nèi)取兩個計算點和，其值分別為計算和，令22121121211211122 a. 0 618 b. ()()()( )()( )( )(), ,.(),(), ,ffbaa bbaff bbaffffa則丟掉區(qū)間(部分，取為新區(qū)間在計算中作置換較數(shù)縮區(qū)間：則丟掉區(qū)間比比函函值值，小小搜搜索索1112122122 0 618 )( )( )()( )()(), , ,.(),()ba baff abaff部分，取為新區(qū)間在計算中作置換：

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

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

12、382 0 264 1.125 ( )( )()(). ,.-.ffbab af比較函數(shù)值，縮短搜索區(qū)間 判斷迭代終止條件 : ，新點 繼續(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，新點0.208,-1.120121(5) 0 50 28 10 0 3540 3540 2080 14562( ),.-. ().ffbb aaab

13、比較函數(shù)值，縮短搜索區(qū)間0.208 判斷迭代終 迭代停止。取 止 理論解條件: 22212E(0)T(0)Tmin()(- 3) + (- 4) + 52,3 2,3,XfXxxSX對下列優(yōu)化問題設(shè)例：搜索方向 做一維搜索 （1）轉(zhuǎn)化為一維搜速問題；（2）用進(jìn)退法確定初始搜速區(qū)間； （3）用0.618法確定初始搜主要步驟：速區(qū)間；3 3 牛頓法牛頓法基本思想：基本思想：在極小點附近，將目標(biāo)函數(shù)做二階在極小點附近，將目標(biāo)函數(shù)做二階Taylor展開，展開，得二次多項式，用該多項式的極小點近似原問題的極小點。得二次多項式，用該多項式的極小點近似原問題的極小點。(0)(0)(0)(0)(0)(0)2(

14、 ) =()+()(0 5()(xxf xfxx- x)fxx- x)對初始點（極小點的估計）： .(0)(0)(0)(0)(0)(0)( )0()()()() ()xfxfxx- xfxx= xfx令 ，有 0新的極小點(0)(1)1(0)2(1)(0)(1)()() ()()fxfxx= xxxfxfx（ ）（ ）令(k)(k+1)(k)(k)()()fxx= xfx一般迭代格式(0)(k) f xxf xfxxxxx設(shè) ( )存在連續(xù)二階導(dǎo)數(shù)， 滿足()0； ()0初始點接近 ，由牛頓法產(chǎn)生的 迭代序列收斂于 結(jié)論。：(0)(k)(k)(k)(k+1)(k)(k)0 0()() 1x,k

15、2 f xxxfxx= xfxkk21） 給定初始點，允許誤差） 若()，迭代停止，得 否則，進(jìn)行下一步3）計計算步驟算 ，轉(zhuǎn)步 ）：注意點：初始迭代點的選擇很重要，要靠近極小點，否則可注意點：初始迭代點的選擇很重要，要靠近極小點，否則可 能不收斂。能不收斂。 需計算一、二階導(dǎo)數(shù)，計算兩增大，實用可能不方便。需計算一、二階導(dǎo)數(shù)，計算兩增大，實用可能不方便。1432E0 m in()34121 2fxxxxx.x（）例 ， 迭 代 兩 次思考思考：實際問題如何得到初始迭代點？實際問題如何得到初始迭代點？割線法：割線法：導(dǎo)數(shù)的近似計算。導(dǎo)數(shù)的近似計算。(k)xxy(k-1)x( )y= f x切線

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

17、(1)xy( )y= f xab(2)(3)1f2f3f( )y= P x(1)(2)(3)(1)(2)(3)ab在a,b中設(shè)定三點，和123123f , f , f ,fff對應(yīng)有 且P2012xaa xa x構(gòu)造二次多項式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 x121(1)(3)1P2P2202C12Cxxaa xaa求P( )極小點，P( )311(3)(1)(2

18、)(1)2112(2)(3)C()()CCffff/其中，(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)(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)(2)Pf x比較與兩點， ( )的大小；縮短搜索區(qū)間。(2)PP2(1)(1)(2)(3)(2)P1 ff,（ ），(2)PP2(1)(2)(2)(3)(3)P3 ff,（ ），注意點注意點(1)(2)(3)1223 -; 1- ff , ff) 三個試探點 且大 小 大241242122 2442ff