运筹学资料非线性规划

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章,非线性规划,1,1 引 言,非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性规划复杂，由于时间的限制，只能作简单的介绍。,例,6-1,电厂投资分配问题,水电部门打算将一笔资金分配去建设,n,个水电厂，其库容量为,k,i,i=1,2.n,各,2,电厂水库径流输入量分布为F,i,(Q)，发电量随库容与径流量而变化，以E,i,(k,i,Q)表示。计划部门构造一个模型，即在一定条件下，使总发电量年平均值最大，用数学语言来说，使其期望值最大。对每个电厂i ，其年发电量的期望值为,E,i,(k,i,Q) dF,i,(Q),设V为总投资额，V,i,为各水电厂的投资，,3,都是k,i,的非线性函数，构造非线性规划模型如下：,Max,E,i,(k,i,Q) dF,i,(Q),s.t.V,1,(k,1,)+ V,2,(k,2,)+ + V,n,(k,n,)=V,V,1,(k,1,), V,2,(k,2,),V,n,(k,n,),0,利用一定的算法，可求出最优分配k,i,*,和V,i,*,(i=1,2,.n).,4,主要内容,非线性规划,理论方面,应用方面,算法方面,互补稳定灵敏,对偶问题,最优性条件,无约束问题,直接法,有约束问题,间接法,5,一般模型,Min f(X),s.t. h,i,(X) = 0 (i=1,2,.m),（,P,）,g,j,(X),0 (j=1,2.l),X,E,n,f(X) h,i,(X),g,j,(X),为,E,n,上的实函数。,6,几个概念,定义,1,如果,X,满足（,P,）,的约束条件,h,i,(X)=0 (i=1,2,.m),g,j,(X),0 (j=1,2.l),则称,X,E,n,为（,P,）,的一个可行解。,记（,P,）,的所有可行解的集合为,D,，,D,称为（,P,）,可行域。,7,几个概念,定义,2,X,*,称为（,P,）,的一个（整体）最优解，如果,X,*,D,，,满足,f(X),f(X,*,),，,X,D,。,8,几个概念,定义,3,X,*,称为（,P,）,的一个（局部）最优解，如果,X,*,D,，,且存在一个,X,*,的邻域,N(X,*,)=,X,E,n,X-,X,*,0,满足,f(X),f(X,*,),，,X,D,N(X,*,),9,f(X),局部最优解,整体最优解,10,模型分类,Min f(X),s.t. h,i,(X)=0 (i=1,2,.m),（,P,）,g,j,(X),0 (j=1,2.l),X,E,n,f(X) h,i,(X),g,j,(X),为,E,n,上的实函数。,11,模型分类,1,如果,f(X) h,i,(X),g,j,(X),中至少有一个函数不是线性（仿射）函数，则称（,P,）,为非线性问题。,如果,f(X) h,i,(X),g,j,(X),都是线性（仿射）函数，则称（,P,）,为线性问题。,12,模型分类,2,若,m=l=0,，,则称（,P,）为,无约束问题。 （,P,1,）,Min f(X),X,E,n,13,模型分类,2,若,m,0,，,l=0,，,则称（,P,）,为带等式约束问题。,（,P,2,）,Min f(X),s.t. h,i,(X)=0 (i=1,2,.m),X,E,n,14,模型分类,2,若,m,=,0,，,l,0,，,则称（,P,）,为带不等式约束问题。,（,P,3,）,Min f(X),s.t.,g,j,(X),0 (j=1,2.l),X,E,n,15,模型分类,2,若,m,0,，,l,0,，,则称（,P,）,为一般问题。,（,P,）,Min f(X),s.t. h,i,(X)=0 (i=1,2,.m),g,j,(X),0 (j=1,2.l),X,E,n,16,凸函数的概念,凸集概念：,设,D,是,n,维线性空间,E,n,的一个点集，若,D,中的任意两点,x,(1),x,(2),的连,线上的一切点,x,仍在,D,中，则称,D,为凸集。,即：,若,D,中的任意两点,x,(1),x,(2),D,，,存在,0,1,使得,x=,x,(1),+(1-,)x,(2),D,则称,D,为凸集,17,凸函数的概念,定义：定义在凸集,D,E,n,上的,函数,f(X),如果对任意两点,x,(1),x,(2),D,，,均有,0, 0( 0 ),则称,H(X),在,X,*,点正定,(,半正定,),.,24,海赛,(,Hesse,),矩阵,xx,f,(X) = H(X),2,f/x,1,2,2,f/x,1,x,2,. ,2,f/x,1,x,n,2,f/x,2,x,1,2,f/x,2,2,. ,2,f/x,2,x,n,.,2,f/x,n,x,1,2,f/x,n,x,2,. ,2,f/x,n,2,=,25,2 最优性条件,最优性条件的研究是非线性规划理论研究的一个中心问题。,为什么要研究最优性条件？,本质上把可行解集合的范围缩小。,它是许多算法设计的基础。,26,无约束问题的最优性条件,（,P,1,）,Min f(X),X,E,n,定理,1,（一阶必要条件）,设,f(X),在,X,*,点可微，则,X,*,为（,P,1,）,的,一个局部最优解，一定有,f(,X,*,)=grad f(,X,*,)=0,（,X,*,称为驻点,）,27,无约束问题的最优性条件,（,P,1,）,Min f(X),X,E,n,定理,2,（二阶必要条件）,设,f(X),在,X,*,点二阶可微，如果,X,*,为,（,P,1,） 的,一个局部最优解，则有,f(,X,*,) =0,和,H,（,X,*,）,为半正定。,28,无约束问题的最优性条件,（,P,1,）,Min f(X),X,E,n,定理,3,（二阶充分条件）,设,f(X),在,X,*,点二阶可微，如果,f(,X,*,) =0,和,H(,X,*,),为正定，,则,X,*,为,(,P,1,),的,一个局部最优解。（,H(,X,),在,X,*,的邻域内,为半正定。,29,无约束问题的最优性条件,（,P,1,）,Min f(X),X,E,n,定理,4,（一阶充分条件）,设,f(X),为,E,n,上的凸函数，又设,f(X),在,X,*,点可微，如果,f(,X,*,) =0,，,则,X,*,为,(,P,1,),的,一个整体最优解。,30,例6-2,Min f(X)=（x,2,-1),3,X,E,1,解：,利用一阶必要条,件求出有可能成为最,优解的那些点:,f(,X,) =,6x(x,2,-1),2,=0 得到：x,1,=0,x,2,=1,x,3,= -1,进一步考虑,二阶必要条件，缩小范围：,31,H(X) =,xx,f(X) =,6(x,2,-1),2,+24 x,2,(x,2,-1),H(x,1,) =,xx,f(x,1,) = ,xx,f(0) =60,H(x,2,) =,xx,f(x,2,) = ,xx,f(1) = 0,H(x,3,) =,xx,f(x,3,) = ,xx,f(-1) =0,f(X)在x,1,=0点正定，依二阶必要条件， x,1,=0为（P,1,）的局部最优解。而x,2,=1， x,3,= -1满足二阶必要条件和一阶必要条件，但它们显然都不是最优解。,32,例6-3,Min f(X)= 2,x,1,2,+5x,2,2,+x,3,2,+,2x,2,x,3,+,2x,1,x,3,-,6x,2,+3,X,E,3,解：,f(,X,) = （4x,1,+,2x,3, 10x,2,+,2x,3,6,2x,1,+,2x,2,+,2x,3,）=0,驻点x*=(1,1,-2),H(X) =,xx,f(X)=,0 2,0 10 2,2 2 2,33,H(X) =,xx,f(X)=,0 2,0 10 2,2 2 2,各阶主子式：40,4,0,0 10,=400,0 2,0 10 2,2 2 2,=240,34,H(X)正定，,X*=(1,1,-2)为最优解。,f(X*)=0,35,解无约束问题的算法：,求,f(X),的驻点,X*,，,若是凸函数，得到最优解。否则，转下一步。,在驻点,X*,处，计算,H(x),。,根据,H(x),来,判断该驻点,X*,是否是极值点。,36,若,H(x),为正定，该驻点,X*,是严格局部极小值点；,若,H(x),为负定，该驻点,X*,是严格局部极大值点；,若,H(x),为半正定（半负定）则进一步观察它在该点某邻域内的情况，如果保持半正定（半负定），那它们是严格局部极小值点（极大值点）；,如果,H(x),不定的，该驻点,X*,就不是,f(X),极值点。,37,例6-4,求极值 f(X)=,x,1,+,2x,3,+x,2,x,3,-,x,1,2,-x,2,2,-x,3,2,X,E,3,解：,f(,X,) = (1-2x,1,x,3,-2x,2, 2+x,2,-,2x,3,) = 0,驻点x*=(1/2,2/3,4/3),H(X) =,xx,f(X)=,-2 0 0,0 -2 1,0 1 -2,38,H(X) =,xx,f(X)=,各阶主子式：-20,= - 60,-2 0 0,0 -2 1,0 1 -2,-2 0 0,0 -2 1,0 1 -2,39,H(X)负定，,f(X),是凹函数,X*=(1/2,2/3,4/3)为极大值点。,f(X*)= f(1/2,2/3,4/3)=19/12,40,带不等式约束问题的最优性条件,（,P,3,）,Min f(X),s.t.,g,j,(X),0 (j=1,2.l),X,E,n,令,X*,D,，记,J,（,X*,）,= j,g,j,(,X*,) =0,紧约束集合。,41,定理5（Kuhn-Tucker必要条件）,设f(X)和每个g,j,(X)在X,*,D,点可微，又设,g,j,(X) (,j J（X*）),线性无关，如果,X,*,为（P,3,）的局部最优解，则存在（u,1,u,2,u,l,),0,使得,f(X,*,)+,u,j,g,j,(X,*,) =0,g,j,(X,*,),0 j=1,2.l,u,j,g,j,(X,*,) =0 j=1,2.l,42,定理6（一阶充分条件）,设f(X)和每个g,j,(X)都是E,n,中的凸函数，且在X,*,D,点可微，,如果,存在（u,1,u,2,u,l,),0,使得,f(X,*,)+,u,j,g,j,(X,*,) =0,g,j,(X,*,),0 j=1,2.l,u,j,g,j,(X,*,) =0 j=1,2.l,则,X,*,为（,P,3,）,的一个最优解。,43,一般问题的最优性条件,（,P,）,Min f(X),s.t. h,i,(X)=0 (i=1,2,.m),g,j,(X),0 (j=1,2.l),X,E,n,44,定理7（Kuhn-Tucker必要条件）,设f(X)和每个g,j,(X)在X,*,D,点可微，每个h,i,(X)在X,*,D,点连续可微,又设,g,j,(X)(,j J(X*)和,h,i,(X),线性无关,如果,X,*,为(P)的局部最优解,一定存在(u,1,u,2,u,l,),0和(v,1,v,2,v,m,),使得,f(X,*,)+,u,j,g,j,(X,*,) +,v,i,h,i,(X,*,) =0,g,j,(X,*,),0,u,j,g,j,(X,*,) =0 j=1,2.l,h,i,(X,*,) =0 i=1,2.m,45,定理8（ Kuhn-Tucker充分条件）,设f(X)和每个g,j,(X)都是E,n,中的凸函数，每个g,j,(X) 都是线性函数，,如果,存在（u,1,u,2,u,l,),0,和(v,1,v,2,v,m,),使得,f(X,*,)+,u,j,g,j,(X,*,) +,v,i,h,i,(X,*,) =0,g,j,(X,*,),0,u,j,g,j,(X,*,) =0 j=1,2.l,h,i,(X,*,) =0 i=1,2.m,则,X,*,为（,P,）,的一个最优解。,46,算法概述,一个算法（,Algorithm),就是一种求解方法，它可看作为一个循环过程，按照一组指令和规定的停算准则，产生近似解序列，它应该收敛到整体最优解，但由于某些原因（不连续性、无凸性、规模大、实现方面困难等）常使得计算难以符合以上条件，往往是一个无限的过程，因而给出停算准则，如果在第,k,次循环时，满足停算准则条件，则停算。,47,常用的停算准则条件：,X,k,+n,-,X,k,X,k,+1,-,X,k,/ ,X,k,(,X,k,)-,(,X,k,+1,) ,(,X,k,)-,(,X,k,+1,) )/,(,X,k,),(,X,k,)-,(,X*) ,etc,48,评价一个算法（Algorithm)的好坏，通常注意以下几个方面：,通用性,(,Generality),可求解问题的广度，越大越好。,可靠性,(,Reliability),指以合理的精度，求解设计的这个算法时，针对要解决那个问题的能力。,任意给定一个算法，不难构造一个它所不能有效地求解的问题。,49,评价一个算法（Algorithm)的好坏，通常注意以下几个方面：,精确性,(,Precision),指计算舍入误差和累进误差及可行性。,对参数和数据的灵敏性,(,Sensitivity),原则：越不灵敏越好。,50,评价一个算法（Algorithm)的好坏，通常注意以下几个方面：,预备工作量和计算量的大小,预备工作量（如求初始可行解）及计算量。,有时预备工作量比计算量本身还大。,收敛性,(,Convergency,),考虑收敛速度，越快越好。,51,