第六章非线性规划(运筹学-上海电力学院,施泉生

第六章非线性规划1引言非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性规划复杂，由于时间的限制，只能作简单的介绍。例6-1电厂投资分配问题水电部门打算将一笔资金分配去建设n个水电厂，其库容量为ki,i=1,2….n,各电厂水库径流输入量分布为Fi(Q)，发电量随库容与径流量而变化，以Ei(ki,Q)表示。计划部门构造一个模型，即在一定条件下，使总发电量年平均值最大，用数学语言来说，使其期望值最大。对每个电厂i，其年发电量的期望值为Ei(ki,Q)dFi(Q)设V为总投资额，Vi为各水电厂的投资，都是ki的非线性函数，构造非线性规划模型如下：MaxEi(ki,Q)dFi(Q)s.t.V1(k1)+V2(k2)+……+Vn(kn)=VV1(k1),V2(k2),……,Vn(kn)0利用一定的算法，可求出最优分配ki*和Vi*(i=1,2,….n).主要内容非线性规划理论方面应用方面算法方面互补稳定灵敏对偶问题最优性条件无约束问题直接法有约束问题间接法一般模型Minf(X)s.t.hi(X)=0(i=1,2,….m)（P）gj(X)0(j=1,2….l)XEnf(X)hi(X)gj(X)为En上的实函数。几个概念定义1如果X满足（P）的约束条件hi(X)=0(i=1,2,….m)gj(X)0(j=1,2….l)则称XEn为（P）的一个可行解。记（P）的所有可行解的集合为D，D称为（P）可行域。几个概念定义2X*称为（P）的一个（整体）最优解，如果X*D，满足f(X)f(X*)，XD。几个概念定义3X*称为（P）的一个（局部）最优解，如果X*D，且存在一个X*的邻域N(X*,)=XEnX-X*0满足f(X)f(X*)，XDN(X*,)f(X)局部最优解整体最优解模型分类Minf(X)s.t.hi(X)=0(i=1,2,….m)（P）gj(X)0(j=1,2….l)XEnf(X)hi(X)gj(X)为En上的实函数。模型分类1如果f(X)hi(X)gj(X)中至少有一个函数不是线性（仿射）函数，则称（P）为非线性问题。如果f(X)hi(X)gj(X)都是线性（仿射）函数，则称（P）为线性问题。模型分类2o若m=l=0，则称（P）为无约束问题。（P1）Minf(X)XEn模型分类2o若m0，l=0，则称（P）为带等式约束问题。（P2）Minf(X)s.t.hi(X)=0(i=1,2,….m)XEn模型分类2o若m=0，l0，则称（P）为带不等式约束问题。（P3）Minf(X)s.t.gj(X)0(j=1,2….l)XEn模型分类2o若m0，l0，则称（P）为一般问题。（P）Minf(X)s.t.hi(X)=0(i=1,2,….m)gj(X)0(j=1,2….l)XEn凸函数的概念凸集概念：设D是n维线性空间En的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。即：若D中的任意两点x(1),x(2)∈D，存在01使得x=x(1)+(1-)x(2)∈D,则称D为凸集凸函数的概念定义：定义在凸集DEn上的函数f(X)如果对任意两点x(1),x(2)∈D，均有01使得f(x(1)+(1-)x(2))f(x(1))+(1-)f(x(2))则称函数f(X)为D上的凸函数.凸函数的概念若严格不等式成立,则称函数f(X)为D上的严格凸函数.如果-g(X)为D上的(严格)凸函数,则g(X)为D上的(严格)凹函数.f(X)Xf(X1)f(X2)X1X2f(X)Xf(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)f(X)Xf(x1)+(1-)f(x2)f(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)f(X)Xf(x1)+(1-)f(x2)f(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)任意两点的函数值的连线上的点都在曲线的上方线性函数既是凸函数,又是凹函数,反之也然.梯度向量f(X)=gradf(X)=(f/x1,f/x2,…..,f/xn)正定矩阵如果对矩阵H(X),对任意XN(X*,)ZEn均有ZTH(X)Z0(0)则称H(X)在X*点正定(半正定).海赛(Hesse)矩阵xxf(X)=H(X)2f/x122f/x1x2…..2f/x1xn2f/x2x12f/x22…..2f/x2xn……..2f/xnx12f/xnx2…..2f/xn2=2最优性条件最优性条件的研究是非线性规划理论研究的一个中心问题。为什么要研究最优性条件？o本质上把可行解集合的范围缩小。o它是许多算法设计的基础。无约束问题的最优性条件（P1）Minf(X)XEn定理1（一阶必要条件）设f(X)在X*点可微，则X*为（P1）的一个局部最优解，一定有f(X*)=gradf(X*)=0（X*称为驻点）无约束问题的最优性条件（P1）Minf(X)XEn定理2（二阶必要条件）设f(X)在X*点二阶可微，如果X*为（P1）的一个局部最优解，则有f(X*)=0和H（X*）为半正定。无约束问题的最优性条件（P1）Minf(X)XEn定理3（二阶充分条件）设f(X)在X*点二阶可微，如果f(X*)=0和H(X*)为正定，则X*为(P1)的一个局部最优解。（H(X)在X*的邻域内为半正定。无约束问题的最优性条件（P1）Minf(X)XEn定理4（一阶充分条件）设f(X)为En上的凸函数，又设f(X)在X*点可微，如果f(X*)=0，则X*为(P1)的一个整体最优解。例6-2Minf(X)=（x2-1)3XE1解：利用一阶必要条件求出有可能成为最优解的那些点:f(X)=6x(x2-1)2=0得到：x1=0,x2=1,x3=-1进一步考虑二阶必要条件，缩小范围：H(X)=xxf(X)=6(x2-1)2+24x2(x2-1)H(x1)=xxf(x1)=xxf(0)=60H(x2)=xxf(x2)=xxf(1)=0H(x3)=xxf(x3)=xxf(-1)=0f(X)在x1=0点正定，依二阶必要条件，x1=0为（P1）的局部最优解。而x2=1，x3=-1满足二阶必要条件和一阶必要条件，但它们显然都不是最优解。例6-3Minf(X)=2x12+5x22+x32+2x2x3+2x1x3-6x2+3XE3解：f(X)=（4x1+2x3,10x2+2x3–6,2x1+2x2+2x3）=0驻点x*=(1,1,-2)H(X)=xxf(X)=4020102222H(X)=xxf(X)=4020102222各阶主子式：40,40010=4004020102222=240H(X)正定，X*=(1,1,-2)为最优解。f(X*)=0解无约束问题的算法：求f(X)的驻点X*，若是凸函数，得到最优解。否则，转下一步。在驻点X*处，计算H(x)。根据H(x)来判断该驻点X*是否是极值点。o若H(x)为正定，该驻点X*是严格局部极小值点；o若H(x)为负定，该驻点X*是严格局部极大值点；o若H(x)为半正定（半负定）则进一步观察它在该点某邻域内的情况，如果保持半正定（半负定），那它们是严格局部极小值点（极大值点）；o如果H(x)不定的，该驻点X*就不是f(X)极值点。例6-4求极值f(X)=x1+2x3+x2x3-x12-x22-x32XE3解：f(X)=(1-2x1,x3-2x2,2+x2-2x3)=0驻点x*=(1/2,2/3,4/3)H(X)=xxf(X)=-2000-2101-2H(X)=xxf(X)=各阶主子式：-20,-200-2=40=-60-2000-2101-2-2000-2101-2H(X)负定，f(X)是凹函数X*=(1/2,2/3,4/3)为极大值点。f(X*)=f(1/2,2/3,4/3)=19/12带不等式约束问题的最优性条件（P3）Minf(X)s.t.gj(X)0(j=1,2….l)XEn令X*D，记J（X*）=jgj(X*)=0紧约束集合。定理5（Kuhn-Tucker必要条件）设f(X)和每个gj(X)在X*D点可微，又设gj(X)(jJ（X*）)线性无关，如果X*为（P3）的局部最优解，则存在（u1,u2,…ul)0,使得f(X*)+ujgj(X*)=0gj(X*)0j=1,2….lujgj(X*)=0j=1,2….l定理6（一阶充分条件）设f(X)和每个gj(X)都是En中的凸函数，且在X*D点可微，如果存在（u1,u2,…ul)0,使得f(X*)+ujgj(X*)=0gj(X*)0j=1,2….lujgj(X*)=0j=1,2….l则X*为（P3）的一个最优解。一般问题的最优性条件（P）Minf(X)s.t.hi(X)=0(i=1,2,….m)gj(X)0(j=1,2….l)XEn定理7（Kuhn-Tucker必要条件）设f(X)和每个gj(X)在X*D点可微，每个hi(X)在X*D点连续可微,又设gj(X)(jJ(X*))和hi(X)线性无关,如果X*为(P)的局部最优解,一定存在(u1,u2,…ul)0和(v1,v2,…vm),使得f(X*)+ujgj(X*)+vihi(X*)=0gj(X*)0ujgj(X*)=0j=1,2….lhi(X*)=0i=1,2….m定理8（Kuhn-Tucker充分条件）设f(X)和每个gj(X)都是En中的凸函数，每个gj(X)都是线性函数，如果存在（u1,u2,…ul)0,和(v1,v2,…vm),使得f(X*)+ujgj(X*)+vihi(X*)=0gj(X*)0ujgj(X*)=0j=1,2….lhi(X*)=0i=1,2….m则X*为（P）的一个最优解。3算法概述一个算法（Algorithm)就是一种求解方法，它可看作为一个循环过程，按照一组指令和规定的停算准则，产生近似解序列，它应该收敛到整体最优解，但由于某些原因（不连续性、无凸性、规模大、实现方面困难等）常使得计算难以符合以上条件，往往是一个无限的过程，因而给出停算准则，如果在第k次循环时，满足停算准则条件，则停算。常用的停算准则条件：Xk+n-XkXk+1-Xk/Xk(Xk)-(Xk+1)((Xk)-(Xk+1))/(Xk)(Xk)-(X*)etc评价一个算法（Algorithm)的好坏，通常注意以下几个方面：通用性(Generality)可求解问题的广度，越大越好。可靠性(Reliability)指以合理的精度，求解设计的这个算法时，针对要解决那个问题的能力。任意给定一个算法，不难构造一个它所不能有效地求解的问题。评价一个算法（Algorithm)的好坏，通常注意以下几个方面：精确性(Precision)指计算舍入误差和累进误差及可行性。对参数和数据的灵敏性(Sensitivity)原则：越不灵敏越好。评价一个算法（Algorithm)的好坏，通常注意以下几个方面：预备工作量和计算量的大小预备工作量（如求初始可行解）及计算量。有时预备工作量比计算量本身还大。收敛性(Convergency)考虑收敛速度，越快越好。习题七P1907.37.47.5