運籌學(xué) 非線性規(guī)劃2

1、xjtu非線性規(guī)劃1,.kkkkkkkkxpxxxp：給定如何確定移動步長，目使得的()().kkkkf xpf x一般要求：,k選擇步長使其滿足四 線性搜索方法線性搜索方法的分類:精確線性搜索法不精確線性搜索法直接搜索法插值法精確線性搜索0min ( ) ( )()kkkf xp 0() = min()kkkkkkf xpf xpxjtu非線性規(guī)劃極值的必由要條件：( )()0)kktkf xpp ( ) 因為難于找到的全局極小點)urry.c(k ：取( )的最小正根作為的極小點準(zhǔn)則min()0,0kktkkf xppin practice,( ).f x 除非特殊情況(如為二次函數(shù))，尋

2、求 ( )的精確極小點是不可能在內(nèi)限步實現(xiàn)的有數(shù)值分析 非線性方程求根的方法 newton法 割線法 簡單迭代法等k應(yīng)為下列方程的非負(fù)根xjtu非線性規(guī)劃hesse精確線性搜索往往要用到梯度，二階陣計算量大 對某些非光滑函數(shù)、導(dǎo)數(shù)表達(dá)式很復(fù)雜難于應(yīng)用搜索區(qū)間的確定 , 0,) ka b要求事先知道包含的某個區(qū)間.k直接搜索法、插求值法搜索區(qū)間 , ( )a b 在上求的(近似)極小點.*( )f xx對一般的(mp),在包含局部最優(yōu)解 的某個區(qū)域上為凸函數(shù)*( )()kktf xp 在包含極小點的某個區(qū)間上關(guān)于 為凸.xjtu非線性規(guī)劃 , a b確定的基本思想：()(0,)()acb a 假

3、設(shè)為連續(xù)函數(shù)，逐步確定三點使得滿足( )( )( ),acb().ab 則 在與之 間 必 有的 一 個 極 小 點001010hh 給定0,計算 (),取步長,令=,計算 ().012121,h 若 ()()，則令=，計算 ();2313,().h 否則,令=計算1( ) ()()kkk 如此繼續(xù)，因為，局部凸函數(shù)，使故必存在某個21021, , abca b 若 ()()，則令 =xjtu非線性規(guī)劃11, , kkkabca b0101()(),()(or) 若開始時有若，0101()() 令，1010()() ，1010()() ，212().h 令=，計算21()(), 若201,.a

4、bc=2323until for som,():e kh 如否則,令=計算,。此繼續(xù)1()()kk 11,.kkkabcxjtu非線性規(guī)劃() 如 果 可 以 利 用的 導(dǎo) 數(shù) ：*() ,xa b 在 包 含的 極 小 點的 區(qū) 間的 端 點 處 ， 必 有 ：( )0,( )0ab00,0h給定取初始點，010()0,h 若，則取010()0,h若， 則 取xjtu非線性規(guī)劃*( ) ).or(ab ：已知包含的極小點的搜索區(qū)間 ，要求求為單谷函數(shù)要() , a b 函數(shù)稱為是區(qū)間上的單谷函數(shù)，*( )ba baa b 若存在， 使得在上 ，嚴(yán)格遞減，且在， 上嚴(yán)格遞增，區(qū)間 ， 稱為 (

5、 )的單谷區(qū)間.0.618法(黃金分割法)精確線性搜索法不用導(dǎo)數(shù)、簡單易行直接搜索法defxjtu非線性規(guī)劃1212 , ,a b:在搜索區(qū)間上選取兩個對稱點，：基本思想1212(), (),b,0.618,a 比較的大小：刪除左半?yún)^(qū)間 ，或右半?yún)^(qū)間，刪除后的新區(qū)間的長度是原來的倍,新區(qū)間包含原區(qū)間中的兩個對稱點中的一個關(guān)于這一點，再選取一個對稱點根據(jù)新的兩個對稱點處的函數(shù)值來決定新區(qū)間的刪除直至新區(qū)間的長度小于預(yù)先指定的精度為止.xjtu非線性規(guī)劃0000*,( ),kkkkaa bbabkabab 記設(shè)區(qū)間經(jīng) 次刪除后的區(qū)間為的極小點121221, 1kkkkkkkkkkkkababba在

6、中選取兩個對稱點使（）（）21i.e.kkkkkkkkabbaba12 kkkkkkkkbbaaba（）（）推導(dǎo)過程: from which we have(2)xjtu非線性規(guī)劃12(),()kk 計算1222211()(),kkkkkkkkkkbaaab 若，刪除右半?yún)^(qū)間(，保留，記111111112,().kkkkkkkab 在新區(qū)間上，希望能利用處的函數(shù)值故取，再依對稱的原則確定+1+1+1+121+1+1+1+1 .kkkkkkkkabbaba同時希望兩個新的分點保持原來的比例 ，即+1+1211+1+122()kkkkkkkkkkkkkkaababbaaa而由(1)和(2)得()1

7、()kkkkkkbababaxjtu非線性規(guī)劃1210 0,51 0.6180339890.618 .2因為故取正根,即令從以上兩個等式可得：15.2 每次分割總按比例 =0.618來選點;每次只需計算一個新點處的函數(shù)值;新區(qū)間的長度是老區(qū)間長度的0.618倍.xjtu非線性規(guī)劃1211() (),)ontheotherhan,d,kkkkkkab 若在開始時刪去左半?yún)^(qū)間，保留，+1+1+1112=kkkkkkabb令，則+1+1+1+12=+kkkkaba（）.12+1+1+1+11211()()kkkkkkba 比較兩點，處的函數(shù)值，重復(fù)上述過程，直到note: , ()na bnba區(qū)間經(jīng) 次縮小后，最終搜索區(qū)間的長度為512在古代，人們認(rèn)為按0.618的比例分割線段是最協(xié)調(diào)的， 每次區(qū)間的收縮 收 比為，故0.618法 勝似黃金，故斂速度是線性稱為黃的.的金分割法.xjtu非線性規(guī)劃00( ) , ,0.618033989,0;a baa bbk 確定的初始搜索區(qū)間記給定，011(-)(),kkkkkbba 22(-)(),kkkkkaba 122212111111111111()()()(),(),(),kkkkkkkkkkkkkkkaabbba 若,則,計算轉(zhuǎn)s4;12212+1111211+111112()(),()(),(), ()