优化理论第6章约束.ppt

《优化理论第6章约束.ppt》由会员分享，可在线阅读，更多相关《优化理论第6章约束.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第 六六 章章约束最优化方法约束最优化方法第六章第六章 约束最优化方法约束最优化方法 问题问题 min f(x)s.t.g(x)0 分量形式略分量形式略 h(x)=0 约束集约束集 S=x|g(x)0,h(x)=0 6.1 Kuhn-Tucker 条件条件一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件：考虑考虑 min f(x)s.t.h(x)=0 回顾高等数学中所学的条件极值：回顾高等数学中所学的条件极值：问题问题 求求z=f(x,y)极值极值 min f(x,y)在在(x,y)=0的条件下。的条件下。S.t.(x,y)=0 引入引入Lagrange乘子：乘子：Lagran

2、ge函数函数 L(x,y;)=f(x,y)+(x,y)(fgh)(fh)即第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件：(续续)若若(x*,y*)是条件极值，则存在是条件极值，则存在*，使，使 fx(x*,y*)+*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.,则存在则存在*R

3、l使使 矩阵形式：矩阵形式：分量形式：一、等式约束性问题的最优性条件：一、等式约束性问题的最优性条件：(续续)几何意义是明显的：考虑一个约束的情况：几何意义是明显的：考虑一个约束的情况：最优性条件即：最优性条件即：第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件-f()h()h(x)-f(x*)h(x*)这里 x*-l.opt.f(x*)与h(x*)共线，而非l.opt.f()与h()不共线。第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件二、不等式约束问题的二、不等式约束问题的Khun-Tucker条

4、件：条件：考虑问题考虑问题 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.,对每一个约束函数来说，只有当它是起作用约对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：束时，才产生影响，如：(fg)g2(x)=0 x*g1(x)=0g1(x*)=0,g1为起作用约束第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件二、不等式约束问题的二、不

5、等式约束问题的Khun-Tucker条件：条件：（续）（续）特别特别 有如下特征：如图有如下特征：如图 在在x*：f(x*)+u*g(x*)=0 u*0 要使函数值下降，必须使要使函数值下降，必须使g(x)值变大，则值变大，则 在在 点使点使f(x)下降的方向（下降的方向（-f()方向）指向约束集合内方向）指向约束集合内部，因此部，因此不是不是l.opt.l.opt.。g()-f()X*-f(x*)g(x*)第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）定理（最

6、优性必要条件）：定理（最优性必要条件）：（K-T条件）条件）问题问题(fg),设设S=x|gi(x)0,x*S,I为为x*点处的起作用集，点处的起作用集，设设f,gi(x),i I在在x*点可微，点可微，gi(x),i I在在x*点连续。点连续。向量组向量组gi(x*),i I线性无关。线性无关。如果如果x*-l.opt.那么，那么，u*i0,i I使使第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）123412g1=0g2=0g4=0 x1g3=0 x2x*g2

7、(x*)g1(x*)-f(x*)(3,2)T第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）用用K-T条件求解：条件求解：第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件

8、：（续）（续）可能的可能的K-T点出现在下列情况：点出现在下列情况：两约束曲线的交点：两约束曲线的交点：g1与与g2,g1与与g3,g1与与g4,g2与与g3,g2与与g4,g3与与g4。目标函数与一条曲线相交的情况：目标函数与一条曲线相交的情况：g1，g2,g3,g4 对每一个情况求得满足对每一个情况求得满足(1)(6)的点的点(x1,x2)T及乘子及乘子u1,u2,u3,u4,验证当满足可得，且验证当满足可得，且ui 0时，即为一个时，即为一个K-T点。点。下面举几个情况：下面举几个情况：g1与与g2交点：交点：x=(2,1)TS,I=1,2 则则u3=u4=0 解解第六章第六章 6.1

9、Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件二、不等式约束问题的二、不等式约束问题的Khun-Tucker条件：条件：（续）（续）第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件三、一般约束问题的三、一般约束问题的Kuhn-Tucker 条件条件第六章第六章 6.1 Kuhn-Tucker 6.1 Kuhn-Tucker 条件条件条件条件三、一

