最优化方法(约束优化问题的最优性条件)

1、最优化方法补充内容10约束优化问题的最优性条件约束优化问题的最优性条件先看等式约束问题先看等式约束问题回顾以前学的知识什么定理？推广到一般的情况几何解释几何解释二阶充分条件二阶充分条件不等式约束问题不等式约束问题不等式约束问题和等式约束问题之不等式约束问题和等式约束问题之间是否存在什么关系？间是否存在什么关系？有效约束和非有效约束有效约束和非有效约束再换句话说，不等式约束问题的在最优解处的某再换句话说，不等式约束问题的在最优解处的某个小邻域内，看以看成等式约束问题个小邻域内，看以看成等式约束问题回想最优解的定义，可行的概念对回想最优解的定义，可行的概念对于不等式约束是怎么样的概念？于不等式约束

2、是怎么样的概念？一一个个可可行行方方向向。处处的的为为则则称称有有使使得得对对任任意意的的，实实数数为为一一个个向向量量。如如果果存存在在，设设可可行行方方向向：000,00 xdQdxdQx 0)(1xc0 x1x1d1d2d2d。可行域为0)(|xcxQ0)(. .)(minxctsxf是是可可行行方方向向？如如何何判判断断一一个个向向量量是是否否可行方向。的是点则有，如果对任意的向量。给定的有效约束指标集为记点给定点定理xddxcxIidxIxQxTi,0)()()(,1：证明证明有有则则对对任任意意的的。令令, )(0,xIitdtxx )|()()() (2tdodxctxcxcTi

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

4、*)()()(*)(*3xxxxIixcxxIixcxfxIQxii0)()(0)(dxfxIidxcTTi0)()(0)(dxfxIidxcTTi 无解 有解锥和锥和 Farkas引理引理Gordan引理引理处没有可行下降方向。点）的局部极小点，则在是约束极值问题（续。如果处连在点处可微，在点和是其有效约束指标集。，设定理*1*)*)()(*)*)()()(*)(*3xxxxIixcxxIixcxfxIQxii解释解释Fritz-John一阶必要条件一阶必要条件举例验证举例验证KT条件条件 KKT最优化条件是Karush1939以及Kuhn和Tucker1951先后独立发表出來的。这组最优化

5、条件在Kuhn和Tucker 发表之后才逐渐受到重视，因此许多书只记载成Kuhn-Tucker 最优化条件 (Kuhn-Tucker conditions)。 凸锥中凸锥中最优解不一定是KT点二阶充分条件二阶充分条件凸规划问题的充分条件凸规划问题的充分条件KT条件就是最优条件条件就是最优条件验证验证KT点点验证KT点的步骤 小结 1 化为标准形式化为标准形式 2 验证约束成立验证约束成立 并且求得有效约束并且求得有效约束 3 约束规范约束规范 4 一阶条件方程一阶条件方程 例如例如 5 验证不等式约束互补条件、乘子的非负性验证不等式约束互补条件、乘子的非负性 6结论结论0)()()(*22*1

6、1* xcxcxf 点的计算点的计算TK . 3求约束极值问题求约束极值问题例例004. .)866(5 . 0)(min2121212221xxxxtsxxxxxf。点点的的TK 解：解：。3,3)(21Txxxf2114)(xxxg Txg1,1)(1 。Txgxxg0,1)(,)(212 。Txgxxg1,0)(,)(323 条条件件得得由由TK 01001113332121 xx条条件件及及约约束束条条件件得得由由TK 0,4000)4(3321321212312211312211xxxxxxxxxx 以下分情况讨论：以下分情况讨论：: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 333111 x031 x013 x 矛盾。矛盾。这与这与03 :0,0)4(21 xx若若032 331211 xx21xx 421 xx若若01 321 xx4621 xx矛盾。矛盾。421 xx221 xx11 点。点。为为TKT