《非线性约束优化精选文档.ppt》由会员分享，可在线阅读，更多相关《非线性约束优化精选文档.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、非线性约束优化本讲稿第一页，共二十页 高等数学中所学的条件极值：高等数学中所学的条件极值：一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件：考虑考虑 min f(x)s.t.h(x)=0 问题问题:在在(x,y)=0的条件下的条件下,求求z=f(x,y)极值极值.min f(x,y)。s.t.(x,y)=0 引入引入Lagrange乘子：乘子：Lagrange函数函数 L(x,y;)=f(x,y)+(x,y)本讲稿第二页，共二十页一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件：(续续)若若(x*,y*)是条件极值，则存在是条件极值，则存在*，使，使 fx(x*,y
2、*)+*x(x*,y*)=0 fy(x*,y*)+*y(x*,y*)=0 (x*,y*)=0 推广到推广到多元情况多元情况，可得到对于，可得到对于(fh)的情况：的情况：min f(x)s.t.hj(x)=0 j=1,2,l 若若x*是是(fh)的的l.opt.,则存在则存在*Rl使使 以及以及 hj(x)=0，j=1,2,l本讲稿第三页，共二十页一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件：(续续)几何意义是明显的：考虑一个约束的情况：几何意义是明显的：考虑一个约束的情况：最优性条件即：最优性条件即：-f()h()h(x)f(x*)h(x*)这里这里 x*-l.opt.f(
3、x*)与与h(x*)共线，而共线，而非非l.opt.f()与与h()不共线。不共线。本讲稿第四页，共二十页一一 等式约束下的拉格朗日乘子算法等式约束下的拉格朗日乘子算法考虑等式约束问题:令拉格朗日函数:则等式约束下规划问题转化成无约束问题:min L(X,)该问题有极值点的必要条件为:本讲稿第五页，共二十页充分条件充分条件:如果如果 且行列式方程且行列式方程:所有根所有根Zj0(j=1,2,n-l)，则，则X*为局部极小点；反为局部极小点；反之所有之所有Zj0，为局部极大点；有正有负非极值点，为局部极大点；有正有负非极值点本讲稿第六页，共二十页例题4-1用拉格朗日乘子算法求解:解:令 极大点的
4、必要条件:对于得到的三个根。使用充分条件检验如下：本讲稿第七页，共二十页计算:展开z的(n-l)=(2-1)=1次多项式方程，得本讲稿第八页，共二十页一个信息处理技术中重要的例子一个信息处理技术中重要的例子求最优隶属度函数求最优隶属度函数）背景介绍聚类分析）背景介绍聚类分析）目标函数符号说明）目标函数符号说明构造拉日函数：构造拉日函数：最优化的一阶必要条件为最优化的一阶必要条件为 代回上式进入到约束条件：代回上式进入到约束条件：得得所以所以本讲稿第九页，共二十页FCM的中心迭代过程的中心迭代过程本讲稿第十页，共二十页2)不等式约束问题的不等式约束问题的Khun-Tucker条件：条件：考虑问题
5、考虑问题 min f(x)s.t.gi(x)0 i=1,2,m 设设 x*S=x|gi(x)0 i=1,2,m,并令并令 I=i|gi(x*)=0，i=1,2,m 称称I为为 x*点处的起作用集（紧约束集）。点处的起作用集（紧约束集）。如果如果x*是是l.opt.,对每一个约束函数来说，只有当它是起作用约束时，对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：才产生影响，如：g2(x)=0 x*g1(x)=0g1(x*)=0,g1为起作用约束，为起作用约束，约束集已知时回归到含等式优化问题约束集已知时回归到含等式优化问题问题问题:事先并不知道约束集？事先并不知道约束集？本讲稿第十一
6、页，共二十页 定理（任意情况的定理（任意情况的最优性最优性必要条件必要条件）：（）：（K-T条件）条件）问题问题(fg),设设=x|gi(x)0，,x*,I为为x*点处的起作用集，设点处的起作用集，设f,gi(x),i I在在x*点可微，点可微，gi(x),i I在在x*点连点连续。续。向量组向量组gi(x*),i I线性无关。线性无关。构造拉日函数：构造拉日函数：如果如果x*-l.opt.那么，那么，u*i0,使得使得）驻点条件：）驻点条件：）互补条件：）互补条件：）非负条件：）非负条件：）不等式约束：）不等式约束：）等式约束：）等式约束：说明说明：）如果是）如果是max问题等，要改变叙述。
7、问题等，要改变叙述。）在一定条件下上面叙述变成充要条件。）在一定条件下上面叙述变成充要条件。本讲稿第十二页，共二十页二阶充分条件二阶充分条件设拉格朗日函数为为非线性规划的严格局部极小点的充分条件：）为点；）拉日函数的海瑟矩阵在方向正定，并且方向满足下列等式：本讲稿第十三页，共二十页例求解不等式约束问题的例求解不等式约束问题的K-T点，并判断是否为局部极小点，并判断是否为局部极小解：解：）条件）条件：考虑两种情况考虑两种情况：）局部最小判别：）局部最小判别：自行看课本自行看课本本讲稿第十四页，共二十页3 3罚函数法（外点法）罚函数法（外点法）罚函数法（外点法）罚函数法（外点法）本讲稿第十五页，共
8、二十页例题用外点法求解例题用外点法求解解：都是不等式约束。定义外部罚函数解：都是不等式约束。定义外部罚函数解法一解法一可行域可行域不可行域不可行域本讲稿第十六页，共二十页解法二迭代法本讲稿第十七页，共二十页3.内点罚函数法内点罚函数法与外点法对应，但只适合不等式约束问题与外点法对应，但只适合不等式约束问题本讲稿第十八页，共二十页3.闸函数法：（续）闸函数法：（续）因此，求解下列序贯无约束规划问题因此，求解下列序贯无约束规划问题例题用内点法求解例题用内点法求解解：构造罚函数：解：构造罚函数：1）微分法：）微分法：解得解得 让，得让，得本讲稿第十九页，共二十页4.罚函数类算法与闸函数法的缺点罚函数类算法与闸函数法的缺点：1当罚函数法（闸函数法）的当罚函数法（闸函数法）的 （0+）时，时，惩罚项惩罚项 +0或或0+形式，在计算上有困难；形式，在计算上有困难；2计算一系列无约束问题，故计算量大。计算一系列无约束问题，故计算量大。本讲稿第二十页，共二十页