10、般约束问题的三、一般约束问题的Kuhn-Tucker 条件条件(续续)第六章第六章 6.2 6.2 既约梯度法既约梯度法既约梯度法既约梯度法一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法第六章第六章 6.2 6.2 既约梯度法既约梯度法既约梯度法既约梯度法一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）第六章第六章 6.2 6.2 既约梯度法既约梯度法既约梯度法既约梯度法一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）第六章第六章 6.2 6.2 既约梯度法既约梯度法既约梯度法既约梯度法一、解线性约束问题的既约梯度法一、解线性约束问

11、题的既约梯度法（续）（续）第六章第六章 6.2 6.2 既约梯度法既约梯度法既约梯度法既约梯度法一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）第六章第六章 6.26.2解线性约束问题的既约梯度法解线性约束问题的既约梯度法解线性约束问题的既约梯度法解线性约束问题的既约梯度法 （续）（续）（续）（续）第六章第六章 6.2 6.2 既约梯度法既约梯度法既约梯度法既约梯度法一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）第六章第六章 6.2 6.2 既约梯度法既约梯度法既约梯度法既约梯度法算法：算法：x(1)S,k=1k=k+1Jk=j|xj为x(k)

12、中最大m个正分量之一B=,aj(jJk),N=,aj(jJk),YNT=NfT(x(k)-BfT(x(k)B-1NdB=-B-1NdN解得 x(k+1)=x(k)+kdd=0?YNStop;x(k)K-T点 第六章第六章 6.2 6.2 既约梯度法既约梯度法既约梯度法既约梯度法一、解线性约束问题的既约梯度法一、解线性约束问题的既约梯度法（续）（续）第六章第六章 6.2 6.2 既约梯度法既约梯度法既约梯度法既约梯度法二、广义既约梯度法二、广义既约梯度法（续）（续）第六章第六章 6.2 6.2 既约梯度法既约梯度法既约梯度法既约梯度法二、广义既约梯度法二、广义既约梯度法（续）（续）第六章第六章

13、6.3 6.3罚函数法罚函数法罚函数法罚函数法第六章第六章 6.3 6.3罚函数法罚函数法罚函数法罚函数法 1.1.罚函数概念罚函数概念罚函数概念罚函数概念 （续）（续）（续）（续）第六章第六章 6.3 6.3 罚函数法罚函数法罚函数法罚函数法 1.1.罚函数概念罚函数概念罚函数概念罚函数概念 （续）（续）（续）（续）图示图示图示图示第六章第六章 6.3 6.3罚函数法罚函数法罚函数法罚函数法2.罚函数法罚函数法：（fgh）第六章第六章 6.3 6.3罚函数法罚函数法罚函数法罚函数法2.罚函数法罚函数法：（续）（续）第六章第六章 6.3 6.3 罚函数法罚函数法罚函数法罚函数法 2.2.罚函数

14、法罚函数法罚函数法罚函数法：（续）（续）（续）（续）算法：算法：初始x(1),10,1,0,k=1以x(k)为初始点，解min f(x)+(x)得到，x(k+1)k(x(k+1)0,0,1,0,k=1min f(x)+k B(x)s.t.x S0从x(k）出发，求得，x(k+1)k B(x(k+1)yes停；x(k+1)解Nok+1=k k=k+1第六章第六章 6.3 6.3 罚函数法罚函数法罚函数法罚函数法 3.3.闸函数法：闸函数法：闸函数法：闸函数法：（续）（续）（续）（续）第六章第六章 6.3 6.3 罚函数法罚函数法罚函数法罚函数法4.罚函数法与闸函数法的缺点：罚函数法与闸函数法的缺点：1当罚函数法（闸函数法）的当罚函数法（闸函数法）的 （0+）时，惩罚项时，惩罚项 +0或或0+形式，在计算上有困难；形式，在计算上有困难；2计算一系列无约束问题，故计算量大。计算一系列无约束问题，故计算量大。5.乘子法：乘子法：第六章第六章 6.3 6.3 罚函数法罚函数法罚函数法罚函数法5.乘子法：乘子法：（续）（续）第六章第六章 6.3 6.3 罚函数法罚函数法罚函数法罚函数法 5.5.乘子法：乘子法：乘子法：乘子法：（续）（续）（续）（续）