运筹学资料非线性规划.pptx

《运筹学资料非线性规划.pptx》由会员分享，可在线阅读，更多相关《运筹学资料非线性规划.pptx（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、电厂水库径流输入量分布为Fi(Q)，发电量随库容与径流量而变化，以Ei(ki,Q)表示。计划部门构造一个模型，即在一定条件下，使总发电量年平均值最大，用数学语言来说，使其期望值最大。对每个电厂i ，其年发电量的期望值为 Ei(ki,Q)dFi(Q)设V为总投资额，Vi为各水电厂的投资，第1页/共50页都是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).第2页/共50页主要内容非线性规划理论方面应用方面算法方

2、面互补稳定灵敏互补稳定灵敏对偶问题最优性条件无约束问题无约束问题直接法直接法有约束问题有约束问题间接法间接法第3页/共50页一般模型Min f(X)s.t.hi(X)=0 (i=1,2,.m)（P）gj(X)0 (j=1,2.l)X En f(X)hi(X)gj(X)为En上的实函数。第4页/共50页几个概念定义1 如果X满足（P）的约束条件 hi(X)=0 (i=1,2,.m)gj(X)0 (j=1,2.l)则称X En 为（P）的一个可行解。记（P）的所有可行解的集合为D，D称为（P）可行域。第5页/共50页几个概念定义2 X*称为（P）的一个（整体）最优解，如果X*D，满足 f(X)f(

3、X*)，X D。第6页/共50页几个概念定义3 X*称为（P）的一个（局部）最优解，如果X*D，且存在一个X*的邻域N(X*,)=X En X-X*0满足 f(X)f(X*)，X D N(X*,)第7页/共50页f(X)f(X)局部最优解局部最优解整体最优解整体最优解第8页/共50页模型分类Min f(X)s.t.hi(X)=0 (i=1,2,.m)（P）gj(X)0 (j=1,2.l)X En f(X)hi(X)gj(X)为En上的实函数。第9页/共50页模型分类1 如果 f(X)hi(X)gj(X)中至少有一个函数不是线性（仿射）函数，则称（P）为非线性问题。如果 f(X)hi(X)gj(

4、X)都是线性（仿射）函数，则称（P）为线性问题。第10页/共50页模型分类2o若m=l=0，则称（P）为无约束问题。（P1）Min f(X)X X E En n 第11页/共50页模型分类2o若m 0，l=0，则称（P）为带等式约束问题。（P2）Min f(X)s.t.hi(X)=0 (i=1,2,.m)X X E En n 第12页/共50页模型分类2o若m=0，l 0，则称（P）为带不等式约束问题。（P3）Min f(X)s.t.gj(X)0 (j=1,2.l)X X E En n 第13页/共50页模型分类2o若m 0，l 0，则称（P）为一般问题。（P）Min f(X)s.t.hi(X

5、)=0 (i=1,2,.m)gj(X)0 (j=1,2.l)X X E En n 第14页/共50页凸函数的概念凸集概念：设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为凸集第15页/共50页凸函数的概念定义：定义在凸集D En上的函数f(X)如果对任意两点x(1),x(2)D，均有0 0(0)则称H(X)在X*点正定(半正定).第22页/共50页海赛(Hesse)矩阵 xxf(X)=H(X)2f/x12 2f/x1 x2 .2f/x

6、1 xn 2f/x2 x1 2f/x22 .2f/x2 xn.2f/xn x1 2f/xn x2 .2f/xn2=第23页/共50页2 最优性条件最优性条件的研究是非线性规划理论研究的一个中心问题。为什么要研究最优性条件？o本质上把可行解集合的范围缩小。o它是许多算法设计的基础。第24页/共50页v无约束问题的最优性条件（P1）Min f(X)X X E En n 定理1（一阶必要条件）设f(X)在X*点可微，则X*为（P1）的一个局部最优解，一定有 f(X*)=grad f(X*)=0（X*称为驻点）第25页/共50页v无约束问题的最优性条件（P1）Min f(X)X X E En n 定理

7、2（二阶必要条件）设f(X)在X*点二阶可微，如果X*为（P1）的一个局部最优解，则有 f(X*)=0 和 H（X*）为半正定。第26页/共50页v无约束问题的最优性条件（P1）Min f(X)X X E En n 定理3（二阶充分条件）设f(X)在X*点二阶可微，如果 f(X*)=0 和 H(X*)为正定，则X*为(P1)的一个局部最优解。（H(X)在X*的邻域内为半正定。第27页/共50页v无约束问题的最优性条件（P1）Min f(X)X X E En n 定理4（一阶充分条件）设f(X)为En上的凸函数，又设f(X)在X*点可微，如果 f(X*)=0，则X*为(P1)的一个整体最优解。第

8、28页/共50页例6-2 Min f(X)=（x2-1)3 X X E E1 1 解：利用一阶必要条件求出有可能成为最优解的那些点:f(X)=6x(x2-1)2=0 得到：x1=0,x2=1,x3=-1进一步考虑二阶必要条件，缩小范围：第29页/共50页H(X)=xxf(X)=6(x2-1)2+24 x2(x2-1)H(x1)=xxf(x1)=xxf(0)=60H(x2)=xxf(x2)=xxf(1)=0H(x3)=xxf(x3)=xxf(-1)=0 f(X)在x1=0点正定，依二阶必要条件，x1=0为（P1）的局部最优解。而x2=1，x3=-1满足二阶必要条件和一阶必要条件，但它们显然都不是

