运筹学资料5非线性规划.ppt

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

1、第六章第六章非线性规划非线性规划1 引引 言言非线性规划是运筹学中包含内容最多，非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性应用最广泛的一个分支，计算远比线性规划复杂，由于时间的限制，只能作简规划复杂，由于时间的限制，只能作简单的介绍。单的介绍。例例6-1 电厂投资分配问题电厂投资分配问题水电部门打算将一笔资金分配去建设水电部门打算将一笔资金分配去建设n个水电厂，其库容量为个水电厂，其库容量为ki,i=1,2.n,各各电厂水库径流输入量分布为电厂水库径流输入量分布为Fi(Q)，发，发电量随库容与径流量而变化，以电量随库容与径流量而变化，以Ei(ki,Q)表示。计划部门构

2、造一个模型，表示。计划部门构造一个模型，即在一定条件下，使总发电量年平均值即在一定条件下，使总发电量年平均值最大，用数学语言来说，使其期望值最最大，用数学语言来说，使其期望值最大。对每个电厂大。对每个电厂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利用一定的算法，可求出最优分配

3、利用一定的算法，可求出最优分配ki*和和Vi*(i=1,2,.n).主要内容主要内容非线性规划非线性规划理论方面理论方面应用方面应用方面算法方面算法方面互补稳定灵敏互补稳定灵敏互补稳定灵敏互补稳定灵敏对偶问题对偶问题最优性条件最优性条件无约束问题无约束问题无约束问题无约束问题直接法直接法直接法直接法有约束问题有约束问题有约束问题有约束问题间接法间接法间接法间接法一般模型一般模型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上上的实函数。的实函数。几个概念几个概念定义定义1 如果如果X满足（满足（P

4、）的约束条件的约束条件 hi(X)=0 (i=1,2,.m)gj(X)0 (j=1,2.l)则称则称X En 为（为（P）的一个可行解。的一个可行解。记（记（P）的所有可行解的集合为的所有可行解的集合为D，D称为（称为（P）可行域。可行域。几个概念几个概念定义定义2 X*称为（称为（P）的一个（整体）的一个（整体）最优解，如果最优解，如果X*D，满足满足 f(X)f(X*)，X D。几个概念几个概念定义定义3 X*称为（称为（P）的一个（局部）的一个（局部）最优解，如果最优解，如果X*D，且存在一个且存在一个X*的邻域的邻域N(X*,)=X En X-X*0满足满足 f(X)f(X*)，X D

5、 N(X*,)f(X)f(X)局部最优解局部最优解局部最优解局部最优解整体最优解整体最优解整体最优解整体最优解模型分类模型分类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上上的实函数。的实函数。模型分类模型分类1 如果如果 f(X)hi(X)gj(X)中至少有中至少有一个函数不是线性（仿射）函数，则一个函数不是线性（仿射）函数，则称（称（P）为非线性问题。为非线性问题。如果如果 f(X)hi(X)gj(X)都是线性都是线性（仿射）函数，则称（仿射）函数，则称（P）为线性问为线性问题。题。模型分类

6、模型分类2o若若m=l=0，则称（则称（P）为）为无约束问题。无约束问题。（P1）Min f(X)X X E En n 模型分类模型分类2o若若m 0，l=0，则称（则称（P）为带等式为带等式约束问题。约束问题。（P2）Min f(X)s.t.hi(X)=0 (i=1,2,.m)X X E En n 模型分类模型分类2o若若m=0，l 0，则称（则称（P）为带不等为带不等式约束问题。式约束问题。（P3）Min f(X)s.t.gj(X)0 (j=1,2.l)X X E En n 模型分类模型分类2o若若m 0，l 0，则称（则称（P）为一般为一般问题。问题。（P）Min f(X)s.t.hi(

7、X)=0 (i=1,2,.m)gj(X)0 (j=1,2.l)X X E En n 凸函数的概念凸函数的概念凸集概念：凸集概念：设设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，均有均有

