约束最优化条件KTT.ppt

第十三讲约束优化问题的最优性条件?凸规划问题的最优性条件?一般约束优化问题的最优性条件?约束品性1定理:凸规划问题的局部最优解必定是其整体最优解凸规划—求凸函数在凸集上的最小值问题***2min(),,,.()(-)0,nTfxxDRfDfxDfxxxxD???????定理:)9(m},1,{,0)(},,2,1{,0)(..)(min11?????????mEjxhmIixgtsxfji考虑一般约束问题:},0)(;,0)(:{EjxhIixgxDji?????可行域:连续可微这里我们假设函数jihgf,,.为闭集显然可行域D一般约束问题的最优性条件1、,,Lagrange).()()()()()()(),,(::-乘子称为其中函数的该函数称为问题定义函数??????????????????mmmIiEjjjiiETITmnRRxhxgxfxhxgxfxLRRL???????????????????IiEjjjiixxhxgxfxL)()()(),,(???????????????????IiEjjjiixxhxgxfxL)()()(),,(????一阶必要条件11***-*****(),SFD(,)LFD(,)()Lagrange:,(,,)0mmmxjxDxDxDRRLxh??????????定理设是问题的一个局部最优解如果则存在乘子向量使得*************()0,()()0,0,()0,,(,,)()()()iiiixiijjiIjExjEgxgxiILxfxgxhx????????????????????????????这里条件—的一阶必要条件称为问题T-K-K)()(.KKT1.(9)(*点)的一个称为问题的点满足x互补松弛条件KKT(),—可能的最优解点吗??优解一定是请问约束问题的局部最定是驻点无约束问题的极值点一若函数可导KKT,,.KKT点类似于无约束问题的驻点约束问题的思考不一定啦是最优解吗?点吗是请问已知约束问题例,KKT2)(0,)()()(..)(?????????????????????xxxgxxxgtsxxf●)2,0(x1x2x)(xf?)(1xg?)(2xg?o121212021(),(),()100,(),().0210100,,fxgxgxgxgx?????????????????????????????????????????????????????解:显然线性相关令方程组无解见图线性组合表示的正不能用)(),()(),()(),()(2121xgxgxfxgxfxgxf?????????点不是故KKTx是最优解吗?x是KKT约束优化问题的局部最优定是不一解点!???*x最优解*KKTx点**SFD(,)LFD(,)xDxD?约束品性(约束规格)约束品性对研究约束问题的最优性条件非常重要.],,0(,,0.,???????????),FD(Dxx为处所有可行方向的集合记)GD(xfx集合为的所有下降方向处函数若记??),FD()(GD,,)(,**Dxxx*?即可行的方向又则在该点不存在既下降解的最优是如果容易看出条件该条件称为几何最优性●xdD●dx??可行不可行●基本概念