第五章約束問題的最優(yōu)化方法講課教案

1、第七講第七講 約束約束(yush)(yush)非線性規(guī)非線性規(guī)劃劃l 約束極值及最優(yōu)性條件(tiojin)l 等式約束l 不等式約束l 一般約束問題l 約束極值問題的算法l 外點法l 內點法l 乘子法1第一頁，共63頁。 ljxgmixhtsxfji,2,10)(,2,10)(.)(min, 0)(,0)(| xgxhxQ令令為為此此約約束束極極值值問問題題的的稱稱Q,) )(, )(, )()(,) )(, )(, )()(2121TlTmxgxgxgxgxhxhxhxh 記記約束極值問題可記為則 0)(0)(.)(minxgxhtsxf可可行行域域。1 1、約束、約束(yush)(yush

2、)極值問極值問題的表示題的表示一一 、約束極值問題、約束極值問題(wnt)(wnt)的最優(yōu)性條件的最優(yōu)性條件2第二頁，共63頁。 0)(0)(0)(xhxhxhiii約約束束極極值值問問題題也也可可記記為為0)(s.t.)(min xgxf ljxgmixhxfji,2,10)(,2,10)(s.t.)(min3第三頁，共63頁。2 約束約束(yush)極值及最優(yōu)性條件極值及最優(yōu)性條件Kuhn-Tucker 條件條件（1 1）等式）等式(dngsh)(dngsh)約束性問題的最優(yōu)性條件約束性問題的最優(yōu)性條件 考慮 min f(x) s.t. h(x)=0 回顧高等數學中所學的條件(tiojin

3、)極值： 問題 求 z = f(x,y)極值，在(x,y)=0的條件(tiojin)下。 即： min f(x,y) s.t. (x,y)=0 引入Lagrange乘子： Lagrange函數 L(x,y;)= f(x,y)+ (x,y)4第四頁，共63頁。 ljjjxhxf1*0)()( 若若x*是其的最優(yōu)解是其的最優(yōu)解 , 則存在則存在(cnzi)* Rl 使使 ljxhxfyxyxyxfyxyxfyxjyyxx, 2 , 1, 0)(s.t.)(min0),(0),(),(0),(),(),(*分分量量形形式式：到到對對于于等等式式約約束束的的情情況況推推廣廣到到多多元元情情況況，可可得

4、得，使使得得是是條條件件極極值值，則則存存在在若若 5第五頁，共63頁。 幾何意義(yy)：考慮一個約束的情況：x ljjjxhxf1*)(*)( 最優(yōu)性條件最優(yōu)性條件(tiojin)(tiojin)即：即： ljjjxhxf1*0)()( )(xh)(*xh )(*xf 不不共共線線，與與非非最最優(yōu)優(yōu)共共線線，而而與與最最優(yōu)優(yōu)，這這里里) () ()()(*xhxfxxhxfx ) (xf )(xh 6第六頁，共63頁。一一個個可可行行方方向向。處處的的為為則則稱稱有有使使得得對對任任意意的的，實實數數為為一一個個向向量量。如如果果存存在在，設設000,00 xdQdxdQx 0)(1 xg

5、0)(2 xg0 x1x1d1d2d2d0)(s.t.)(min xgxf)1(?？尚杏驗榭尚杏驗?)(| xgxQ(2)(2)不等式約束極值不等式約束極值(j zh)(j zh)問題的最優(yōu)性條件問題的最優(yōu)性條件可行方向可行方向可行方向與積極約束可行方向與積極約束7第七頁，共63頁。處的積極約束。處的積極約束。是點是點則稱則稱，如果，如果對于不等式約束對于不等式約束設點設點xxgxgxgQxiii0)(,0)(0)(, 約束指標集。約束指標集。處的積極處的積極為點為點稱稱記記xxIlixgixIi)(, 1,0)(|)( 的積極約束指標集。的積極約束指標集。，求點，求點令令。設設xxxxgxx

6、xgxxxgT)22,22(0)(,01)(,02)解：解：,022)22(2)(21 xg,01)22()22()(222 xg積極約束積極約束例或 起作用約束(yush)（緊約束(yush)積極約束(yush)有效約束(yush)）。8第八頁，共63頁。022)(3 xg。2,1)( xI1x2xO0)(1 xg0)(2 xg0)(3 xgx如何判斷如何判斷(pndun)一個方向是可一個方向是可行方向行方向?9第九頁，共63頁。有有則則對對任任意意的的。令令, )(0,xIitdtxx )|()()() (2tdodxgtxgxgTiii )|()(2tdodxg

7、tTi 0 為可行方向。為可行方向。即即dQx, 處的可行下降方向。為點則稱又是該點的下降方向，處的可行方向，既是點，如果給定向量，設點xdxddQx 證明(zhngmng):定理定理(dngl)1:可行可行(kxng)下降方向下降方向:的可行方向。的可行方向。是點是點則則有有如果對任意的如果對任意的，。給定向量。給定向量的積極約束指標集為的積極約束指標集為記點記點給定點給定點xddxgxIidxIxQxTi,0)()()(, 10第十頁，共63頁。處的可行下降方向。處的可行下降方向。是點是點則向量則向量滿足滿足，如果，如果向量向量。給定。給定的積極約束指標集為的積極約束指標集為記點記點給定點

8、給定點xddxfxIidxgddxIxQxTTi 0)()(0)()(,是是其其積積極極約約束束指指標標集集。，設設*)(*xIQx 定理(dngl)2:定理(dngl)3:證略極值(j zh)點的必要條件:處處可可微微，在在點點和和*)*)( )()(xxIixgxfi 處處連連續(xù)續(xù)。在在點點*)*)( )(xxIixgi 處處沒沒有有可可行行下下降降方方向向。點點的的局局部部極極小小點點，則則在在是是約約束束極極值值問問題題如如果果*)1(*xx11第十一頁，共63頁。塔塔克克條條件件）條條件件（庫庫恩恩 TK3.。處處不不存存在在下下降降方方向向則則在在點點的的局局部部極極小小點點是是約

9、約束束極極值值問問題題點點是是其其積積極極約約束束指指標標集集設設dxxxI*,)1(*,*)(分析：。，使使下下式式成成立立可可知知，不不存存在在向向量量則則由由定定理理 0*)(*)(0*)(2dxfxIidxgdTTi為積極約束。設中只有一個指標，不妨如果)(*)() 1 (1xgxI成成立立。使使得得則則不不存存在在向向量量 0*)(0*)(1dxfdxgdTT12第十二頁，共63頁。0)(1 xg*x*)(1xg *)(xf 。則有則有0,*)(*)(1 xgxf。即即0*)(*)(1 xgxf 成成立立。使使得得則則不不存存在在向向量量 0*)(0*)(1dxfdxgdTT13第十

10、三頁，共63頁。線性無關。線性無關。和和并設并設為積極約束。為積極約束。和和中有兩個指標，不妨設中有兩個指標，不妨設如果如果*)(*)()()(*)()2(2121xgxgxgxgxI 0)(1 xg0)(2 xg*x*)(1xg *)(2xg *)(xf 。使得使得，存在存在則則*)(*)(*)(,0221121xgxgxf 14第十四頁，共63頁。0*)(*)(*)(2211 xgxgxf 線性無關。設一般情況：*)(|*)()(xIixgi 3使使得得則則存存在在非非負負實實數數),*)(xIii 0*)(*)(*)( xIiiixgxf 式式可可改改寫寫為為)2()2( lixgxgx

11、fiiiliii, 2, 1, 0, 0*)(0*)(*)(1 )3(15第十五頁，共63頁。 lilixgiii,2,1, 0,2,1,0*)( ;0*)(,0;0*)(,0 xgxgiiii 使使其其滿滿足足則則存存在在一一組組實實數數的的局局部部極極小小點點，是是約約束束極極值值問問題題線線性性無無關關。若若處處連連續(xù)續(xù)在在點點處處可可微微，在在和和，設設iiiixxIixgxxIixgxxIixgxfQx )1(*)(|*)( ,*)*)( )(*)*)( )()(* lixgxgxfiiiliii,2,1, 0,0*)(0*)(*)(1 )( 點。點。稱為稱為式的點式的點塔克條件），

12、滿足塔克條件），滿足條件（庫恩條件（庫恩式稱為式稱為TK)(TK)( 定理定理(dngl)4(K-T條件條件):16第十六頁，共63頁。 0)(0)(.s.t)(minxgxhxf問問題題對對于于有有等等式式約約束束的的極極值值)4(條條件件可可寫寫為為TK lixgxgxhuxfiiiliiimjjj,2,1, 0,0*)(0*)(*)(*)(11 )(17第十七頁，共63頁。點的計算點的計算TK 004.866)(min2121212221xxxxtsxxxxxf。點點的的TK 解：解：。Txxxf3,32)(21 , 4)(211 xxxgTxg1,1)(1 。Txgxxg0,1)( ,

13、)(212 。Txgxxg1,0)( ,)(323 例例: : 求約束求約束(yush)(yush)極值極值問題問題18第十八頁，共63頁。條條件件得得由由TK 01001113332121 xx條條件件及及約約束束條條件件得得由由TK 0,04000)4(3321321212312211312211xxxxxxxxxx 以下分情況討論：以下分情況討論：19第十九頁，共63頁。:0)1(21 xx若若?？傻每傻糜捎?0)4(1211 xx321 32 矛盾。矛盾。這與這與02 :0,0)2(21 xx若若03 332112 x022 x022 x 矛盾。矛盾。這與這與02 :0,0)3(21

14、xx若若02 0,04000)4(3321321212312211312211xxxxxxxxxx 20第二十頁，共63頁。 333111 x031 x013 x 矛盾。矛盾。這與這與03 :0,0)4(21 xx若若032 331211 xx21xx 421 xx若若01 321 xx4621 xx矛盾。矛盾。421 xx221 xx11 點。點。為為TK2,2 T 0,04000)4(3321321212312211312211xxxxxxxxxx 21第二十一頁，共63頁。其其它它最最優(yōu)優(yōu)性性條條件件. 4，使使得得的的非非負負實實數數在在一一組組不不全全為為零零）的的局局部部極極小小點

15、點，則則存存問問題題（是是約約束束極極值值若若。處處連連續(xù)續(xù)在在點點處處可可微微，在在點點和和，設設iiixxxIixgxxIixgxfQx 1*)*)( )(*)*)( )()(* 0*)(*)(*)(0 xIiiixgxf 定理定理(dngl)5(Fritz John條件條件):22第二十二頁，共63頁。 0)(0)(.s.t)(minxgxhxf)cnlp(一一般般的的約約束束極極值值問問題題 lixgxgxhuxfiiiliiimjjj,2,1, 0,0*)(0*)(*)(*)(11 )( 使使其其滿滿足足則則存存在在一一組組實實數數）的的局局部部極極小小點點，是是約約束束極極值值問問

16、題題（線線性性無無關關。若若處處連連續(xù)續(xù)在在點點處處可可微微，在在和和，設設iiiixxIixgxxIixgxxIixgxfQx cnlp*)(|*)( ,*)*)( )(*)*)( )()(* 點點。稱稱為為式式的的點點塔塔克克條條件件），滿滿足足條條件件（庫庫恩恩式式稱稱為為TK)(TK)( 定理(dngl) (K-T條件):23第二十三頁，共63頁。（一）懲罰（一）懲罰(chngf)(chngf)函數法（函數法（SUMTSUMT）二、約束極值二、約束極值(j zh)(j zh)問題的算法問題的算法 將有約束優(yōu)化問題轉化為一系列無約束優(yōu)化問題進行將有約束優(yōu)化問題轉化為一系列無約束優(yōu)化問題進

17、行(jnxng)(jnxng)求解。（求解。（Sequential Unconstrained Minimization Sequential Unconstrained Minimization Technique - SUMTTechnique - SUMT）1 1、算法思想：、算法思想：2 2、算法類型：、算法類型：q 外點法（外懲法）外點法（外懲法） q 內點法（內懲法）內點法（內懲法）24第二十四頁，共63頁。3 3、問題、問題(wnt)(wnt)：Tmxgxgxgxgxf），（這這里里)()()(0)(s.t.)(min1 mixgxfi，, 10)(s.t.)(min 可可行行點

18、點集集或或可可行行解解集集 :0)(|s.t.)(min xgxDDxxf25第二十五頁，共63頁。)(xk 算法思想：構造算法思想：構造）（且且滿足：滿足： kxDxxfxDxxfxxkkkk)()()()()()( 可可取?。?。）（）（滿足條件滿足條件其中其中DxxpDxxpxpxpxfxkk 0)(2;0)(1:)(, )()()( 4 4、外點法（外部、外點法（外部(wib)(wib)懲罰函數法）懲罰函數法）)(min)(min)(min)(minxxxxfkRxRxRxDxnnn 21 )(21k 26第二十六頁，共63頁。，事事實實上上，這這樣樣，我我們們只只需需構構造造)(xp0

19、)( xgj因為因為 mjjmjjxgxgxp12210),(max) 0),(max)(所以可設所以可設。和和滿滿足足恰恰前前面面的的條條件件顯顯然然)2()1()(xp也連續(xù)。也連續(xù)。連續(xù)，那么連續(xù)，那么如果如果：結論結論)(), 2 , 1()(1xpmjxgj 2)()()()()(),(max212121xgxgxgxgxgxg 事事實實上上，只只須須注注意意：0)0),(max00),(max2 xgxgjj27第二十七頁，共63頁。的的最最優(yōu)優(yōu)解解。：也也是是問問題題）則則。）（，即即有有最最優(yōu)優(yōu)解解）問問題題（如如果果：結結論論)(min)(, 2 , 10)()(2); )(

20、)(min: (1)2*xfAxmjxgDxxxBDxkkjkkkRxn 。所以所以。的最優(yōu)解的最優(yōu)解）是（是（因為因為：證明證明nkkkkRxkRxxxxBxn , )()()(min:)(* 。所以所以）（即即又又0) )(, 2 , 10)(,)(* kkjkxpmjxgDx )()()(,*kkkkxpxfxfDx 有有所以所以)(*kkx )(xk 的的最最優(yōu)優(yōu)解解。是是問問題題所所以以)(max)(*xfxDxk )()(xpxfk )(xf 28第二十八頁，共63頁。)x(1 )x(2 )x(f)x(k D*xx（1 1）幾何）幾何(j h)(j h)解釋解釋29第二十九頁，共6

21、3頁。（3 3）算法）算法(sun f)(sun f)步驟（外點法）：步驟（外點法）：。精度精度），），（可?。扇。跏紤土P因子，初始懲罰因子給定初始點給定初始點0:, 010:1step110 kx .)()0),(max)()()()(min:2step1*12 kkmjjkkkRxkxxxgxfxpxfxxn，記為，記為得到極小點為得到極小點為優(yōu)化問題優(yōu)化問題為初始點，求解無約束為初始點，求解無約束以以 . 4step;stop)(min(,)(,)(3step*否則轉否則轉的最優(yōu)解，的最優(yōu)解，）：）：就是問題（就是問題（）則則即即如果如果：xfAxxpDxDxkkk . 2step,

22、 1:,14step11轉轉因因子子的的放放大大系系數數）為為懲懲罰罰這這里里（可可取取給給定定： kkkkkk 30第三十頁，共63頁。yesNo1, 0 1, 0,1)1( kx 初始初始)1()( )()(min, kkkxxpxfx得到得到解解為初始點為初始點以以 )()1(kkxpopt )1( kx停停kk 11 kk外點法框圖外點法框圖(kungt)31第三十一頁，共63頁。)()()(min2step(a)xpxfxkkRxn 算算法法求求解解可可用用無無約約束束優(yōu)優(yōu)化化問問題題的的中中，在在矩矩陣陣的的條條件件數數越越壞壞）。的的越越大大，求求解解困困難難（無無約約束束優(yōu)優(yōu)化

23、化問問題題造造成成不不宜宜取取的的過過大大。否否則則會會一一開開始始在在算算法法中中，Hesse)()(min(c)xxkkkRxkn .)(, 2 , 1|)(|)(b)* xpmjxgDxkkjk）或或（用用在在實實際際計計算算中中，判判斷斷（4 4）應注意）應注意(zh y)(zh y)的的問題問題懲懲罰罰項項：懲懲罰罰因因子子：懲懲罰罰函函數數：增增廣廣函函數數通通常常稱稱：)(,)(,)()d(xpxpxkkk 32第三十二頁，共63頁。02s.t.)1()(min2 xxxf問問題題函函數數法法）求求解解如如下下優(yōu)優(yōu)化化試試用用外外點點法法（外外部部懲懲罰罰 2if )2(12if

24、)1(222xxxxxk ）（22)0 , 2min(1)()( xxxxkkk ）（如如下下：構構造造增增廣廣函函數數解：例: 2if )2(2122if12)(xxxxxdxxdkk ）（）（0)2(212:0)( xxdxxdkk ）（可可得得由由33第三十三頁，共63頁。的的最最優(yōu)優(yōu)解解。，問問題題這這就就是是對對于于固固定定的的所所以以)(min121)(*xxxkRxkkkkkn 解解。就就是是所所求求原原問問題題的的最最優(yōu)優(yōu)，*2121lim)(limlimxxxxkkkkkkk 1200 11 102 xk *xO)(xf34第三十四頁，共63頁。 0)(0)(s.t.)(mi

25、nxhxgxf pjxhmixgxfji, 1, 0)(, 1, 0)(s.t.)(minq （7 7）一般）一般(ybn)(ybn)模型的外點法模型的外點法 lkmjjlkkmjjxhxgxhxgxpk12122121)(0),(max) )() 0),(max)(的的懲懲罰罰函函數數我我們們不不難難想想到到構構造造如如下下q q 算法步驟算法步驟(bzhu)(bzhu)相同相同35第三十五頁，共63頁。）（）（）（）（）（）（有有是是由由外外點點法法產產生生的的，則則若若點點列列結結論論kkkkkkkkkxfxfxpxpxxx 11111. 求求問問題題的的極極小小點點。的的任任何何極極限

26、限點點一一定定是是所所列列點點法法產產生生的的點點上上的的連連續(xù)續(xù)函函數數，則則由由外外都都是是）（和和）（、設設結結論論), 1(), 1()(2.knkjxRlkxhmjxgxf (8)(8)算法算法(sun (sun f)f)收斂性收斂性36第三十六頁，共63頁。5 5、內點法（障礙、內點法（障礙(zhng i)(zhng i)函數法）函數法）內點集內點集邊界點集邊界點集 DDDintD Dint（1 1）集合）集合(jh)(jh)結構結構; 0)(,| xgjxDj使得使得至少存在一個至少存在一個。,0)(|intjxgxDj 37第三十七頁，共63頁。（2 2）算法）算法(sun f

27、)(sun f)思想思想 內點法（障礙函數法）的迭代點是在可行域點集內部移動的，對接近可行域邊界上的點施加越來越大的懲罰(chngf)，對可行域邊界上的點施加無限大的懲罰(chngf)，這好比邊界是一道障礙物，阻礙迭代點穿越邊界。 內點法要求可行點集的內點集合(jh)非空，否則算法無法運行。這樣一來內點法只對不等式約束的優(yōu)化問題才可能有效。38第三十八頁，共63頁。, )()(xqxf(x)kk 構造函數構造函數mixgxfi, 1,0)(s.t.)(min 考慮如下優(yōu)化問題：考慮如下優(yōu)化問題：0)()()()(min:21 kkkRxxqxfxn 轉化為無約束優(yōu)化問題轉化為無約束優(yōu)化問題（3

28、 3）算法）算法(sun (sun f)f)分析分析DxxqDxxqxq if)(2intif0)(1:)(）（）（滿足滿足其中其中39第三十九頁，共63頁。等等或或等等或或 mjjmjjmjmjjxgxqxgxqxgxqxgxqj11121)(ln()()(1ln)(;)(1)()(1)(。懲懲罰罰項項：懲懲罰罰因因子子障障礙礙函函數數：增增廣廣函函數數通通常常稱稱：)( ,)(,)(xqxqxkkk （常常取取前前兩兩種種）一一般般取取以以下下形形式式的的函函數數)(xq40第四十頁，共63頁。轉轉因子的縮小系數）因子的縮小系數）為懲罰為懲罰這里這里（可?。扇〗o定給定2step, 1:,

29、1:4step11 kkkkkk 。否則轉否則轉的最優(yōu)解，的最優(yōu)解，）：）：（就是問題就是問題則則如果如果4step;stop)(min,)(:3step11xfAxxqDxkkk （4 4）算法）算法(sun f)(sun f)步驟（內點步驟（內點法）：法）：。精精度度）（可可取取，初初始始懲懲罰罰因因子子給給定定初初始始點點0:, 0,1,0int:1step110 kDx 。，記記為為得得到到其其最最優(yōu)優(yōu)解解優(yōu)優(yōu)化化問問題題為為初初始始點點，求求解解無無約約束束以以1*1)()(1)()()()(min:2step kkmjjkkkRxkxxxgxfxqxfxxn 41第四十一頁，共63

30、頁。內點法框圖內點法框圖(kungt)1 kkkk 1 )()1(kkxqyesNoopt )1( kx停停1, 0 ,1 , 0 , 0,10)0( kSx )1()(0 , s.t.)()(min kkkxxSxxqxf求求得得出出發(fā)發(fā)從從 42第四十二頁，共63頁。01s.t.31)(min3 xxxf問問題題函函數數法法）求求解解如如下下優(yōu)優(yōu)化化試試用用內內點點法法（內內部部懲懲罰罰11)()(3 xxxxkkk 如如下下：構構造造增增廣廣函函數數kxx )1(可得：可得：由由0)1()(22 xxdxxdkk 。所以所以因為因為kxxx )1(1例解43第四十三頁，共63頁。)411

31、(21)411(211kkkxx 所所以以因因為為負負根根不不滿滿足足條條件件，因因此此1 2 3 x 1x2x3x*x1)411(21limlim1* kkkkxx 由由此此可可以以得得到到：331)(xxf o144第四十四頁，共63頁。（5 5）算法）算法(sun f)(sun f)收斂性：收斂性：（6 6）罰函數法的缺點）罰函數法的缺點(qudin)(qudin)。）（）（有有是是由由內內點點法法產產生生的的，則則若若點點列列結結論論kkkkkxxx 111.求求問問題題的的極極小小點點。的的任任何何極極限限點點一一定定是是所所產產生生的的點點列列連連續(xù)續(xù)函函數數，則則由由內內點點法法

32、上上的的都都是是）（、設設結結論論), 1()(2.knjxRmjxgxf 因而計算量大。因而計算量大。計算一系列無約束問題計算一系列無約束問題有困難；有困難；形式，在計算上形式，在計算上或或項項）時，懲罰）時，懲罰（的的當外點法（或內點法）當外點法（或內點法） ,. 2)0)(0)(0 . 1 xqxpkk 45第四十五頁，共63頁。(7)(7)內、外點法的優(yōu)缺點的比較內、外點法的優(yōu)缺點的比較(bjio)(bjio)1. x(0)S 02.等式約束不適用等式約束不適用3.障礙函數障礙函數(hnsh)B(x) 在在S 0的可的可微階數與微階數與gi(x)相同相同(可選用的無約束可選用的無約束最

33、優(yōu)化方法廣最優(yōu)化方法廣)4.迭代中迭代中x（k）R （隨時可取（隨時可取x（k）x*）5.非凸規(guī)劃適用非凸規(guī)劃適用1.任意任意x(0)Rn2.等式約束適用等式約束適用(shyng)3.懲罰項的二階偏導在懲罰項的二階偏導在S的邊的邊界上不存在界上不存在 4.5.非凸規(guī)劃適用非凸規(guī)劃適用(shyng)內點法內點法外點法外點法迭代中迭代中x（k）R 46第四十六頁，共63頁。 約約束束構構成成。是是一一個個集集合合，常常由由簡簡單單nlnnRDDxRRhxhRRfxf:0)(s.t.:)(min6. 乘子法乘子法 liiixhvxfvxL1)()(),(:)(Lagrangexf函函數數代代替替用用

34、為罰因子。為罰因子。為乘子，為乘子，其中：其中：llliiiliiiRRvxhxhvxfvx 121)()()(),(乘子罰函數乘子罰函數(hnsh):(hnsh):乘子罰函數與乘子罰函數與LangrangeLangrange函數及懲罰函數及懲罰(chngf)(chngf)函數的區(qū)別：多一項。函數的區(qū)別：多一項。 (1)(1)等式等式(dngsh)(dngsh)約束約束47第四十七頁，共63頁。為為罰罰因因子子。為為乘乘子子，其其中中：llliiiliiiRuRvxhuxhvxfvx 121)()()(),( ,2,1 ,0,s.t.),(min)1()()( kxDxuvxkkk得得到到求求

35、解解 。及及調調整整否否則則及及乘乘子子得得到到解解若若)()()()1()1(;0)(kkkkkvvxxh 乘子罰函數(hnsh):48第四十八頁，共63頁。解解。的的最最優(yōu)優(yōu)解解，即即原原問問題題的的存存在在時時，當當存存在在可可以以證證明明： Dxtsvxv.),(min Dxxhxgxf 0)( 0)(s.t.)(min(2)等式等式(dngsh)、不等式、不等式(dngsh)約束約束 0,|0)(0)(s.t.)(minzDxzxDxxhzxgxf引引入入松松弛弛變變量量49第四十九頁，共63頁。轉轉計算計算2step, 1:, 2 , 1, )(:4step)()()1( kkmj

36、xhuvvjkkjkj.4step,4step,|,)(|/|)(|;stop,|)(|:3step)()1(1轉轉令令若若轉轉若若否否則則，計計算算就就是是最最優(yōu)優(yōu)解解，則則如如果果kkkkkkuurrxhxhxxh 算法算法(sun f)(sun f)步驟（乘子罰函數步驟（乘子罰函數法）：法）：。令令精精度度常常數數可可取取及及其其放放大大系系數數初初始始罰罰因因子子，初初始始乘乘子子向向量量給給定定初初始始點點1:,0 ),1 ,0(),102(1,:1step)1()1(0 kruvx 。，記記為為得得到到其其最最優(yōu)優(yōu)解解優(yōu)優(yōu)化化問問題題為為初初始始點點，求求解解無無約約束束以以kkk

37、liikliikikkRxkxvuxxhuxhvxfuvxxn),()()()(),(min:2step)()(*12)(1)()()(1 50第五十頁，共63頁。解：1. 懲罰函數(hnsh)法。對于懲罰函數(hnsh)例： 問題(wnt) 的最優(yōu)解為的最優(yōu)解為x x* * =(0.25, 0.75), =(0.25, 0.75),分別分別(fnbi)(fnbi)用懲罰函數法和乘子法用懲罰函數法和乘子法 求它求它的迭代點列。的迭代點列。 可求得最優(yōu)解為：可求得最優(yōu)解為： 2. 乘子法。對于乘子罰函數乘子法。對于乘子罰函數可求得最優(yōu)解為：可求得最優(yōu)解為：1 s.t. 6121min212221

38、 xxxx )1(6121)(2212221 xxuxxxk 816,812* kkkkkuuuux )1()1(6121)(221212221 xxuxxvxxxkk 81)2(3,812* kkkkkkkuvuuvux得下表得下表取取, 1 , )1(, 0,205. 0)(2)(110 kxxuvvvukkkkkkk51第五十一頁，共63頁。 從表中可見，從表中可見，xk*比比 xk 近近于于x*的速度慢得多，用乘子的速度慢得多，用乘子法迭代法迭代(di di)6次就達到懲次就達到懲罰函數法迭代罰函數法迭代(di di)15次的次的效效 這里，懲罰因子在懲罰函這里，懲罰因子在懲罰函數法中

39、要增大到數法中要增大到u153276.8，而在乘子法中只要增大到而在乘子法中只要增大到u6=6.4 相比之下，乘子法不需過相比之下，乘子法不需過分地增大懲罰因子，確實比分地增大懲罰因子，確實比懲罰函數法有效很多懲罰函數法有效很多. 52第五十二頁，共63頁。Matlab求解(qi ji)約束非線性規(guī)劃其中：x、b、beq、lb、ub是向量，A、Aeq為矩陣(j zhn)，C(x)、Ceq(x)是約束向量的函數，f(x)為目標函數，f(x)、C(x)、Ceq(x)可以是非線性函數。 53第五十三頁，共63頁。函數(hnsh) fmincon格式 x = fmincon(fun,x0,A,b)x

40、= fmincon(fun,x0,A,b,Aeq,beq)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x,fval = fmincon()x,fval,exitflag = fmincon()x,fval,exitflag,output = fmincon()x,fval,exitflag,output,lambda = fmincon()x,fval,exitflag,

41、output,lambda,grad = fmincon()x,fval,exitflag,output,lambda,grad,hessian = fmincon()54第五十四頁，共63頁。解: (1)寫成標準(biozhn)形式： 0054632t.s.2121xxxx 2100 xx22212121212minxxxxf 例例10,54632s.t.21212min 212121222121 xxxxxxxxxxf55第五十五頁，共63頁。(2)先建立(jinl)M-文件 fun1.m: function f=fun1(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1

42、/2)*x(2)2(3)再建立(jinl)主程序youh1.m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; LB=0;0; UB=; x,fval=fmincon(fun1,x0,A,b,Aeq,beq,LB,UB)(4)在命令窗口(chungku)中輸入youh1,得運算結果為： x = 0.7647 1.0588 fval = -2.029456第五十六頁，共63頁。0)1(221 xx63221 xx解：約束條件的標準(biozhn)形式為（1）在MATLAB編輯器中建立非線性約束(yush)函數文件：function c, ceq=nlcon (x)c

43、=(x(1)-1)2-x(2);ceq= ; %無等式約束(yush)57第五十七頁，共63頁。（1 1）在）在MATLABMATLAB編輯器中建立非線性約束函數編輯器中建立非線性約束函數(hnsh)(hnsh)文件：文件：function c, ceq=nlcon (x)function c, ceq=nlcon (x)c=(x(1)-1)2-x(2);c=(x(1)-1)2-x(2);ceq= ; %ceq= ; %無等式約束無等式約束（2 2）在命令窗口鍵入如下命令或建立）在命令窗口鍵入如下命令或建立MM文件：文件：fun2=x(1)2+x(2)2-x(1)fun2=x(1)2+x(2)

44、2-x(1)* *x(2)-2x(2)-2* *x(1)-5x(1)-5* *x(2); %x(2); %目標函數目標函數x0=0 1;x0=0 1;A=-2 3; %A=-2 3; %線性不等式線性不等式(dngsh)(dngsh)約束約束b=6;b=6;Aeq= ; %Aeq= ; %無線性等式無線性等式(dngsh)(dngsh)約束約束beq= ;beq= ;lb= ; % xlb= ; % x沒有下、上界沒有下、上界ub= ;ub= ;x,fval,exitflag,output,lambda,grad,hessianx,fval,exitflag,output,lambda,grad,hessian=fmincon(fun2,x0,A,b,Aeq,beq,lb,ub,nlcon