運(yùn)籌學(xué)ppt課件非線性規(guī)劃課件

1、xjtu非線性規(guī)劃(wolf)the 法的收斂性( )(2)wolfe(2)k-tkf xamx 設(shè)連續(xù)可微，問題的約束系數(shù)陣 的任意 列均線性無關(guān)，且其任何基本可行解非退化，則簡約梯度法所產(chǎn)生點(diǎn)列的任一聚點(diǎn)均是的點(diǎn)。014(2,1,3,1)( ,) ,ttbxxx x從出發(fā)，初始時(shí)取運(yùn)用簡約梯度法求解下列極小化問題：例：22121231241234min( )()4(). . 21 - 0 , 0f xxxstxxxxxxx x x x xjtu非線性規(guī)劃求解線性約束優(yōu)化問題的其他方法：序列l(wèi)p方法zoutendijk可行方向法投影梯度法有效集方法及其改進(jìn)xjtu非線性規(guī)劃非線性約束問題的廣

2、義簡約梯度法：min( ). . ( )0, 1,if xstc xim (1),kx設(shè)已有可行點(diǎn)在該點(diǎn)處由各個(gè)約束函數(shù)的梯度向量1()(),()kkkkn mmaa xc xcx , , bmn mbnnxxxxxx設(shè)存在 的一個(gè)劃分：1()()(),1,bmtkkkiixibbc xc xc ximxx且假定，線性無關(guān).xjtu非線性規(guī)劃1()(),()bbkkkkm mbbxxmac xc xcx 非奇異(), , kkkn mmbnnknaaaxa各約束函數(shù)關(guān)于的偏導(dǎo)數(shù)向量由隱函數(shù)定理 kbnxxx在 的一個(gè)鄰域內(nèi)可由方程組 c(,)=0bnbnxxxx惟一的確定 為的函數(shù)：（ ）問題

3、(1)等價(jià)于下列無約束局部優(yōu)化問題： min(,)(,)n mnbnnnnxf xxfxxf x （）（）xjtu非線性規(guī)劃knnf xx假設(shè)用最速下降法求解此問題，先計(jì)算（）在處的梯度(,)(,)()ntbnbnbnxnnnbf xxf xxxg xf xxxx （）(,)0,tbbnnxc xxx由約束方程組知滿足：(,)(,)0tttbnbnbnbnc xxc xxxxxxkba由非奇異，隱函數(shù)存在定理及上述兩個(gè)等式1(,)(,)()kkkkkkkbnbnnnbnbf xxf xxg xaaxx()kkpg x 從而得搜索方向: .kpls沿進(jìn)行以確定步長xjtu非線性規(guī)劃約束的，于然而

4、由非線性性()( (),)(1)kkkkkkknnnpf xtpfxtpxtp當(dāng)沿對進(jìn)行一維極小時(shí)，難以保證問題的約束始終滿足！( )(,)0( )kkbnf xc xxtp代替ls,對在滿足方程組 的曲線上作曲線搜索.0()kkkbntxxtpx因 ()的解析表達(dá)式一般未知，且對每個(gè)試探步長，通過求解隨而變化，因此定，( ),確xjtu非線性規(guī)劃newton若用法，則有(0)kbbxx(1)( )( )( )1(,)(,)jkkbbnjjjkkbbbnxxc xxc xxtppt(1)( )1( )(,)jjkjkkbbbbnxxac xxtpnewton偽法具體迭代過程，算法？xjtu非線

5、性規(guī)劃罰函數(shù)類方法通過構(gòu)造懲罰函數(shù)，將帶約束的非線性規(guī)劃問題 轉(zhuǎn)化為無約束優(yōu)化問題思想：的求解。每當(dāng)某個(gè)點(diǎn)不可行時(shí)，就要對其處以懲罰，且懲罰值將隨著該點(diǎn)不可行性的提高而增大，但當(dāng)某點(diǎn)變?yōu)榭尚袝r(shí)，懲罰項(xiàng)的則不做任構(gòu)造原理：何懲罰。sumt因需通過調(diào)整罰參數(shù)，求解一系列無約束優(yōu)化問題才能保證得到序列無約束極小化方法原(mp)的解，故又稱不同的構(gòu)造罰函數(shù)的思路，就可導(dǎo)出不同的 具remark:體罰函數(shù)算法xjtu非線性規(guī)劃等式約束問題的平方罰函數(shù)21min ( )s.t.( )0, 1,( ,)( )( ) , 0 ( ,)jqjjkkkfxhxjqp xfxhxp xxx 罰 因 子不等式約束問題