9、最优解。第30页/共50页例6-3 Min f(X)=2x12+5x22+x32+2x2x3 +2x1x3-6x2+3 X E3 解：f(X)=（4x1+2x3,10 x2+2x3 6,2x1+2x2+2x3）=0 驻点x*=(1,1,-2)H(X)=xxf(X)=4 0 20 10 22 2 2 第31页/共50页H(X)=xxf(X)=4 0 20 10 22 2 2 各阶主子式：40,4 00 10=4004 0 20 10 22 2 2=240第32页/共50页H(X)正定，X*=(1,1,-2)为最优解。f(X*)=0第33页/共50页解无约束问题的算法：求f(X)的驻点X*，若是凸

10、函数，得到最优解。否则，转下一步。在驻点X*处，计算H(x)。根据H(x)来判断该驻点X*是否是极值点。第34页/共50页o若H(x)为正定，该驻点X*是严格局部极小值点；o若H(x)为负定，该驻点X*是严格局部极大值点；o若H(x)为半正定（半负定）则进一步观察它在该点某邻域内的情况，如果保持半正定（半负定），那它们是严格局部极小值点（极大值点）；o如果H(x)不定的，该驻点X*就不是f(X)极值点。第35页/共50页例6-4 求极值 f(X)=x1+2x3+x2x3-x12-x22-x32 X E3 解：f(X)=(1-2x1,x3-2x2,2+x2-2x3)=0 驻点x*=(1/2,2/

11、3,4/3)H(X)=xxf(X)=-2 0 00 -2 10 1 -2 第36页/共50页H(X)=xxf(X)=各阶主子式：-20=-60-2 0 00 -2 10 1 -2-2 0 00 -2 10 1 -2 第37页/共50页H(X)负定，f(X)是凹函数X*=(1/2,2/3,4/3)为极大值点。f(X*)=f(1/2,2/3,4/3)=19/12第38页/共50页v带不等式约束问题的最优性条件（P3）Min f(X)s.t.gj(X)0 (j=1,2.l)X X E En n 令X*D D，记，记J J（X*X*）=j =j gj(X*X*)=0 紧约束集合。第39页/共50页定理

12、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*)0 j=1,2.luj gj(X*)=0 j=1,2.l第40页/共50页定理6（一阶充分条件）设f(X)和每个gj(X)都是En中的凸函数，且在X*D点可微，如果存在（u1,u2,ul)0,使得 f(X*)+uj gj(X*)=0gj(X*)0 j=1,2.luj gj(X*)=0 j=1,2.l则X*为（P3）的一个最优解。第41页/共50页v一般问题的最优

13、性条件（P）Min f(X)s.t.hi(X)=0 (i=1,2,.m)gj(X)0 (j=1,2.l)X X E En n 第42页/共50页定理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*)0 uj gj(X*)=0 j=1,2.lhi(X*)=0 i=1,2.m第43页/共50页定理8（Kuhn-Tucker充分条

14、件）设f(X)和每个gj(X)都是En中的凸函数，每个gj(X)都是线性函数，如果存在（u1,u2,ul)0,和(v1,v2,vm),使得 f(X*)+uj gj(X*)+vi hi(X*)=0gj(X*)0 uj gj(X*)=0 j=1,2.lhi(X*)=0 i=1,2.m则X*为（P）的一个最优解。第44页/共50页3算法概述算法概述 一个算法（一个算法（Algorithm)就是一种求解方就是一种求解方法，它可看作为一个循环过程，按照一组指法，它可看作为一个循环过程，按照一组指令和规定的停算准则，产生近似解序列，它令和规定的停算准则，产生近似解序列，它应该收敛到整体最优解，但由于某些原

15、因应该收敛到整体最优解，但由于某些原因（不连续性、无凸性、规模大、实现方面困（不连续性、无凸性、规模大、实现方面困难等）常使得计算难以符合以上条件，往往难等）常使得计算难以符合以上条件，往往是一个无限的过程，因而给出停算准则，如是一个无限的过程，因而给出停算准则，如果在第果在第k次循环时，满足停算准则条件，则停次循环时，满足停算准则条件，则停算。算。第45页/共50页 常用的停算准则条件：常用的停算准则条件：Xk+n-Xk Xk+1-Xk /Xk (Xk)-(Xk+1)(Xk)-(Xk+1)/(Xk)(Xk)-(X*)etc第46页/共50页 评价一个算法（评价一个算法（Algorithm)的

16、好坏，的好坏，通常注意以下几个方面：通常注意以下几个方面：通用性通用性(Generality)可求解问题的广度，越大越好。可求解问题的广度，越大越好。可靠性可靠性(Reliability)指以合理的精度，求解设计的这个算法指以合理的精度，求解设计的这个算法时，针对要解决那个问题的能力。时，针对要解决那个问题的能力。任意给定一个算法，不难构造一个它所任意给定一个算法，不难构造一个它所不能有效地求解的问题。不能有效地求解的问题。第47页/共50页 评价一个算法（评价一个算法（Algorithm)的好坏，的好坏，通常注意以下几个方面：通常注意以下几个方面：精确性精确性(Precision)指计算舍入

17、误差和累进误差及可行性。指计算舍入误差和累进误差及可行性。对参数和数据的灵敏性对参数和数据的灵敏性(Sensitivity)原则：越不灵敏越好。原则：越不灵敏越好。第48页/共50页 评价一个算法（评价一个算法（Algorithm)的好坏，通常的好坏，通常注意以下几个方面：注意以下几个方面：预备工作量和计算量的大小预备工作量和计算量的大小预备工作量（如求初始可行解）及计算量。预备工作量（如求初始可行解）及计算量。有时预备工作量比计算量本身还大。有时预备工作量比计算量本身还大。收敛性收敛性(Convergency)考虑收敛速度，越快越好。考虑收敛速度，越快越好。第49页/共50页感谢您的观看！第50页/共50页