运筹学与最优化方法第6章.ppt

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乘子： Lagrange函数 L(x,y;)= f(x,y)+ (x,y),第六章 6.1 Kuhn-Tucker 条件,一、等式约束性问题的最优性

2、条件： (续) 若(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. ,则存在* Rl使 矩阵形式：,一、等式约束性问题的最优性条件： (续) 几何意义是明显的：考虑一个约束的情况： 最优性条件即：,第六章 6.1 Kuhn-Tucker 条件,第六章 6.1 Kuhn-Tucker 条件,二、不等式约束问题的Khun-Tucker条件： 考虑问

3、题 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,第六章 6.1 Kuhn-Tucker 条件,二、不等式约束问题的Khun-Tucker条件： （续） 特别 有如下特征：如图 在x* ： f(x*)+u* g(x*)=0 u*0 要使函数值下降，必须使g(x)值变大，则 在 点使f(x)下降的方向（- f( ) 方向）指向约

4、束集合内部，因此不是l.opt. 。,g( ),第六章 6.1 Kuhn-Tucker 条件,二、不等式约束问题的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 I线性无关。 如果x*-l.opt. 那么， u*i0, i I使,第六章 6.1 Kuhn-Tucker 条件,二、不等式约束问题的Khun-Tucker条件： （续）,第六章 6.1 Kuhn-Tucker 条件,二、不等

5、式约束问题的Khun-Tucker条件： （续） 用K-T条件求解：,第六章 6.1 Kuhn-Tucker 条件,二、不等式约束问题的Khun-Tucker条件： （续）,第六章 6.1 Kuhn-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-T点。 下面举

6、几个情况： g1与g2交点：x=(2,1)TS ,I=1,2 则u3=u4=0 解,第六章 6.1 Kuhn-Tucker 条件,二、不等式约束问题的Khun-Tucker条件： （续） ,第六章 6.1 Kuhn-Tucker 条件,二、不等式约束问题的Khun-Tucker条件： （续） ,第六章 6.1 Kuhn-Tucker 条件,三、一般约束问题的Kuhn-Tucker 条件,第六章 6.1 Kuhn-Tucker 条件,三、一般约束问题的Kuhn-Tucker 条件 (续),第六章 6.2 既约梯度法,一、解线性约束问题的既约梯度法,第六章 6.2 既约梯度法,一、解线性约束问题的

7、既约梯度法 （续）,第六章 6.2 既约梯度法,一、解线性约束问题的既约梯度法 （续）,第六章 6.2 既约梯度法,一、解线性约束问题的既约梯度法 （续）,第六章 6.2 既约梯度法,一、解线性约束问题的既约梯度法 （续）,第六章 6.2解线性约束问题的既约梯度法 （续）,第六章 6.2 既约梯度法,一、解线性约束问题的既约梯度法 （续）,第六章 6.2 既约梯度法,算法：,x(1)S, k=1,k=k+1,Jk=j|xj为x(k)中最大m个正分量之一 B=,aj(jJk), N=,aj(jJk), YNT=NfT(x(k)- BfT(x(k)B-1N dB=-B-1NdN,解 得 x(k+1

8、)=x(k)+kd,d=0?,Y,N,Stop; x(k)K-T点,第六章 6.2 既约梯度法,一、解线性约束问题的既约梯度法 （续）,第六章 6.2 既约梯度法,二、广义既约梯度法 （续）,第六章 6.2 既约梯度法,二、广义既约梯度法 （续）,第六章 6.3罚函数法,第六章 6.3罚函数法 1.罚函数概念 （续）,第六章 6.3 罚函数法 1.罚函数概念 （续）,图示,第六章 6.3罚函数法,2.罚函数法： （fgh）,第六章 6.3罚函数法,2.罚函数法： （续）,第六章 6.3 罚函数法 2.罚函数法： （续）,算法：,第六章 6.3 罚函数法,3.闸函数法： （内点罚函数法）,第六章 6.3 罚函数法,3.闸函数法： （续）,第六章 6.3 罚函数法,3.闸函数法： （续）,第六章 6.3 罚函数法,3.闸函数法： （续）,第六章 6.3 罚函数法 3.闸函数法： （续）,算法：,第六章 6.3 罚函数法 3.闸函数法： （续）,第六章 6.3 罚函数法,4.