6、的內(nèi)點(diǎn)罰函數(shù)（障礙罰函數(shù)）000m in()s.t.()0, 1,()0, 1,inifxgxipxrgxipx xjtu非線性規(guī)劃()分 倒 數(shù)罰函數(shù)11( ,)( )( )piip xf xg x1( ,)( )ln( )piip xf xg x對數(shù)罰函數(shù)000 x缺點(diǎn)：要求非空，且初始點(diǎn)迭代只能在可行域內(nèi)部、病態(tài)問題xjtu非線性規(guī)劃一般(mp)的混合罰函數(shù)min( ). .( )0, 1, ( )0, 1,ijf xstg xiph xjq (mp)( )jh x等式約束的違反程度可由來度量max0,( )ig x不等式約束的違反程度可由來度量依照懲罰項(xiàng)的構(gòu)造原理可取下列函數(shù)為懲罰項(xiàng)：

7、11( )( )max0,( ) , (1)qpjijip xh xg x11這里，為選定的常數(shù)，( )p x 通常取 = =2，連續(xù)可微xjtu非線性規(guī)劃，可定義(mp)的因此罰函數(shù)為(,)()(), (2 )pxfxpx0這里為一參數(shù)，常稱其為罰因子。()xmp當(dāng) 為的可行解時(shí)：( )0, 1, max0,( )0( )0, 1, ( )0iijjg xipg xh xjqh x( )0 ( ,)( )p xp xf x，( )0(1)p xx，若，則由式中各項(xiàng)的非負(fù)性知： 此時(shí)，對應(yīng)的 必須滿足(mp)的約束條件，即其為反之可行點(diǎn)。xjtu非線性規(guī)劃()xmp當(dāng) 不是的可行解時(shí)：則至少有

8、一個(gè)約束不成立。:1iip ，則若某個(gè)不等式約束不存在成立，使得( )0max0,( )( )0 max0,( )0 ( )0iiiig xg xg xg xp x:1jjq，則存若某個(gè)等式在約束不成立，使得( )0 ( )0 ( )0jjh xh xp x( )0( ,)( )xp xp xf x當(dāng) 不可行時(shí)，必有從而( )()( ).p xxmpp x且由的定義知， 離的可行域越遠(yuǎn)，的值越大( )xp x而當(dāng) 接近可行時(shí)，的值會(huì)變小.xjtu非線性規(guī)劃，可望通過求解下列無約綜上述束優(yōu)化問題min( ,) (3)nx rp x ().mp來找到的最優(yōu)解,( )( ),xmpxin fact若

