第五章约束问题的最优化方法讲课教案

1、第七讲第七讲 约束约束(yush)(yush)非线性规非线性规划划l 约束极值及最优性条件(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)的最优性条件的最优性条件2第二页，共63页。 0)(0)(0)(xhxhxhiii约约束束极极值值问问题题也也可可记记为为0)(s.t.)(min xgxf ljxgmixhxfji,2,10)(,2,10)(s.t.)(min3第三页，共63页。2 约束约束(yush)极值及最优性条件极值及最优性条件Kuhn-Tucker 条件条件（1 1）等式）等式(dngsh)(dngsh)约束性问题的最优性条件约束性问题的最优性条件 考虑 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*是其的最优解是其的最优解 , 则存在则存在(cnzi)* Rl 使使 ljxhxfyxyxyxfyxyxfyxjyyxx, 2 , 1, 0)(s.t.)(min0),(0),(),(0),(),(),(*分分量量形形式式：到到对对于于等等式式约约束束的的情情况况推推广广到到多多元元情情况况，可可得

4、得，使使得得是是条条件件极极值值，则则存存在在若若 5第五页，共63页。 几何意义(yy)：考虑一个约束的情况：x ljjjxhxf1*)(*)( 最优性条件最优性条件(tiojin)(tiojin)即：即： ljjjxhxf1*0)()( )(xh)(*xh )(*xf 不不共共线线，与与非非最最优优共共线线，而而与与最最优优，这这里里) () ()()(*xhxfxxhxfx ) (xf )(xh 6第六页，共63页。一一个个可可行行方方向向。处处的的为为则则称称有有使使得得对对任任意意的的，实实数数为为一一个个向向量量。如如果果存存在在，设设000,00 xdQdxdQx 0)(1 xg

5、0)(2 xg0 x1x1d1d2d2d0)(s.t.)(min xgxf)1(。可行域为可行域为0)(| xgxQ(2)(2)不等式约束极值不等式约束极值(j zh)(j zh)问题的最优性条件问题的最优性条件可行方向可行方向可行方向与积极约束可行方向与积极约束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 处处连连续续。在在点点*)*)( )(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 使使其其满满足足则则存存在在一一组组实实数数的的局局部部极极小小点点，是是约约束束极极值值问问题题线线性性无无关关。若若处处连连续续在在点点处处可可微微，在在和和，设设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若若。可得可得由由00)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页。其其它它最最优优性性条条件件. 4，使使得得的的非非负负实实数数在在一一组组不不全全为为零零）的的局局部部极极小小点