8、0 0(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它是许多算法设计的基础。它是许多算法设计的基础。v无约束问题的最优性条件无约束问题的

9、最优性条件（P1）Min f(X)X X E En n 定理定理1（一阶必要条件）（一阶必要条件）设设f(X)在在X*点可微，则点可微，则X*为（为（P1）的的一个局部最优解，一定有一个局部最优解，一定有 f(X*)=grad f(X*)=0（X*称为驻点称为驻点）v无约束问题的最优性条件无约束问题的最优性条件（P1）Min f(X)X X E En n 定理定理2（二阶必要条件）（二阶必要条件）设设f(X)在在X*点二阶可微，如果点二阶可微，如果X*为为（P1）的的一个局部最优解，则有一个局部最优解，则有 f(X*)=0 和和 H（X*）为半正定。为半正定。v无约束问题的最优性条件无约束问题

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

11、个整体最优解。例例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进一步考虑进一步考虑二阶必要条件，缩小范围：二阶必要条件，缩小范围：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=

12、0为（为（P1）的局部最优解。而）的局部最优解。而x2=1，x3=-1满足二阶必要条件和一阶必要条满足二阶必要条件和一阶必要条件，但它们显然都不是最优解。件，但它们显然都不是最优解。例例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 250 10 262 2 2 H(X)=xxf(X)=4 0 250 10 262 2 2 各阶主子式：各阶主子式：40,4 00 10=4004 0 250

13、10 262 2 2=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)为半正定（半负定）则进一步为半正定（半负定）则

14、进一步观察它在该点某邻域内的情况，如果保观察它在该点某邻域内的情况，如果保持半正定（半负定），那它们是严格局持半正定（半负定），那它们是严格局部极小值点（极大值点）；部极小值点（极大值点）；o如果如果H(x)不定的，该驻点不定的，该驻点X*就不是就不是f(X)极值点。极值点。例例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/3,4/3)H(X)=xxf(X)=-2 0 00 -2 10 1 -2 H(X)=xxf(X)=各阶主子式：各阶主子式：-20=-

15、60-2 0 00 -2 10 1 -2-2 0 00 -2 10 1 -2 H(X)负定，负定，f(X)是凹函数是凹函数X*=(1/2,2/3,4/3)为极大值点。为极大值点。f(X*)=f(1/2,2/3,4/3)=19/12v带不等式约束问题的最优性条件带不等式约束问题的最优性条件（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 紧约束集合。紧约束集合。定理定理5（Kuhn-Tucker必要条件）必要条件）设设f(X)和每个和每个gj(X)在在X*D点可微，又点可微，又设设

16、 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定理定理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）的一个最优解。的一个最优解。v

17、一般问题的最优性条件一般问题的最优性条件（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 定理定理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

18、*)=0 j=1,2.lhi(X*)=0 i=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*)0 uj gj(X*)=0 j=1,2.lhi(X*)=0 i=1,2.m则则X*为（为（P）的一个最优解。的一个最优解。3算法概述算法概述4 一个算法（一个算法（Algorithm)就是一种求解就是一种求解方法，它可看作为一个循环

19、过程，按照一组方法，它可看作为一个循环过程，按照一组指令和规定的停算准则，产生近似解序列，指令和规定的停算准则，产生近似解序列，它应该收敛到整体最优解，但由于某些原因它应该收敛到整体最优解，但由于某些原因（不连续性、无凸性、规模大、实现方面困（不连续性、无凸性、规模大、实现方面困难等）常使得计算难以符合以上条件，往往难等）常使得计算难以符合以上条件，往往是一个无限的过程，因而给出停算准则，如是一个无限的过程，因而给出停算准则，如果在第果在第k次循环时，满足停算准则条件，则停次循环时，满足停算准则条件，则停算。算。常用的停算准则条件：常用的停算准则条件：Xk+n-Xk Xk+1-Xk /Xk (

20、Xk)-(Xk+1)(Xk)-(Xk+1)/(Xk)(Xk)-(X*)etc 评价一个算法（评价一个算法（Algorithm)的好坏，的好坏，通常注意以下几个方面：通常注意以下几个方面：通用性通用性(Generality)可求解问题的广度，越大越好。可求解问题的广度，越大越好。可靠性可靠性(Reliability)指以合理的精度，求解设计的这个算法指以合理的精度，求解设计的这个算法时，针对要解决那个问题的能力。时，针对要解决那个问题的能力。任意给定一个算法，不难构造一个它所任意给定一个算法，不难构造一个它所不能有效地求解的问题。不能有效地求解的问题。评价一个算法（评价一个算法（Algorith

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