第六章约束最优化方法

第六章约束优化问题的最优性条件Page2Page3先看等式约束问题Page4回顾以前学的知识Page5Page6Page7什么定理？Page8推广到一般的情况Page9Page10几何解释Page11二阶充分条件Page12不等式约束问题不等式约束问题和等式约束问题之间是否存在什么关系？Page13有效约束和非有效约束再换句话说，不等式约束问题的在最优解处的某个小邻域内，可以看成等式约束问题Page14例如考虑由约束221122123142()10()0()0()0cxxxcxxxcxxcxx所确定的可行集,对于点(1,0)22(,)22TATBxx有效的约束分别为1412()()()()cxcxcxcx，和，Page15回想最优解的定义，可行的概念对于不等式约束是怎么样的概念？一个可行方向。处的为则称有使得对任意的，实数为一个向量。如果存在，设可行方向：000,],0[0xdQdxdQx0)(1xc0x1x1d1d2d2d。可行域为}0)(|{xcxQ0)(..)(minxctsxfPage16是可行方向？如何判断一个向量是否可行方向。的是点则有，如果对任意的向量。给定的有效约束指标集为记点给定点定理xddxcxIidxIxQxTi,0)()()(,1：证明有则对任意的。令,)(0,'xIitdtxx)||||()()()'(2tdodxctxcxcTiii)||||()(2tdodxctTi0为可行方向。即dQx,'Page17行下降方向。处的可为点的下降方向，则称的可行方向，又是该点处既是点，如果给定向量，设点可行下降方向：xdxddQx处的可行下降方向。是点则向量满足，如果向量。给定的积极约束指标集为记点给定点定理xddxfxIidxcddxIxQxTTi0)()(0)()(,2Page18极值点的必要条件：处没有可行下降方向。点）的局部极小点，则在是约束极值问题（续。如果处连在点处可微，在点和是其有效约束指标集。，设定理*1**)*)(()(*)*)(()()(*)(*3xxxxIixcxxIixcxfxIQxii0)()(0)(dxfxIidxcTTi0)()(0)(dxfxIidxcTTi无解有解Page19锥和Farkas引理Page20Page21Gordan引理Page22处没有可行下降方向。点）的局部极小点，则在是约束极值问题（续。如果处连在点处可微，在点和是其有效约束指标集。，设定理*1**)*)(()(*)*)(()()(*)(*3xxxxIixcxxIixcxfxIQxii解释Page23Fritz-John一阶必要条件Page24Page25i.5.6Fritz-JohnFritz-JohnLagrange这个定理给出了（6）在最优点处所满足的必要条件，即公式（6），今后满足条件的点称为点。其中称为乘子Page26举例验证Page27Page28KT条件KT最优化条件是Karush[1939]以及Kuhn和Tucker[1951]先后独立发表出來的。这组最优化条件在Kuhn和Tucker发表之后才逐渐受到重视，因此许多书只记载成「Kuhn-Tucker最优化条件(Kuhn-Tuckerconditions)」。Page29Page30Page31凸锥中最优解不一定是KT点Page32Page33Page34二阶充分条件Page35凸规划问题的充分条件KT条件就是最优条件Page36解：将原问题转化为标准形式：2322215.05.1minxxxxfs.t.03)(2322211xxxxc,0)(212xxxc0)(13xxc,0)(24xxc,0)(35xxc验证KT点2322215.05.1maxxxxxfs.t.03)(2322211xxxxc,0)(212xxxc0)(13xxc,0)(24xxc,0)(35xxc试验证Tx)1,1,1(*是否为KT点。Page37将Tx)1,1,1(*带入约束条件可知满足约束条件并且有效约束集合为}2,1{*ITxf)2,1,3()(，Txc)2,2,2()(1，Txc)0,1,1()(2且Txc)2,2,2()(1与Txc)0,1,1()(2线性无关。令0)()()(*22*11*xcxcxf求得11，12即)()()(*22*11*xcxcxf对于不等式约束)(2xc对应的Lagrange乘子02且0)(*22xc故Tx)1,1,1(*为KT点。Page38验证KT点的步骤小结1化为标准形式2验证约束成立并且求得有效约束3约束规范4一阶条件方程例如5验证不等式约束互补条件、乘子的非负性6结论0)()()(*22*11*xcxcxfPage39点的计算TK.3求约束极值问题例004..)866(5.0)(min2121212221xxxxtsxxxxxf。点的TK解：。]3,3[)(21Txxxf2114)(xxxgTxg]1,1[)(1。Txgxxg]0,1[)(,)(212。Txgxxg]1,0[)(,)(323Page40条件得由TK01001113332121xx条件及约束条件得由TK0,,,,4000)4(3321321212312211312211xxxxxxxxxxPage41: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以下分情况讨论：Page42333111x031x013x矛盾。这与03:0,0)4(21xx若032331211xx21xx421xx若01321xx4621xx矛盾。421xx221xx11点。为TKT]2,2[0,,,,4000)4(3321321212312211312211xxxxxxxxxxPage43二阶充分条件对于一般约束优化问题)(minxfs.t.0)(xciEi0)(xciIi)(xf，)(xci二阶连续可微(ii)**x为KT点，且严格互补松弛条件成立；(ii)对于子空间},0)(|{**IixcdRdMiTn中的任意0d有0),(**2dxLdxT则*x是严格局部最优解Page44