《数模(非线性规划模型).ppt》由会员分享，可在线阅读，更多相关《数模(非线性规划模型).ppt（90页珍藏版）》请在三一办公上搜索。
1、1,数学模型电子教案,重庆邮电大学数理学院沈世云,2,第四章 非线性规划,一、非线性规划引例线性规划和整数规划它们的目标函数和约束条件都是自变量的线性函数，在实际中还有大量的问题，其目标函数或约束条件很难用线性函数来表示。如果目标函数或约束条件中含有非线性函数，则称这种规划问题为非线性规划问题。先看两个实例。,问题1 容器设计问题问题提出 某公司生产贮藏用容器，订货合同要求该公司制造一种敞口的长方体容器，容积为12立方米，该容器的底为正方形，容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10元，重3公斤；用作容器底的材料每平方米20元，重2公斤。试问制造该容器所需的最小费用是多少？
2、,3,模型建立 设该容器的底边长和高分别为,则问题的数学模型为,4,5,定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,二 非现性规划的基本概念,一般形式:（1）其中，是定义在 En 上的实值函数，简记:,其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式,6,定义1 把满足问题（1）中条件的解 称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）记为D即 问题(1)可简记为,定义2 对于问题(1)，设，若存在,使得对一切，且，都有，则称X*是f(X)在D上的局部极小值点（局部最优解）特别地当 时，若，
3、则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）,定义3 对于问题(1),设,对任意的,都有 则称X*是f(X)在D上的全局极小值点（全局最优解）特别地当 时，若，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）,7,定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,非现性规划的基本概念,一般形式:（1）其中，是定义在 En 上的实值函数，简记:,其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式,8,定义1 把满足问题（1）中条件的解 称为可行解（或可行点），所有可行点的集合称为可行集（或
4、可行域）记为D即 问题(1)可简记为,定义2 对于问题(1)，设，若存在,使得对一切，且，都有，则称X*是f(X)在D上的局部极小值点（局部最优解）特别地当 时，若，则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）,定义3 对于问题(1),设,对任意的,都有 则称X*是f(X)在D上的全局极小值点（全局最优解）特别地当 时，若，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）,9,三.非线性规划的图解法,10,三角形表示的是可行域。,同心圆表示的是目标函数的等值线。,最优解为（1/2，1/2）最优值为1/2,问题：(1/2,1/2)是整体的还是局部的？是严格的还是非严格
5、的？,1/2,1/2,11,2、非线性规划方法概述,微分学方法的局限性：,实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不易处理。,12,数值方法的基本思路：迭代,给定初始点x0,根据x0,依次迭代产生点列xk,xk的最后一点为最优解,xk收敛于最优解,13,迭代格式,xk,xk+1,称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。,产生tk和pk的不同方法，形成了不同的算法。,14,定义：下降方向,15,定义,解非线性规划问题，关键在于找到某个方向，使得在此方向上，目标函数得到下降，同时还是可行方
6、向。这样的方向称为可行下降方向。,16,第二节 凸函数和凸规划,1、凸函数及其性质：,定义,，,17,定理:,关于凸函数的一些结论,定理:,是凸集。,函数f在集合S上关于c的水平集,18,定理,n=1时几何意义：可微函数是凸的等价于切线不在函数图像上方。,19,20,2、凸规划及其性质：,凸规划定义：,21,凸规划性质：,凸规划的任一局部最优解都是它的整体最优解。,凸规划是以后重点讨论的一类非线性规划,线性函数,22,第三节 一维搜索方法,t为实数,一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：,什么叫一维搜索问题？,或,23,一维搜索问题的算法分类：,精确一维搜
7、索（最优一维搜索）非精确一维搜索（可接受一维搜索）,本节内容：,两种精确一维搜索方法：0.618法，Newton法。两种非精确一维搜索方法：Goldstein法,Armijo法。,24,1、0.618法（近似黄金分割法）,问题：凸函数是不是单谷函数？严格凸函数是不是单谷函数？单谷函数是不是凸函数？,单谷函数,25,搜索法求解：,或,基本过程：给出a,b,使得t*在a,b中。a,b称为搜索区间。迭代缩短a,b的长度。当a,b的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。,26,假定：已经确定了单谷区间a,b,新搜索区间为a,t2,新搜索区间为t1,b,27,区间缩小比例
8、的确定：,区间缩短比例为(t2-a)/(b-a),缩短比例为(b-t1)/(b-a),缩短比例 满足：每次插入搜索点使得两个区间a,t2和t1,b相等；每次迭代都以相等的比例缩小区间。,退 出,前一页,后一页,28,确定a,b,计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a),0.618法解题步骤：,停止，输出t1,以a,t2为新的搜索区间,停止，输出t2,以t1,b为新的搜索区间,29,例：,解：,1、第一轮：t1=1.146,t2=1.854,t200.5,30,2、第二轮：t2=1.146,t1=0.708,t20=1.1460.5,3、第三轮：t1=0.438,t
9、2=0.708,b-t1=1.146-0.4380.5,31,4、第四轮：t2=0.876,t1=0.708,b-t1=1.146-0.7080.5,输出：t*=t2=0.876为最优解，最优值为-0.0798,32,2、Newton法,Newton法基本思想：,用探索点tk处的二阶Taylor展开式近似代替目标函数，以展开式的最小点为新的探索点。,33,解题步骤：,给定初始点t1和精度,停止，输出t1,停止，解题失败,停止，输出t2,34,例：,解：,取t1=1,计算：,迭代过程如下表：,退 出,前一页,后一页,35,3、非精确一维搜索法,数值方法的关键是从一个点迭代到下一个点。,确定下一个
10、点的关键是确定搜索方向和步长,如果已经确定了搜索方向pk,则只要确定一个最佳的步长即可。,所谓的最佳步长即是在pk方向上走一个最好的长度使得目标函数下降的最多，即下述的最优化问题：,这样的最优化问题不需要太高的精度，只要满足某些更宽松的精度要求即可。这样的搜索方法称之为非精确一维搜索方法,36,Goldstein法原理：,Y=(0)+(0)t,Y=(0)+m2(0)t,Y=(0)+m1(0)t,37,是,Goldstein算法,确定m1,m2,t0,a=0,b=+,(t0)(0)+m1(0)t0,(t0)(0)+m2(0)t0,是,停止,输出t0,否,a=a,b=t0,t1=(a+b)/2,否
11、,a=t0,b=b,t1=(a+b)/2(若b=+,则t1=a),退 出,前一页,后一页,38,Armijo法原理：,退 出,前一页,后一页,39,第四节 无约束最优化方法,本节课讨论n元函数的无约束非线性规划问题：,求解此类模型(UMP)的方法称为无约束最优化方法。,无约束最优化方法通常有两类：解析法：要使用导数的方法；直接法：无须考虑函数是否可导，直接使用函数值。,40,1、无约束问题的最优性条件,定理1,定理2,梯度为0的点称为函数的驻点。驻点可能是极小点，也可能是极大点，也可能即不是极大也不是极小，这时称为函数的鞍点。定理2说明：UMP问题的局部最优解必是目标函数的驻点。,注：,退 出
12、,前一页,后一页,41,定理3,定理4,课下练习：画图理解定理1、2、4的几何意义。,退 出,前一页,后一页,42,无约束优化问题的基本算法,最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.,1最速下降法（共轭梯度法）算法步骤：,43,2牛顿法算法步骤：,如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法
13、的收敛速度还是很快的.,牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.,44,3拟牛顿法,45,用Matlab解无约束优化问题,其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。,常用格式如下：（1）x=fminbnd(fun,x1,x2)（2）x=fminbnd(fun,x1,x2，options)（3）x，fval=fminbnd（.）（4）x，fval，exitflag=fminbnd（.）（5）x，
14、fval，exitflag，output=fminbnd（.）,46,主程序为:f=2*exp(-x).*sin(x);fplot(f,0,8);%作图语句 xmin,ymin=fminbnd(f,0,8)f1=-2*exp(-x).*sin(x);xmax,ymax=fminbnd(f1,0,8),47,例2 对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？p156，例8-1,解,先编写M文件fminbndtest.m如下:function f=myfun(x)f=-(3-2*x).2*x;,主程序调用fminbnd:x,fval=fminb
15、nd(fminbndtest,0,1.5);xmax=x fmax=-fval,运算结果为:xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.,48,命令格式为:（1）x=fminunc（fun,X0）；或x=fminsearch（fun,X0）（2）x=fminunc（fun,X0，options）；或x=fminsearch（fun,X0，options）（3）x，fval=fminunc（.）；或x，fval=fminsearch（.）（4）x，fval，exitflag=fminunc（.）；或x，fval，exitfl
16、ag=fminsearch（5）x，fval，exitflag，output=fminunc（.）；或x，fval，exitflag，output=fminsearch（.）,2、多元函数无约束优化问题,标准型为：min F(X),49,3 fminunc为中型优化算法的步长一维搜索提供了两种算法，由options中参数LineSearchType控制：LineSearchType=quadcubic(缺省值)，混合的二次和三 次多项式插值；LineSearchType=cubicpoly，三次多项式插,使用fminunc和 fminsearch可能会得到局部最优解.,说明:,fminsear
17、ch是用单纯形法寻优.fminunc的算法见以下几点说明：,1 fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控制：LargeScale=on(默认值),使用大型算法LargeScale=off(默认值),使用中型算法,2 fminunc为中型优化算法的搜索方向提供了4种算法，由 options中的参数HessUpdate控制：HessUpdate=bfgs（默认值），拟牛顿法的BFGS公式；HessUpdate=dfp，拟牛顿法的DFP公式；HessUpdate=steepdesc，最速下降法,50,例3 min f(x)=(4x12+2
18、x22+4x1x2+2x2+1)*exp(x1),1、编写M-文件 fun1.m:function f=fun1(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);2、输入M文件myprg3.m如下:x0=-1,1;x=fminunc(fun1,x0);y=fun1(x),3、运行结果:x=0.5000-1.0000 y=1.3029e-10,51,第五节 约束最优化方法,本节课讨论约束非线性规划问题MP,其中,x=(x1,x2,xn)T，f(x),gi(x),hj(x)为x的实值函数,求解此类模型(MP)的方法称为约束最优化方法。,52,
19、1、约束最优化问题的最优性条件,对于MP问题：,53,若x*有变化，则约束条件可能没有破坏,若x*有变化，则约束条件一定被破坏,令J表示MP的全部等式约束的下标集合，即J=1,2q,I表示MP的全部不等式约束的下标集合，即I=1,2p,x*的积极约束的下标集合,54,定理1,对于,若x*是局部最优解,则,55,定理1的说明：,2、称下述表达式为MP的Kuhn-Tucker条件，简称K-T条件,满足K-T条件的点称为MP的K-T点，定理1说明MP的局部最优解一定是MP的K-T点。,为了求出MP的最优解，可以先找出MP的K-T点，再做进一步的判断。,56,3、定理1的实例说明,定理1表明：若(x1
20、,x2)T是局部最优解，g1和g2为积极约束，则：,57,4、定理1的特例1,58,5、定理1的特例2,59,6、定理1的改进：,对于,若x*是局部最优解,则,互补松紧条件,60,7、实例说明改进后的定理1：,定理1改进后表明：若(x1,x2)T是局部最优解，则：,61,互补松紧条件,62,定理2,对于,注：定理2表明，在凸性条件下，K-T点是整体最优解。,63,例：写出K-T条件;求出相应的K-T点;判断K-T点是不是问题的最优解,解：由于全部函数都是连续可微的，所以应用以下K-T条件,64,首先写出原MP问题的K-T条件：,根据定理1,K-T点还应该满足原问题的约束条件,互补松紧条件,65
21、,利用互补松紧条件，可以求出K-T点：,利用定理2，由于全部函数都连续可微，并且f和g都是凸函数，h是线性函数，所以K-T点就是整体最优解。,66,2、惩罚函数法,惩罚函数法的基本思想：利用原问题的中的约束函数构造适当的惩罚函数，并和原问题的目标函数相加，得到带参数的增广目标函数，从而将原问题题转换为一系列无约束非线性规划问题。惩罚函数法的分类：罚函数法（外部惩罚法），障碍函数法（内部惩罚法）,67,(1)罚函数法,罚函数法基本原理：,考虑：,构造惩罚函数：,很大的正数,无约束最优化问题min F(x)=f(x)+p(x)的最优解必定是原问题的最优解。,退 出,前一页,后一页,68,可选的惩罚
22、函数：,惩罚函数法的经济解释：f(x)为产品成本，约束条件为产品质量约束；如果违反质量约束，就给予一定的惩罚p(x)；追求的目标就是成本f(x)和惩罚量p(x)的总和最小（即构造的无约束最优化问题）；如果惩罚条件很苛刻，最好的结果就是不违反质量约束（无约束最优化问题的最优解为MP的最优解）,69,(2)障碍函数法,障碍函数法基本原理：构造一个新的目标函数，它在可行区域的边界筑起一道墙；当迭代点靠近边界时，新的目标函数迅速增加；迭代点被档在可行区域的内部；迭代得到的点列就只可能在可行区域的内部。,70,可选的惩罚函数：,考虑：,构造最优化问题：,或：,当x靠近边界时，至少有一个gi(x)趋近于零
23、，则F(x)将无限增大，从而使得迭代点保持在可行区域的内部。,71,72,73,74,75,76,77,78,79,5、计算结果,80,用MATLAB软件求解,其输入格式如下:1.x=quadprog(H,C,A,b);2.x=quadprog(H,C,A,b,Aeq,beq);3.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6.x,fval=quaprog(.);7.x,fval,exi
24、tflag=quaprog(.);8.x,fval,exitflag,output=quaprog(.);,1、二次规划,81,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t.x1+x22-x1+2x22 x10,x20,1、写成标准形式：,2、输入命令：H=1-1;-1 2;c=-2;-6;A=1 1;-1 2;b=2;2;Aeq=;beq=;VLB=0;0;VUB=;x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),3、运算结果为：x=0.6667 1.3333 z=-8.2222,s.t.,82,1.首先建立M文件fun.
25、m,定义目标函数F（X）:function f=fun(X);f=F(X);,2、一般非线性规划,其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：,83,3.建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下：(1)x=fmincon(fun,X0,A,b)(2)x=fmincon(fun,X0,A,b,Aeq,beq)(3)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB)(4)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,
26、VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options)(6)x,fval=fmincon(.)(7)x,fval,exitflag=fmincon(.)(8)x,fval,exitflag,output=fmincon(.),输出极值点,M文件,迭代的初值,参数说明,变量上下限,84,1、写成标准形式：s.t.,2x1+3x2 6 s.t x1+4x2 5 x1,x2 0,例2,85,2、先建立M-文件 fun3.m:function f=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)2+(1
27、/2)*x(2)2,3、再建立主程序youh2.m：x0=1;1;A=2 3;1 4;b=6;5;Aeq=;beq=;VLB=0;0;VUB=;x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB),4、运算结果为：x=0.7647 1.0588 fval=-2.0294,86,1先建立M文件 fun4.m,定义目标函数:function f=fun4(x);f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,x1+x2=0 s.t.1.5+x1x2-x1-x2 0-x1x2 10 0,例3,2再建立M文件myc
28、on.m定义非线性约束：function g,ceq=mycon(x)g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,87,3主程序为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon),3.运算结果为：x=-1.2250 1.2250 fval=1.8951,88,例4,1先建立M-文件fun.m定义目标函数:function f=fun(x);f=-2*x(1)-x(2);,2再建立M文件mycon2.m定义非线性约束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;,89,3.主程序fxx.m为:x0=3;2.5;VLB=0 0;VUB=5 10;x,fval,exitflag,output=fmincon(fun,x0,VLB,VUB,mycon2),90,4.运算结果为:x=4.0000 3.0000fval=-11.0000exitflag=1output=iterations:4 funcCount:17 stepsize:1 algorithm:1x44 char firstorderopt:cgiterations:,
