第六章约束最优化方法讲课讲稿

1、第六章第六章约束约束(yush)优化问题的最优性条优化问题的最优性条件件第一页，共44页。Page 2第二页，共44页。Page 3第三页，共44页。Page 4第四页，共44页。Page 5第五页，共44页。Page 6第六页，共44页。Page 7什么(shn me)定理？第七页，共44页。Page 8第八页，共44页。Page 9第九页，共44页。Page 10第十页，共44页。Page 11第十一页，共44页。Page 12不等式不等式(dngsh)约束问题和等式约束问题和等式(dngsh)约束问题之间是否存在什约束问题之间是否存在什么关系？么关系？第十二页，共44页。Page 13再

2、换句话说，不等式约束问题的在最优解处的某个小邻域内，再换句话说，不等式约束问题的在最优解处的某个小邻域内， 可以可以(ky)看成等式约束问题看成等式约束问题第十三页，共44页。Page 14例如 考虑由约束221122123142( )10( )0( )0( )0c xxxcxxxcxxcxx所确定的可行集,对于点(1,0)22(,)22TATBxx 有效的约束分别为1412( )( )( )( )c xcxc xcx，和和，第十四页，共44页。Page 15一一个个可可行行方方向向。处处的的为为则则称称有有使使得得对对任任意意的的，实实数数为为一一个个向向量量。如如果果存存在在，设设可可行行

3、方方向向：000,00 xdQdxdQx 0)(1xc0 x1x1d1d2d2d。可行域为0)(|xcxQ0)(. .)(minxctsxf第十五页，共44页。Page 16是是可可行行方方向向？如如何何判判断断一一个个向向量量是是否否可行方向。的是点则有，如果对任意的向量。给定的有效约束指标集为记点给定点定理xddxcxIidxIxQxTi,0)()()(,1：证明证明有有则则对对任任意意的的。令令, )(0,xIitdtxx )|()()() (2tdodxctxcxcTiii)|()(2tdodxctTi0 为可行方向。为可行方向。即即dQx, 第十六页，共44页。Page 17行行下下

4、降降方方向向。处处的的可可为为点点的的下下降降方方向向，则则称称的的可可行行方方向向，又又是是该该点点处处既既是是点点，如如果果给给定定向向量量，设设点点可可行行下下降降方方向向：xdxddQx 处的可行下降方向。是点则向量满足，如果向量。给定的积极约束指标集为记点给定点定理xddxfxIidxcddxIxQxTTi0)()(0)()(,2第十七页，共44页。Page 18极值点的必要条件：极值点的必要条件：处没有可行下降方向。点）的局部极小点，则在是约束极值问题（续。如果处连在点处可微，在点和是其有效约束指标集。，设定理*1*)*)()(*)*)()()(*)(*3xxxxIixcxxIix

5、cxfxIQxii0)()(0)(dxfxIidxcTTi0)()(0)(dxfxIidxcTTi 无解 有解第十八页，共44页。Page 19第十九页，共44页。Page 20第二十页，共44页。Page 21第二十一页，共44页。Page 22处没有可行下降方向。点）的局部极小点，则在是约束极值问题（续。如果处连在点处可微，在点和是其有效约束指标集。，设定理*1*)*)()(*)*)()()(*)(*3xxxxIixcxxIixcxfxIQxii解释解释(jish)第二十二页，共44页。Page 23第二十三页，共44页。Page 24第二十四页，共44页。Page 25 i.5.6Fri

6、tz-JohnFritz-JohnLagrange 这这个个定定理理给给出出了了（6 6 ）在在最最优优点点处处所所满满足足的的必必要要条条件件，即即公公式式（6 6 ），今今后后满满足足条条件件的的点点称称为为点点。其其中中称称为为乘乘子子第二十五页，共44页。Page 26第二十六页，共44页。Page 27第二十七页，共44页。Page 28KT最优化条件(tiojin)是Karush1939以及Kuhn和Tucker1951先后独立发表出來的。这组最优化条件(tiojin)在Kuhn和Tucker 发表之后才逐渐受到重视，因此许多书只记载成Kuhn-Tucker 最优化条件(tioji

7、n) (Kuhn-Tucker conditions)。 第二十八页，共44页。Page 29第二十九页，共44页。Page 30第三十页，共44页。Page 31凸锥中凸锥中最优解不一定(ydng)是KT点第三十一页，共44页。Page 32第三十二页，共44页。Page 33第三十三页，共44页。Page 34第三十四页，共44页。Page 35第三十五页，共44页。Page 36验证验证(ynzhng)KT点点第三十六页，共44页。Page 37第三十七页，共44页。Page 381 化为标准形式2 验证约束成立 并且(bngqi)求得有效约束3 约束规范4 一阶条件方程 例如5 验证不

8、等式约束互补条件、乘子的非负性6结论0)()()(*22*11* xcxcxf 第三十八页，共44页。Page 39点的计算点的计算TK . 3求约束极值问题求约束极值问题例例004. .)866(5 . 0)(min2121212221xxxxtsxxxxxf。点点的的TK 解：解：。3,3)(21Txxxf2114)(xxxg Txg1,1)(1 。Txgxxg0,1)(,)(212 。Txgxxg1,0)(,)(323 第三十九页，共44页。Page 40条条件件得得由由TK 01001113332121 xx条条件件及及约约束束条条件件得得由由TK 0,4000)4(332132121

9、2312211312211xxxxxxxxxx 第四十页，共44页。Page 41: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,4000)4(3321321212312211312211xxxxxxxxxx 以下分情况讨论：以下分情况讨论：第四十一页，共44页。Page 42 333111 x031 x013 x 矛盾。矛盾。这与这与03 :0,0)4(21 xx若若032 331211 xx21xx 421 xx