生產(chǎn)運(yùn)籌之非線性規(guī)劃的基本概念-預(yù)覽頁(yè)
【正文】 數(shù)，即有連續(xù)梯度，則梯度有以下兩個(gè)重要性質(zhì)： 性質(zhì)一 函數(shù)在某點(diǎn)的梯度不為零，則該梯度方向必與過(guò)該點(diǎn)的等值面垂直 。 ? ? 22212121 43, xxxxxxf ???新點(diǎn)是： ? ?? ? ? ? ? ? ??????????????????????????????551552242422xfxfe???????????????????????????????????5511552551552101exx? ? 52526|43 12221211 ????? xxxxxxf函數(shù)值： ? 幾個(gè)常用的梯度公式 ： ? ? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? AxxfAxxxfAxxfxxxfbxfxbxfCxfCxfTTT2 .4...20 .0,.1??????????????則對(duì)稱矩陣。在上的凸函數(shù)，或是則稱 SS ff 上是嚴(yán)格凸的。 參見(jiàn) P104例。是函數(shù)在點(diǎn)）（其中11111 )(,)()( xxxfxxfxf Tn?????? ?定理 1：（一階條件） ?上的嚴(yán)格凸函數(shù)是）（ S2 f 212112121 , ),()()()( xxSxxxfxfxxxf T ???????n=1時(shí)幾何意義：可微函數(shù)是凸的等價(jià)于切線不在函數(shù)圖像上方。上的凸函數(shù)，則是并且皆為線性函數(shù)，上的凸函數(shù)皆為若）（）（）（對(duì)于非線性規(guī)劃)( MP)(,)(g ,1 0 ,1 0 . min,(MP) iXfxhRxqjxh pixgxfjnij???????????凸規(guī)劃性質(zhì)： 定理凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。 6 非線性規(guī)劃方法概述 ?（ 2）數(shù)值方法的基本思路： 迭代 給定初始點(diǎn) x0 根據(jù) x0,依次迭代產(chǎn)生點(diǎn)列 {xk} {xk}的最后一點(diǎn)為最優(yōu)解 {xk}有限 {xk}無(wú)限 {xk}收斂于最優(yōu)解 ?迭代格式 xk xk+1 kx? kkk xx ???? 1pk kkk ptx ?? kkk x ??? 1稱 pk為第 k輪 搜索方向 ， tk為第 k輪沿 pk方向的 步長(zhǎng) 。在就是可導(dǎo)，則在若xxfxfxxf)()()( ?定義 ：特殊搜索方向 —— 下降方向 ，使得若存在設(shè) 0t,0, ????? pRpXxRX nnXtpx ?? 的可行方向。 （ ii）如果 ?? ???? )()()( 10 kxfxfxf，則稱此算法為 下降迭代算法 。 ? ? ? ? ) 1 ( ) ( k k x x ? （２）目標(biāo)函數(shù)值準(zhǔn)則： （絕對(duì)差）?；?(1),(2)和 (3)等。 ?xf一、一維最優(yōu)化問(wèn)題 1. 單峰函數(shù) 定義 ：設(shè) )(xf是區(qū)間 ],[ ba上的一元函數(shù)， x是 )(xf在 ],[ ba上的極小點(diǎn)，且對(duì)任意的 ,],[, 2121 xxbax ??有 （ a）當(dāng) xx ?2時(shí)， 。任取點(diǎn) )(xf ,],[ badc ??則有 （ 1）如果 )()( dfcf ?，則 。 ?迭代縮短 [a,b]的長(zhǎng)度。 進(jìn)退法的計(jì)算步驟 ,.1 )0( Rx ?給定初始點(diǎn) ,00 ?h初始步長(zhǎng) ,0hh ?令 ,)0()1( xx ),( )1(xf計(jì)算 .0?k并令 ,.2 )1()4( hxx ??令 ),( )4(xf計(jì)算 .1: ?? kk令 ),()(.3 )1()4( xfxf ?若，則轉(zhuǎn) 4 ，轉(zhuǎn) ,.4 )1()2( xx ?令 ,)4()1( xx ? ),()( )1()2 xfxf ? ),()( )4()1( xfxf .2,2: 轉(zhuǎn)令 hh ?如何確定包含極小點(diǎn)的一個(gè)區(qū)間？ , k若 ；則轉(zhuǎn) 6 .7否則，轉(zhuǎn),:.6 hh ??令 ,)4()2( xx ? ),()( )4()2( xfxf ?.2轉(zhuǎn) ,.7 )2((3) xx ?令 )1 ,)()1(x停止計(jì)算。1 kk bb ?? ,)()(.2 kk ff ?? ?若 ,ka則令 .k? ？與如何確定 kk ??kkkk ab ??? ??.1 比率相同， )0()(11 ???? ?? ?? kkkk abab)1( )2( ）可得：）與（由式（ 21??????????)())(1(kkkkkkkkabaaba????)3(4 件：要求其滿足以下兩個(gè)條ka kbk?ku？取值的確定?通過(guò)確定 的取值，使上一次迭代剩余的迭代點(diǎn)恰與下一次迭代的一個(gè)迭代點(diǎn)重合，從而減少算法的計(jì)算量。次迭代時(shí)有若在第 )()()2(k kuffk ??同理可得。倍k)2 15( ?其它的試探點(diǎn)算法： Fibonacci算法。 定義 稱滿足條件 （ i） F0 = F1 = 1； （ ii） 的數(shù)列 { Fn }為 Fibonacci數(shù)列。 618 . 0 1 ? ? n n F F 618 . 0 1 代替 n n F F ? 在 Fibonacci法中，第 n次迭代的搜索區(qū)間的長(zhǎng)度（記為 ）是上一次區(qū)間長(zhǎng)度的 倍 所以要使在第 n次迭代時(shí)搜索區(qū)間的長(zhǎng)度不超過(guò) ε，只需 ? 0 1 L F n ε （ ） 即可。置 k =1。的極小點(diǎn)的估計(jì)值作為以 )( xfx ])()()()()()([2 )()()()()()( )3()2()1()2()1()3()1()3()2()3()2()1()2()1()3()1()3()2( 222222xfxxxfxxxfxxxfxxxfxxxfxx???????????令 x = 3 3 2 2 1 1 2 3 3 2 2 2 2 1 1 1 1 1 1 1 1 2 1 f x f x f x x f x f x f ? 拋物線插值算法步驟： ,],[)1( )3()1( xx給定初始區(qū)間 ).()(),()( )3()2()2()1( xfxfxfxf ??設(shè) 。設(shè) 3,2,1,)()()()2( )()(2 ????? ixfxcxbxax ii??解出 。令。的極小點(diǎn)近似并用逼近用數(shù)值和導(dǎo)數(shù)， )()(,)()( xfxxfx ??)1(x )2(x )(xf )(x?*x五 . 三次插值法 設(shè) )1()()()()( )1(2)1(3)1( dxxcxxbxxax ????????令 ???????????????)()()()()()()()()2()2()1()1()2()2()1()1(xfxxfxxfxxfx????則有 ???????????????????????)()(2)(3)()()()()()()2()1()2(2)1()2()1()2()1()2(2)1()2(3)1()2()1(xfcxxbxxaxfcxfdxxcxxbxxaxfd)2( 。所以 0?b 的極小點(diǎn)。滿足條件： 0)(,0)(, )2()1()1()2( ????? xfxfxx 。停止計(jì)算，得到點(diǎn)，若。轉(zhuǎn)。6?? w 。 六、 MATLAB ? 單變量函數(shù)求最小值的標(biāo)準(zhǔn)形式為 )(min xfx21 xxx ??函數(shù) fminbnd 格式 x = fminbnd(fun,x1,x2) %返回自變量 x在區(qū)間 上函數(shù) fun取最小值時(shí) x值， fun為目標(biāo)函數(shù)的表達(dá)式字符串或 MATLAB自定義函數(shù)的函數(shù)柄。 xexxxxxf logcos)( 3 ???解： [x,fval,exitflag,output] =fminbnd(39。 演講完畢，謝謝觀看！
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1