第五章约束问题的最优化方法

1第七讲约束非线性规划约束极值及最优性条件等式约束不等式约束一般约束问题约束极值问题的算法外点法内点法乘子法2ljxgmixhtsxfji,,2,10)(,,2,10)(..)(min,}0)(,0)(|{xgxhxQ令为此约束极值问题的称Q,))(,,)(,)(()(,))(,,)(,)(()(2121TlTmxgxgxgxgxhxhxhxh记约束极值问题可记为则0)(0)(..)(minxgxhtsxf可行域。1、约束极值问题的表示一、约束极值问题的最优性条件30)(0)(0)(xhxhxhiii约束极值问题也可记为0)(s.t.)(minxgxfljxgmixhxfji,,2,10)(,,2,10)(s.t.)(min42约束极值及最优性条件——Kuhn-Tucker条件（1）等式约束性问题的最优性条件考虑minf(x)s.t.h(x)=0回顾高等数学中所学的条件极值：问题求z=f(x,y)极值，在ф(x,y)=0的条件下。即：minf(x,y)s.t.ф(x,y)=0引入Lagrange乘子：λLagrange函数L(x,y;λ)=f(x,y)+λф(x,y)5ljjjxhxf1***0)()(若x*是其的最优解,则存在υ*∈Rl使ljxhxfyxyxyxfyxyxfyxjyyxx,,2,1,0)(s.t.)(min0),(0),(),(0),(),(),(***************分量形式：：到对于等式约束的情况推广到多元情况，可得，使得是条件极值，则存在若6几何意义：考虑一个约束的情况：x'ljjjxhxf1**)(*)(最优性条件即：ljjjxhxf1***0)()()(xh)(*xh)(*xf不共线，与非最优共线，而与最优，这里)'()'(')()(***xhxfxxhxfx)'(xf)'(xh7一个可行方向。处的为则称有使得对任意的，实数为一个向量。如果存在，设000,],0[0xdQdxdQx0)(1xg0)(2xg0x1x1d1d2d2d0)(s.t.)(minxgxf)1(。可行域为}0)(|{xgxQ(2)不等式约束极值问题的最优性条件可行方向:①可行方向与积极约束:8处的积极约束。是点则称，如果对于不等式约束设点xxgxgxgQxiii0)(,0)(0)(,约束指标集。处的积极为点称记xxIlixgixIi)(,}1,0)(|{)(的积极约束指标集。，求点令。设xxxxgxxxgxxxgT)22,22(0)(,01)(,02)(13222122211解：,022)22(2)(21xg,01)22()22()(222xg积极约束:例:或起作用约束（紧约束\积极约束\有效约束）。9。022)(3xg。}2,1{)(xI1x2xO0)(1xg0)(2xg0)(3xgx②如何判断一个方向是可行方向?10有则对任意的。令,)(0,'xIitdtxx)||||()()()'(2tdodxgtxgxgTiii)||||()(2tdodxgtTi0为可行方向。即dQx,'处的可行下降方向。为点则称又是该点的下降方向，处的可行方向，既是点，如果给定向量，设点xdxddQx证明:定理1:可行下降方向:的可行方向。是点则有如果对任意的，。给定向量的积极约束指标集为记点给定点xddxgxIidxIxQxTi,0)()()(,11处的可行下降方向。是点则向量满足，如果向量。给定的积极约束指标集为记点给定点xddxfxIidxgddxIxQxTTi0)()(0)()(,是其积极约束指标集。，设*)(*xIQx定理2:定理3:证略③极值点的必要条件:处可微，在点和*)*)(()()(xxIixgxfi处连续。在点*)*)(()(xxIixgi处没有可行下降方向。点的局部极小点，则在是约束极值问题如果*)1(*xx12塔克条件）条件（库恩TK3.。处不存在下降方向则在点的局部极小点是约束极值问题点是其积极约束指标集设dxxxI*,)1(*,*)(分析：。，使下式成立可知，不存在向量则由定理0*)(*)(0*)(2dxfxIidxgdTTi为积极约束。设中只有一个指标，不妨如果)(*)()1(1xgxI成立。使得则不存在向量0*)(0*)(1dxfdxgdTT130)(1xg*x*)(1xg*)(xf。则有0,*)(*)(1xgxf。即0*)(*)(1xgxf成立。使得则不存在向量0*)(0*)(1dxfdxgdTT14线性无关。和并设为积极约束。和中有两个指标，不妨设如果*)(*)()()(*)()2(2121xgxgxgxgxI0)(1xg0)(2xg*x*)(1xg*)(2xg*)(xf。使得，存在则*)(*)(*)(,0221121xgxgxf15。0*)(*)(*)(2211xgxgxf线性无关。设一般情况：}*)(|*)({)(xIixgi3使得则存在非负实数),*)((xIii0*)(*)(*)(xIiiixgxf式可改写为)2()2(lixgxgxfiiiliii,,2,1,0,0*)(0*)(*)(1)3(16lilixgiii,,2,1,0,,2,1,0*)(;0*)(,0;0*)(,0xgxgiiii使其满足则存在一组实数的局部极小点，是约束极值问题线性无关。若处连续在点处可微，在和，设iiiixxIixgxxIixgxxIixgxfQx)1(*}*)(|*)({,*)*)(()(*)*)(()()(*lixgxgxfiiiliii,,2,1,0,0*)(0*)(*)(1)(点。称为式的点塔克条件），满足条件（库恩式称为TK)(TK)(定理4(K-T条件):170)(0)(.s.t)(minxgxhxf问题对于有等式约束的极值)4(条件可写为TKlixgxgxhuxfiiiliiimjjj,,2,1,0,0*)(0*)(*)(*)(11)(18点的计算TK004..866)(min2121212221xxxxtsxxxxxf。点的TK解：。Txxxf]3,3[2)(21,4)(211xxxgTxg]1,1[)(1。Txgxxg]0,1[)(,)(212。Txgxxg]1,0[)(,)(323例:求约束极值问题19条件得由TK01001113332121xx条件及约束条件得由TK0,,,,04000)4(3321321212312211312211xxxxxxxxxx以下分情况讨论：20: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xx若020,,,,04000)4(3321321212312211312211xxxxxxxxxx21333111x031x013x矛盾。这与03:0,0)4(21xx若032331211xx21xx421xx若01321xx4621xx矛盾。421xx221xx11点。为TK]2,2[T0,,,,04000)4(3321321212312211312211xxxxxxxxxx22其它最优性条件.4，使得的非负实数在一组不全为零）的局部极小点，则存问题（是约束极值若。处连续在点处可微，在点和，设iiixxxIixgxxIixgxfQx1**)*)(()(*)*)(()()(*0*)(*)(*)(0xIiiixgxf定理5(FritzJohn条件):230)(0)(.s.t)(minxgxhxf)cnlp(一般的约束极值问题lixgxgxhuxfiiiliiimjjj,,2,1,0,0*)(0*)(*)(*)(11)(使其满足则存在一组实数）的局部极小点，是约束极值问题（线性无关。若处连续在点处可微，在和，设iiiixxIixgxxIixgxxIixgxfQxcnlp*}*)(|*)({,*)*)(()(*)*)(()()(*点。称为式的点塔克条件），满足条件（库恩式称为TK)(TK)(定理(K-T条件):24（一）惩罚函数法（SUMT）二、约束极值问题的算法将有约束优化问题转化为一系列无约束优化问题进行求解。（SequentialUnconstrainedMinimizationTechnique-SUMT）1、算法思想：2、算法类型：外点法（外惩法）内点法（内惩法）253、问题：Tmxgxgxgxgxf），，（这里)()()(0)(s.t.)(min1mixgxfi，,10)(s.t.)(min可行点集或可行解集:}0)(|{s.t.)(minxgxDDxxf26)(xk算法思想：构造）（且满足：kxDxxfxDxxfxxkkkk)()()()()()(可取：。）（）（满足条件其中DxxpDxxpxpxpxfxkk0)(2;0)(1:)(,)()()(4、外点法（外部惩罚函数法）)(min)(min)(min)(minxxxxfkRxRxRxDxnnn21)(21k27，事实上，这样，我们只需构造)(xp0)(xgj因为mjjmjjxgxgxp1221}0),({max)}0),((max{)(所以可设。和满足恰前面的条件显然)2()1()(xp也连续。连续，那么如果：结论)(),,2,1()(1xpmjxgj2)()()()()}(),({max212121xgxgxgxgxgxg事实上，只须注意：0})0),(({max0}0),(max{2xgxgjj28的最优解。：也是问题）则。）（，即有最优解）问题（如果：结论)(min)((,,2,10))(()((2);)()(min:(1)2****xfAxmjxgDxxxBDxkkjkkkRxn。所以。的最优解）是（因为：证明nkkkkRxkRxxxxBxn,)())(()(min:)(**。所以）（即又0))((,,,2,10))((,)(***kkjkxpmjxgDx))(())(())((,***kkkkxpxfxfDx有所以))((*kkx)(xk的最优解。是问题所以)(max)(*xfxDxk)()(xpxfk)(xf29)x(1