9、對某一充分大的 ，問題(3)的最優(yōu)解屬于的可行域，則對(mp)的任一可行點(diǎn)有( ( )( ( ),)min( ,)( ,)( )nx rf xp xp xp xf x( )(mp)x這意味著為的最優(yōu)解！因在實(shí)際中確定合適大小的 比較困難，k選取一個(gè)單調(diào)增的罰函數(shù)參數(shù)序列，(3)().mp通過求解一系列形如的無約束優(yōu)化問題來尋找的解sumtxjtu非線性規(guī)劃罰函數(shù)法的迭代步驟：01:,0,0: 1.sxck1任選初始點(diǎn)初始罰因子及精度參數(shù)0，令-12:(2)( ,).kkksxp xx以為初始點(diǎn)，求由所定義的罰函數(shù)的 無約束極小點(diǎn)，記其解為13:(),(), :1, 2.kkkkksp xxmp

10、ckks若則取為原約束問題的近似 最優(yōu)解，停止；否則，令轉(zhuǎn)xjtu非線性規(guī)劃( )p x由懲罰項(xiàng)的特點(diǎn)：kk 當(dāng)?shù)臅r(shí)候，隨著的不斷增大，( ).kp x對每個(gè)不可行點(diǎn)的懲罰也不斷增大并趨于無窮(3)()kkkxx在對應(yīng)于的無約束極小化問題的最優(yōu)解處，( ()kkp x的值應(yīng)不斷減小，().kxmp從而保證 逐步趨于可行并最終達(dá)到的最優(yōu)解( )( , )p xp x由，的定義，與有極小下點(diǎn)的含義述定理：xjtu非線性規(guī)劃11k+1( ,)(2)0,( ,)( ,)kkkkkp xp xp xxx設(shè)是由式定義的罰函數(shù)，且如果和分別在 和處達(dá)到無約束全局 極小，則有th1111(,)(,)()()(

11、)()kkkkkkkkp xp xp xp xf xf x1 2min ( ) ,.nx rp x進(jìn)而，若則上述罰函數(shù)算法必有限終止()th 罰函數(shù)法的全局收斂性 1()(1)(2)( ,)kkkkkkkmpkkp xxx設(shè)存在全局最優(yōu)解，為一滿足且的正數(shù)序列，并假定對每個(gè) ，由定義的函數(shù)的整體無約束極小點(diǎn)存在，則由罰函數(shù)算法所產(chǎn)生序列的任一聚點(diǎn)必為(mp)的全局最優(yōu)解.xjtu非線性規(guī)劃:.proofkxx不妨設(shè)().xmp由假定，設(shè) 為的一個(gè)全局最優(yōu)解()0 xp x則由 的可行性知：(,)kkp xth從而由前一中所述的單調(diào)增性知()()()(,)kkkf xf xp xp x (,)k

12、kp xp這表明為一單調(diào)增且上有界序列，故必有極限，設(shè)為()(,)() (4)kkkf xp xf x因()().kkf xf xf故由單調(diào)增的性質(zhì)知亦必收斂到某一極限于是lim()lim( (,)()kkkkkkkp xp xf xpfxjtu非線性規(guī)劃k因，由上式知必有l(wèi)im()0kkp x( )( )0.kxxp xp x從而由與的連續(xù)性知，有().xmp即， 為的可行解()( )(4)xf xf x由 的最優(yōu)性知，以及( )lim()()kkf xf xf x()( )f xf x所以，()xxmp這一點(diǎn)與 的可行性表明 必為的一個(gè)全局最優(yōu)解. xjtu非線性規(guī)劃乘子(罰函數(shù))法克服罰

13、函數(shù)法需罰因子趨于無窮大才可使得罰函數(shù)極小與求解(mp)等價(jià)，以及由此帶來的病態(tài)性質(zhì)，減目的：少計(jì)算量.給某個(gè)罰函數(shù)中增加乘子項(xiàng) 乘子罰函數(shù)法在通常的lagrange函數(shù)中增加懲罰項(xiàng) 增廣lagrang想：思e函數(shù)法對一般的(mp)，其增廣lagrange函數(shù)為：21121( , , ,)( )( )( )21 max(0,( )2qqjjjjjpiiiip xf xh xh xg x xjtu非線性規(guī)劃相應(yīng)的乘子修正公式為：1max(0,(),1, (5)kkkiiigxip1(),1, (6)kkkjjjhxjq11111:,0,0,0,: 1.sxk 選取初始點(diǎn)令乘子罰函數(shù)法的迭代步驟：

14、112:min( ,), .,.nkkkkx rkksxp xxx以為初始點(diǎn)，求解無約束問題得若 c()停止112213:4104 2.kkkksxxss若 c()c() ，則轉(zhuǎn)；否則，令，轉(zhuǎn)1114:(5)(6),:1,2.kkkkskks由計(jì)算，令，轉(zhuǎn)xjtu非線性規(guī)劃11( )(max0,( ),max0,( ),( ),( )remark:pqc xg xgxh xh x)h (t乘子法的收斂性 (mp).,(mp).kkkxxx 若的可行域非空，則對任何 0，上述乘子法必有限終止.對0，算法所產(chǎn)生點(diǎn)列的任何聚點(diǎn)都是可行點(diǎn)如果有界，則 必為的最優(yōu)解xjtu非線性規(guī)劃(sqp)序列二次規(guī)劃方法克服上述方法收斂速度目的：慢的不足.newton.擬法在約束問題思：中的推廣想約束線性化，目標(biāo)函數(shù)“二次”化1min ()(,)2. . ()()0, 1, ()()0, j1,kttkkkkktiikktjjf xpp w xpstg xg xpiph xh xpq11(,)mp)lagrange ( , , )( )( )( )(,)hessen.kkkqpjjiijikkkw xl xf xh xg xxx 這里，為(的函數(shù)在處關(guān)于 的陣xjtu非線性規(guī)劃111:,: 1.n nsxbrk選取初始點(diǎn)正定陣