第二章--约束非线性规划.ppt

,单击此处编辑母版文本样式,*,第二章 非线性规划,1,2.4 约束极值问题,一、基本概念和性质,1.起作用约束,对于点,X,0,D，,在,X,0,点等于零的约束称为对,X,0,起作用的约束,，在,X,0,点不等于零的约束称为对,X,0,不起作用的约束,。,在点,X,0,起作用的约束,包括全体等式约束,h,i,(,X,)=0,i,=1,mg,i,(,X,0,)=0，,j,J,1,l,),的不等式约束,g,i,(,X,0,)0(,j,J,)。,几何意义：位于这些约束的边界上。,在,X,0,的不起作用的约束,g,i,(,X,0,)0,的不等式约束。,几何意义：位于这些约束的内部。,浙江理工大学经济管理学院,2,2.4 约束极值问题,2.可行方向,方向,PR,n,在点,X,0,D,称为是可行的,是指存在正数,0,，使对一切,0,0,都有,X,0,+,P,D。,记,J=,j|g,i,(,X,0,)=0，1,j,l。,即所有起作用约束下标的集合。,如果,P,为,X,0,点的可行方向，则存在,0,0，,使对任意,0,0,，,有：,这个条件是,P,是,X,0,的,可行方向的充分条件？,浙江理工大学经济管理学院,3,2.4 约束极值问题,由泰勒公式,对,X,0,起作用的约束，当,0,足够小时,对,X,0,不起作用的约束，,g,i,(,X,0,)0，,当,0,足够小时，也有：,因此，只要,P,满足下式，即可保证它为,X,0,点的可行方向。,浙江理工大学经济管理学院,5,2.4 约束极值问题,4.可行下降方向,若,X,0,点的某一方向,P，,即是该点的可行方向，又是该点的下降方向，就称它为这个点的可行下降方向。,这可作为,可行下降的充分条件,。,浙江理工大学经济管理学院,6,2.4 约束极值问题,定理4,对某一点来说，若该点不存在可行下降方向,，,它就可能是局部极小点，若存在可行下降方向，它当然就不是极小点。,设,X,*,是,NLP,问题的局部极小点，,f,(X),在,X,*,处可微，而且,g,i,(,X,),在,X,*,处可微，当,j,J,g,i,(,X,),在,X,*,处连续，当,j,J,则在,X,*,点不存在可行下降方向，从而不存在,P,同时满足：,浙江理工大学经济管理学院,7,2.4 约束极值问题,二、最优性条件（,K-T,条件）,库恩-塔克（,Kuhn-Tucker),条件是非线性规划领域中最重要的理论成果之一，具有很重要的理论价值。,(1),Gordan,引理,浙江理工大学经济管理学院,8,2.4 约束极值问题,(2),Fritz John,定理,设,X,*,是,NLP,问题的局部最优点，函数,f,(X,),和,g,j,(,X,)(,j,=1,l,),在,X,*,处有连续一阶偏导数，则必存在不全为零的数,u,0,u,1,u,l,，,使,浙江理工大学经济管理学院,10,2.4 约束极值问题,该定理给出了非线性规划的（局部）最优点应满足的必要条件。这个条件称为,Fritz John,条件,，,满足这个条件的点称为,Fritz John,点,。,如果,u,0,=0,f,(,X,*,),就从式中消去，说明在所讨论的点,X,*,处，起作用约束的梯度线性相关。这时,Fritz John,条件失效。,为了保证,u,0,0，,就需要对讨论点处起作用约束的梯度附近加上线性无关的条件，从而引出了,K-T,条件,。,浙江理工大学经济管理学院,12,2.4 约束极值问题,Kuhn-Tucker,条件：,若,X,*,是,NLP,问题的局部极小点，且,X,*,处的所有起作用约束梯度,h,i,(,X,*,)(,i,=1,2,m,),和,g,j,(,X,*,)(,j,J,),线性无关，则存在向量,=(,1,*,1,*,m,*,),T,和,M,*,=(,u,1,*,u,2,*,u,l,*,),T,使下述条件成立：,1,*,1,*,m,*,和,u,1,*,u,2,*,u,l,*,称为广义拉格朗日（,Lagrange,),乘子。,浙江理工大学经济管理学院,14,2.4 约束极值问题,依次类推。,浙江理工大学经济管理学院,15,2.4 约束极值问题,K-T,条件是确定某点为最优点的必要条件，只要是最优点，且此处起作用约束的梯度线性无关，就必须满足这一条件。但一般来说它并不是充分条件，因而，满足这个条件的点不一定就是最优点。可是，对于凸规划，,K-T,条件不但是最优点存在的必要条件，它同时也是充分条件。,浙江理工大学经济管理学院,16,2.4 约束极值问题,浙江理工大学经济管理学院,17,2.4 约束极值问题,浙江理工大学经济管理学院,18,2.4 约束极值问题,例:考虑非线性规划并验证它为凸规划，用,KT,条件求解。,+x,2,浙江理工大学经济管理学院,20,2.4 约束极值问题,K-T,表达式为：,3,1,浙江理工大学经济管理学院,21,2.4 约束极值问题,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,浙江理工大学经济管理学院,23,2.4 约束极值问题,浙江理工大学经济管理学院,24,2.4 约束极值问题,可能的,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,解,浙江理工大学经济管理学院,26,2.4 约束极值问题,浙江理工大学经济管理学院,27,2.4 约束极值问题,基本思想：将约束与目标组合在一起，化为无约束极值问题求解。,内点法（罚函数法）：从可行域的内部逐步逼近最优解。,外点法（障碍函数法）：从可行域的外部逐步逼近最优解。,三、制约函数法,浙江理工大学经济管理学院,28,2.4 约束极值问题,外点法的关键是基于（,NLP）,构造一个新的目标函数,P（X，M），,称为罚函数。,三、制约函数法,外点法,构造新的函数,浙江理工大学经济管理学院,30,2.4 约束极值问题,三、制约函数法,外点法,也可写成另一种形式,引进阶跃函数：,浙江理工大学经济管理学院,31,2.4 约束极值问题,三、制约函数法,外点法,假定对某一个罚因子，如,M,1,，,X,(,M,1,),R,就加大罚因子的值。随着罚因子数值的增加，惩罚函数,P(X,M),中的惩罚项所起的作用随之增大，,minP(X,),离可行域,R,的距离就会越来越近，当,0M1M2Mkr,2,r,k,0,就会逼近极小点。,浙江理工大学经济管理学院,43,2.4 约束极值问题,三、制约函数法,内点法,障碍函数法的迭代步骤：,1 取第一个障碍因子,r10，,允许误差,0,并令,k:=1;,2,构造障碍函数；,3 在,R,0,内进行无约束极小化。,4 是否满足收敛准则：如满足，停止；否则，取,r,k+1,r,k,，,转3.,浙江理工大学经济管理学院,44,2.4 约束极值问题,三、制约函数法,内点法,课本例11：用障碍函数法求解,浙江理工大学经济管理学院,45,2.4 约束极值问题,三、制约函数法,内点法,浙江理工大学经济管理学院,46,2.4 约束极值问题,三、制约函数法,内点法,47,、消元法,n,元非线性规划,S=f(X)=f(x,1,x,2,x,n,),s.t.g,k,(X)=0,k=1,2,m,mn,若可从,m,个,s.t.,中解出,m,个变量,x,i,=h(x,m+1,x,m+2,x,m,),i=1,2,m,代入目标函数中消去,m,个变量，则问题变为一个求,n-m,个变量函数的,无约束条件的极值问题。,例：求解 Min,s.t.,