15、点，则则存存问问题题（是是约约束束极极值值若若。处处连连续续在在点点处处可可微微，在在点点和和，设设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、题题（线线性性无无关关。若若处处连连续续在在点点处处可可微微，在在和和，设设iiiixxIixgxxIixgxxIixgxfQx cnlp*)(|*)( ,*)*)( )(*)*)( )()(* 点点。称称为为式式的的点点塔塔克克条条件件），满满足足条条件件（库库恩恩式式称称为为TK)(TK)( 定理(dngl) (K-T条件):23第二十三页，共63页。（一）惩罚（一）惩罚(chngf)(chngf)函数法（函数法（SUMTSUMT）二、约束极值二、约束极值(j zh)(j zh)问题的算法问题的算法 将有约束优化问题转化为一系列无约束优化问题进行将有约束优化问题转化为一系列无约束优化问题进

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也连续。也连续。连续，那么连续，那么如果如果：结论结论)(), 2 , 1()(1xpmjxgj 2)()()()()(),(max212121xgxgxgxgxgxg 事事实实上上，只只须须注注意意：0)0),(max00),(max2 xgxgjj27第二十七页，共63页。的的最最优优解解。：也也是是问问题题）则则。）（，即即有有最最优优解解）问问题题（如如果果：结结论论)(min)(, 2 , 10)()(2); )(

20、)(min: (1)2*xfAxmjxgDxxxBDxkkjkkkRxn 。所以所以。的最优解的最优解）是（是（因为因为：证明证明nkkkkRxkRxxxxBxn , )()()(min:)(* 。所以所以）（即即又又0) )(, 2 , 10)(,)(* kkjkxpmjxgDx )()()(,*kkkkxpxfxfDx 有有所以所以)(*kkx )(xk 的的最最优优解解。是是问问题题所所以以)(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)步骤（外点法）：步骤（外点法）：。精度精度），），（可取（可取，初始惩罚因子，初始惩罚因子给定初始点给定初始点0:, 010:1step110 kx .)()0),(max)()()()(min:2step1*12 kkmjjkkkRxkxxxgxfxpxfxxn，记为，记为得到极小点为得到极小点为优化问题优化问题为初始点，求解无约束为初始点，求解无约束以以 . 4step;stop)(min(,)(,)(3step*否则转否则转的最优解，的最优解，）：）：就是问题（就是问题（）则则即即如果如果：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 算算法法求求解解可可用用无无约约束束优优化化问问题题的的中中，在在矩矩阵阵的的条条件件数数越越坏坏）。的的越越大大，求求解解困困难难（无无约约束束优优化

23、化问问题题造造成成不不宜宜取取的的过过大大。否否则则会会一一开开始始在在算算法法中中，Hesse)()(min(c)xxkkkRxkn .)(, 2 , 1|)(|)(b)* xpmjxgDxkkjk）或或（用用在在实实际际计计算算中中，判判断断（4 4）应注意）应注意(zh y)(zh y)的的问题问题惩惩罚罚项项：惩惩罚罚因因子子：惩惩罚罚函函数数：增增广广函函数数通通常常称称：)(,)(,)()d(xpxpxkkk 32第三十二页，共63页。02s.t.)1()(min2 xxxf问问题题函函数数法法）求求解解如如下下优优化化试试用用外外点点法法（外外部部惩惩罚罚 2if )2(12if

24、)1(222xxxxxk ）（22)0 , 2min(1)()( xxxxkkk ）（如如下下：构构造造增增广广函函数数解：例: 2if )2(2122if12)(xxxxxdxxdkk ）（）（0)2(212:0)( xxdxxdkk ）（可可得得由由33第三十三页，共63页。的的最最优优解解。，问问题题这这就就是是对对于于固固定定的的所所以以)(min121)(*xxxkRxkkkkkn 解解。就就是是所所求求原原问问题题的的最最优优，*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、限点点一一定定是是所所列列点点法法产产生生的的点点上上的的连连续续函函数数，则则由由外外都都是是）（和和）（、设设结结论论), 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)非空，否则算法无法运行。这样一来内点法只对不等式约束的优化问题才可能有效。38第三十八页，共63页。, )()(xqxf(x)kk 构造函数构造函数mixgxfi, 1,0)(s.t.)(min 考虑如下优化问题：考虑如下优化问题：0)()()()(min:21 kkkRxxqxfxn 转化为无约束优化问题转化为无约束优化问题（3

28、 3）算法）算法(sun (sun f)f)分析分析DxxqDxxqxq if)(2intif0)(1:)(）（）（满足满足其中其中39第三十九页，共63页。等等或或等等或或 mjjmjjmjmjjxgxqxgxqxgxqxgxqj11121)(ln()()(1ln)(;)(1)()(1)(。惩惩罚罚项项：惩惩罚罚因因子子障障碍碍函函数数：增增广广函函数数通通常常称称：)( ,)(,)(xqxqxkkk （常常取取前前两两种种）一一般般取取以以下下形形式式的的函函数数)(xq40第四十页，共63页。转转因子的缩小系数）因子的缩小系数）为惩罚为惩罚这里这里（可取（可取给定给定2step, 1:,

29、1:4step11 kkkkkk 。否则转否则转的最优解，的最优解，）：）：（就是问题就是问题则则如果如果4step;stop)(min,)(:3step11xfAxxqDxkkk （4 4）算法）算法(sun f)(sun f)步骤（内点步骤（内点法）：法）：。精精度度）（可可取取，初初始始惩惩罚罚因因子子给给定定初初始始点点0:, 0,1,0int:1step110 kDx 。，记记为为得得到到其其最最优优解解优优化化问问题题为为初初始始点点，求求解解无无约约束束以以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求求得得出出发发从从 42第四十二页，共63页。01s.t.31)(min3 xxxf问问题题函函数数法法）求求解解如如下下优优化化试试用用内内点点法法（内内部部惩惩罚罚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.求求问问题题的的极极小小点点。的的任任何何极极限限点点一一定定是是所所产产生生的的点点列列连连续续函函数数，则则由由内内点点法法

32、上上的的都都是是）（、设设结结论论), 1()(2.knjxRmjxgxf 因而计算量大。因而计算量大。计算一系列无约束问题计算一系列无约束问题有困难；有困难；形式，在计算上形式，在计算上或或项项）时，惩罚）时，惩罚（的的当外点法（或内点法）当外点法（或内点法） ,. 2)0)(0)(0 . 1 xqxpkk 45第四十五页，共63页。(7)(7)内、外点法的优缺点的比较内、外点法的优缺点的比较(bjio)(bjio)1. x(0)S 02.等式约束不适用等式约束不适用3.障碍函数障碍函数(hnsh)B(x) 在在S 0的可的可微阶数与微阶数与gi(x)相同相同(可选用的无约束可选用的无约束最

33、优化方法广最优化方法广)4.迭代中迭代中x（k）R （随时可取（随时可取x（k）x*）5.非凸规划适用非凸规划适用1.任意任意x(0)Rn2.等式约束适用等式约束适用(shyng)3.惩罚项的二阶偏导在惩罚项的二阶偏导在S的边的边界上不存在界上不存在 4.5.非凸规划适用非凸规划适用(shyng)内点法内点法外点法外点法迭代中迭代中x（k）R 46第四十六页，共63页。 约约束束构构成成。是是一一个个集集合合，常常由由简简单单nlnnRDDxRRhxhRRfxf:0)(s.t.:)(min6. 乘子法乘子法 liiixhvxfvxL1)()(),(:)(Lagrangexf函函数数代代替替用用

34、为罚因子。为罚因子。为乘子，为乘子，其中：其中：llliiiliiiRRvxhxhvxfvx 121)()()(),(乘子罚函数乘子罚函数(hnsh):(hnsh):乘子罚函数与乘子罚函数与LangrangeLangrange函数及惩罚函数及惩罚(chngf)(chngf)函数的区别：多一项。函数的区别：多一项。 (1)(1)等式等式(dngsh)(dngsh)约束约束47第四十七页，共63页。为为罚罚因因子子。为为乘乘子子，其其中中：llliiiliiiRuRvxhuxhvxfvx 121)()()(),( ,2,1 ,0,s.t.),(min)1()()( kxDxuvxkkk得得到到求求

35、解解 。及及调调整整否否则则及及乘乘子子得得到到解解若若)()()()1()1(;0)(kkkkkvvxxh 乘子罚函数(hnsh):48第四十八页，共63页。解解。的的最最优优解解，即即原原问问题题的的存存在在时时，当当存存在在可可以以证证明明： 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转转令令若若转转若若否否则则，计计算算就就是是最最优优解解，则则如如果果kkkkkkuurrxhxhxxh 算法算法(sun f)(sun f)步骤（乘子罚函数步骤（乘子罚函数法）：法）：。令令精精度度常常数数可可取取及及其其放放大大系系数数初初始始罚罚因因子子，初初始始乘乘子子向向量量给给定定初初始始点点1:,0 ),1 ,0(),102(1,:1step)1()1(0 kruvx 。，记记为为得得到到其其最最优优解解优优化化问问题题为为初初始始点点，求求解解无无约约束束以以kkk

37、liikliikikkRxkxvuxxhuxhvxfuvxxn),()()()(),(min:2step)()(*12)(1)()()(1 50第五十页，共63页。解：1. 惩罚函数(hnsh)法。对于惩罚函数(hnsh)例： 问题(wnt) 的最优解为的最优解为x x* * =(0.25, 0.75), =(0.25, 0.75),分别分别(fnbi)(fnbi)用惩罚函数法和乘子法用惩罚函数法和乘子法 求它求它的迭代点列。的迭代点列。 可求得最优解为：可求得最优解为： 2. 乘子法。对于乘子罚函数乘子法。对于乘子罚函数可求得最优解为：可求得最优解为：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)约束非线性规划其中：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