《约束最优化方法.ppt》由会员分享，可在线阅读，更多相关《约束最优化方法.ppt（42页珍藏版）》请在三一办公上搜索。
1、,约束最优化方法,约束最优化方法,问题 min f(x)s.t.g(x)0 分量形式略 h(x)=0 约束集 S=x|g(x)0,h(x)=0 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乘子：Lagrange函数 L(x,y;)=f(x,y)+(x,y),一、等式约束性问题的最优性条件：(续)若(x*,y*)是条件极值，则存在*，使 fx(x*,y*)+*x(x*,y*)=0 fy
2、(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使 矩阵形式：,一、等式约束性问题的最优性条件：(续)几何意义是明显的：考虑一个约束的情况：最优性条件即：,二、不等式约束问题的Khun-Tucker条件：考虑问题 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.,对每一个约束函数来说，只
3、有当它是起作用约束时，才产生影响，如：,g2(x)=0,Kuhn-Tucker 条件,二、不等式约束问题的Khun-Tucker条件：（续）特别 有如下特征：如图 在x*：f(x*)+u*g(x*)=0 u*0 要使函数值下降，必须使g(x)值变大，则 在 点使f(x)下降的方向（-f()方向）指向约束集合内部，因此不是l.opt.。,g(),二、不等式约束问题的Khun-Tucker条件：（续）定理（最优性必要条件）：（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
4、 I线性无关。如果x*-l.opt.那么，u*i0,i I使,二、不等式约束问题的Khun-Tucker条件：（续）,二、不等式约束问题的Khun-Tucker条件：（续）用K-T条件求解：,二、不等式约束问题的Khun-Tucker条件：（续）,二、不等式约束问题的Khun-Tucker条件：（续）可能的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-
5、T点。下面举几个情况：g1与g2交点：x=(2,1)TS,I=1,2 则u3=u4=0 解,二、不等式约束问题的Khun-Tucker条件：（续）,二、不等式约束问题的Khun-Tucker条件：（续）,三、一般约束问题的Kuhn-Tucker 条件,三、一般约束问题的Kuhn-Tucker 条件(续),一、解线性约束问题的既约梯度法,一、解线性约束问题的既约梯度法（续）,一、解线性约束问题的既约梯度法（续）,一、解线性约束问题的既约梯度法（续）,一、解线性约束问题的既约梯度法（续）,一、解线性约束问题的既约梯度法（续）,算法：,x(1)S,k=1,k=k+1,Jk=j|xj为x(k)中最大m
6、个正分量之一B=,aj(jJk),N=,aj(jJk),YNT=NfT(x(k)-BfT(x(k)B-1NdB=-B-1NdN,解得 x(k+1)=x(k)+kd,d=0?,Y,N,Stop;x(k)K-T点,一、解线性约束问题的既约梯度法（续）,二、广义既约梯度法（续）,二、广义既约梯度法（续）,3罚函数法 1.罚函数概念（续）,3 罚函数法 1.罚函数概念（续）,图示,3罚函数法,2.罚函数法：（fgh）,3罚函数法,2.罚函数法：（续）,3 罚函数法 2.罚函数法：（续）,算法：,3 罚函数法,3.闸函数法：（内点罚函数法）,3 罚函数法,3.闸函数法：（续）,3 罚函数法,3.闸函数法：（续）,3 罚函数法,3.闸函数法：（续）,3 罚函数法 3.闸函数法：（续）,算法：,3 罚函数法 3.闸函数法：（续）,3 罚函数法,4.罚函数法与闸函数法的缺点：1当罚函数法（闸函数法）的（0+）时，惩罚项+0或0+形式，在计算上有困难；2计算一系列无约束问题，故计算量大。5.乘子法：,3 罚函数法,5.乘子法：（续）,3 罚函数法 5.乘子法：（续）,
