约束最优化方法

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,约束最优化方法,约束最优化方法,问题 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),(fgh),(fh),即,一、等式约束性问题的最优性条件：(续),若(,x,*,y,*,)是条件极值，则存在,*,，使,f,x,(x,*,y,*,)+,*,x,(x,*,y,*,),=0,f,y,(x,*,y,*,)+,*,y,(x,*,y,*,),=0,(x,*,y,*,),=0,推广到多元情况，可得到对于(fh)的情况：,min,f(x),s.t.,h,j,(x),=0,j=1,2,l,若x,*,是(fh)的l.opt.,则存在,*,R,l,使,矩阵形式：,分量形式：,一、等式约束性问题的最优性条件：(续),几何意义是明显的：考虑一个约束的情况：,最优性条件即：,-,f(,),h(),h(x),-,f(x*),h(x*),这里,x*,-l.opt.,f(x*),与,h(x*),共线，而,非l.opt.,f(),与,h(),不共线。,二、不等式约束问题的Khun-Tucker条件：,考虑问题 min,f(x),s.t.,g,i,(x),0,i,=1,2,m,设,x*,S,=,x,|,g,i,(x),0,i,=1,2,m,令,I,=,i|g,i,(x*),=0,i,=1,2,m,称,I,为,x*,点处的起作用集（紧约束集）。,如果,x*,是l.opt.,对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：,(fg),g,2,(x),=0,x*,g,1,(x),=0,g,1,(x*)=0,g,1,为起作用约束,Kuhn-Tucker 条件,二、不等式约束问题的Khun-Tucker条件：（续）,特别 有如下特征：如图,在,x*,：,f(x*)+u*g(x*)=0 u*,0,要使函数值下降，必须使,g(x),值变大，则,在,点使,f(x),下降的方向（-,f(,)方向）指向约束集合内部，因此,不是l.opt.。,g(,),-,f(,),X*,-,f(x*),g(x*),二、不等式约束问题的Khun-Tucker条件：（续）,定理（最优性必要条件）：（K-T条件）,问题(fg),设,S=x|g,i,(x)0,x*S,I,为,x*,点处的起作用集，设,f,g,i,(x),i I,在,x*,点可微，,g,i,(x),i I,在,x*,点连续。,向量组,g,i,(x*),i I,线性无关。,如果,x*,-l.opt.那么，,u*,i,0,i I,使,二、不等式约束问题的Khun-Tucker条件：（续）,1,2,3,4,1,2,g,1,=0,g,2,=0,g,4,=0,x,1,g,3,=0,x,2,x*,g,2,(x*),g,1,(x*),-,f(x*),(3,2),T,二、不等式约束问题的Khun-Tucker条件：（续）,用K-T条件求解：,二、不等式约束问题的Khun-Tucker条件：（续）,二、不等式约束问题的Khun-Tucker条件：（续）,可能的K-T点出现在下列情况：,两约束曲线的交点：,g,1,与,g,2,g,1,与,g,3,g,1,与,g,4,g,2,与,g,3,g,2,与,g,4,g,3,与,g,4,。,目标函数与一条曲线相交的情况：,g,1,，g,2,g,3,g,4,对每一个情况求得满足(1)(6)的点(,x,1,x,2,),T,及乘子,u,1,u,2,u,3,u,4,验证当满足可得，且,u,i,0时，即为一个K-T点。,下面举几个情况：,g,1,与,g,2,交点：,x,=(2,1),T,S,I,=1,2 则,u,3,=u,4,=0 解,二、不等式约束问题的Khun-Tucker条件：（续）,二、不等式约束问题的Khun-Tucker条件：（续）,三、一般约束问题的Kuhn-Tucker 条件,三、一般约束问题的Kuhn-Tucker 条件(续),一、解线性约束问题的既约梯度法,一、解线性约束问题的既约梯度法（续）,一、解线性约束问题的既约梯度法（续）,一、解线性约束问题的既约梯度法（续）,一、解线性约束问题的既约梯度法（续）,一、解线性约束问题的既约梯度法（续）,算法：,x,(1),S,k=1,k=k+1,J,k,=,j|x,j,为,x,(k),中最大,m,个正分量之一,B,=,a,j,(j,J,k,),N,=,a,j,(j,J,k,),Y,N,T,=,N,f,T,(,x,(k),)-,B,f,T,(,x,(k),),B,-1,N,d,B,=-B,-1,Nd,N,解,得,x,(k+1),=x,(k),+,k,d,d,=0?,Y,N,Stop;,x(k),K-T点,一、解线性约束问题的既约梯度法（续）,二、广义既约梯度法（续）,二、广义既约梯度法（续）,3罚函数法 1.罚函数概念（续）,3 罚函数法 1.罚函数概念（续）,图示,3罚函数法,2.罚函数法,：（fgh）,3罚函数法,2.罚函数法,：（续）,3 罚函数法 2.罚函数法,：（续）,算法：,初始,x,(1),1,0,1,0,k,=1,以,x,(k),为初始点，解,min,f(x)+(x),得到，,x,(k+1),k,(x,(k+1),)0,0,1,0,k=1,min,f(x)+,k,B(x),s.t.,x S,0,从,x,(k）,出发，,求得，,x,(k+1),k,B(x,(k+1),),yes,停；,x,(k+1),解,No,k+1,=,k,k=k+1,3 罚函数法 3.闸函数法：（续）,3 罚函数法,4.罚函数法与闸函数法的缺点：,1,当罚函数法（闸函数法）的,（0,+,）,时，惩罚项,+,0或0+,形式，在计算上有困难；,2,计算一系列无约束问题，故计算量大。,5.乘子法：,3 罚函数法,5.乘子法：（续）,3 罚函数法 5.乘子法：（续）,