数模(非线性规划模型)

《数模(非线性规划模型)》由会员分享，可在线阅读，更多相关《数模(非线性规划模型)（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，

5、1/2） 最优值为1/2,问题：(1/2,1/2)是整体的还是局部的？是严格的还是非严格的？,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为实数,一维搜索问题指目标函数为单变量的非线性规划问题。又称

7、线性搜索问题。其模型为：,什么叫一维搜索问题？,或,23,一维搜索问题的算法分类：,精确一维搜索（最优一维搜索） 非精确一维搜索（可接受一维搜索）,本节内容：,两种精确一维搜索方法：0.618法，Newton法。 两种非精确一维搜索方法：Goldstein法,Armijo法。,24,1、0.618法（近似黄金分割法）,问题：凸函数是不是单谷函数？严格凸函数是不是单谷函数？单谷函数是不是凸函数？,单谷函数,25,搜索法求解：,或,基本过程： 给出a,b,使得t*在a,b中。a,b称为搜索区间。 迭代缩短a,b的长度。 当a,b的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止

8、。,26,假定：已经确定了单谷区间a,b,新搜索区间为a,t2,新搜索区间为t1,b,27,区间缩小比例的确定：,区间缩短比例为(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.

9、5,30,2、第二轮： t2=1.146, t1=0.708,t20=1.1460.5,3、第三轮： t1=0.438, t2=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,计

10、算：,迭代过程如下表：,退 出,前一页,后一页,35,3、非精确一维搜索法,数值方法的关键是从一个点迭代到下一个点。,确定下一个点的关键是确定搜索方向和步长,如果已经确定了搜索方向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,

11、b=+,(t0) (0)+m1 (0)t0,(t0) (0)+m2(0)t0,是,停止,输出t0,否,a=a, b=t0, t1=(a+b)/2,否,a=t0,b=b, t1=(a+b)/2 (若b=+,则t1= a),退 出,前一页,后一页,38,Armijo法原理：,退 出,前一页,后一页,39,第四节 无约束最优化方法,本节课讨论n元函数的无约束非线性规划问题：,求解此类模型(UMP)的方法称为无约束最优化方法。,无约束最优化方法通常有两类： 解析法：要使用导数的方法； 直接法：无须考虑函数是否可导，直接使用函数值。,40,1、无约束问题的最优性条件,定理1,定理2,梯度为0的点称为函数

12、的驻点。 驻点可能是极小点，也可能是极大点，也可能即不是极大也不是极小，这时称为函数的鞍点。 定理2说明：UMP问题的局部最优解必是目标函数的驻点。,注：,退 出,前一页,后一页,41,定理3,定理4,课下练习：画图理解定理1、2、4的几何意义。,退 出,前一页,后一页,42,无约束优化问题的基本算法,最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.,1最速下降法（共轭梯度法）算法步骤：,43,2牛顿法算法步骤：,如果f是

13、对称正定矩阵A的二次函数，则用牛顿法经过一次迭代 就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点， 但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收 敛速度还是很快的.,牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.,44,3拟牛顿法,45,用Matlab解无约束优化问题,其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。 函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。,常用格式如下： （1）x= fminbnd (fun,x1,

14、x2) （2）x= fminbnd (fun,x1,x2 ，options) （3）x，fval= fminbnd（.） （4）x，fval，exitflag= fminbnd（.） （5）x，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米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问

15、如何剪法使水槽的容积最大？p156，例8-1,解,先编写M文件fminbndtest.m如下: function f=myfun(x) f=-(3-2*x).2*x;,主程序调用fminbnd: x,fval=fminbnd(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，exitflag= fminsearch （5）x，fval，exitflag，output= fminunc（.）； 或x，