约束最优化方法课件.ppt

《约束最优化方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章约束最优化方法第6章约束最优化方法问题minf(x)s.t.g(x)≤0分量形式略h(x)=0约束集S={x

2、g(x)≤0,h(x)=0}6.1Kuhn-Tucker条件1.等式约束性问题的最优性条件：考虑minf(x)s.t.h(x)=0回顾高等数学中所学的条件极值：问题求z=f(x,y)极值minf(x,y)在Ф(x,y)=0的条件下，S.t.Ф(x,y)=0引入Lagrange乘子：λLagrange函数L(x,y;λ)=f(x,y)+λФ(x,y)(fgh)(fh)即6.1Kuhn-Tucker条件若

3、(x*,y*)是条件极值，则存在λ*，使fx(x*,y*)+λ*Фx(x*,y*)=0fy(x*,y*)+λ*Фy(x*,y*)=0Ф(x*,y*)=0推广到多个等式约束，可得到对于(fh)的情况：minf(x)s.t.hj(x)=0j=1,2,…,l若x*是(fh)的l.opt.,则存在υ*∈Rl使矩阵形式：分量形式：几何意义是明显的：考虑一个约束的情况：最优性条件即6.1Kuhn-Tucker条件－▽f(ӯ)ӯ▽h(ӯ)h(x)－▽f(x*)▽h(x*)这里x*—l.opt.▽f(x*)与▽h(x*)共线，而ӯ

4、非l.opt.▽f(ӯ)与▽h(ӯ)不共线。6.1Kuhn-Tucker条件2.不等式约束问题的Khun-Tucker条件考虑问题minf(x)s.t.gi(x)≤0i=1,2,…,m设x*∈S={x

5、gi(x)≤0i=1,2,…,m}令I={i

6、gi(x*)=0i=1,2,…,m}称I为x*点处的起作用集（紧约束集）。如果x*是l.opt.,对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：(fg)g2(x)=0x*g1(x)=0g1(x*)=0,g1为起作用约束6.1Kuhn-Tucker条件特别地

7、，有如下特征：如图(看书上)在x*：▽f(x*)+u*▽g(x*)=0，u*>0要使函数值下降，必须使g(x)值变大，则在ӯ点使f(x)下降的方向（－▽f(ӯ)方向）指向约束集合内部，因此ӯ不是l.opt.。▽g(ӯ)－▽f(ӯ)X*－▽f(x*)▽g(x*)6.1Kuhn-Tucker条件定理（最优性必要条件):（K-T条件）问题(fg),设S={x

8、gi(x)≤0},x*∈S,I为x*点处的起作用集，设f,gi(x),i∈I在x*点可微，gi(x),iI在x*点连续。向量组{▽gi(x*),i∈I}线性无关。

9、如果x*——l.opt.那么，u*i≥0,i∈I使6.1Kuhn-Tucker条件123412g1=0g2=0g4=0x1g3=0x2x*▽g2(x*)▽g1(x*)－▽f(x*)(3,2)T6.1Kuhn-Tucker条件用K-T条件求解6.1Kuhn-Tucker条件6.1Kuhn-Tucker条件可能的K-T点出现在下列情况：①两约束曲线的交点：g1与g2,g1与g3,g1与g4,g2与g3,g2与g4,g3与g4。②目标函数与一条曲线相交的情况：g1，g2,g3,g4对上述每一个情况容易求得满足(1)~(6

10、)的点(x1,x2)T及乘子u1,u2,u3,u4,当满足ui≥0时，即为K-T点。下面举几个情况：●g1与g2交点：x=(2,1)T∈S,I={1,2}则u3=u4=0解6.1Kuhn-Tucker条件●●6.1Kuhn-Tucker条件6.1Kuhn-Tucker条件3.一般约束问题的Kuhn-Tucker条件6.1Kuhn-Tucker条件6.2既约梯度法1.解线性约束问题的既约梯度法6.2既约梯度法6.2既约梯度法6.2既约梯度法6.2既约梯度法6.2既约梯度法6.2既约梯度法算法(看书)：x(1)∈S,k

11、=1k=k+1Jk={j

12、xj为x(k)中最大m个正分量之一}B=[…,aj(j∈Jk),…]N=[…,aj(jŒJk),…]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.3罚函数法6.3罚函数法6.3罚函数法图示6.3罚函数法2.罚函数法：（fgh）6.3罚函数法6.3罚函数法算法初始x(1),μ1>0,β>1,ε>0,k=1以x(k)为初始点，解Minf(

13、x)+μα(x)得到，x(k+1)μkα(x(k+1))<εY停；x(k+1)—l.opt.Nμk+1=βμkk=k+16.3罚函数法3.闸函数法（内点罚函数法）6.3罚函数法6.3罚函数法6.3罚函数法6.3罚函数法算法x(1)∈S0,μ1>0β∈(0,1)ε>0,k=1Minf(x)+μkB(x)s.t.x∈S0从x(k）出发，求得，x(k+1)μkB(