最优性条件(非线性规划)kuhn-tucker条件

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,非线性规划,最优性条件,（,Kuhn-Tucker,条件）,数学规划,约束集或可行域,MP,的可行解或可行点,向量化表示,当,p=0,q=0,时，称为,无约束非线性规划,或者,无约束最优化问题,。,否则，称为,约束非线性规划,或者,约束最优化问题,。,非线性规划方法概述,问题,min,f(x),s.t.,g(x),0,h(x,),=0,约束集,S=x|g(x)0,h(x)=0,一、等式约束问题的最优性条件：,考虑,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(,),不,共线。,二、不等式约束问题的,Kuhn-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,条件：（续）,特别 有如下特征：如图,在,x*,：,f(x*)+u*g(x*)=0 u*,0,要使函数值下降，必须使,g(x),值变大，则,在,点使,f(x),下降的方向（,-,f(,),方向）指向约束集合内部，因此,不是,l.opt.,。,g(,),-,f(,),X*,-,f(x*),g(x*),二、不等式约束问题的,Kuhn-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,使,二、不等式约束问题的,Kuhn-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*),(2,2),T,二、不等式约束问题的,Khun,-Tucker,条件：（续）,用,K-T,条件求解：,二、不等式约束问题的,Khun,-Tucker,条件：（续）,二、不等式约束问题的,Kuhn-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,解,二、不等式约束问题的,Kuhn-Tucker,条件：（续）,二、不等式约束问题的,Kuhn-Tucker,条件：（续）,三、一般约束问题的,Kuhn-Tucker,条件,三、一般约束问题的,Kuhn-Tucker,条件,(,续,),