《数模(非线性规划模型)ppt课件.ppt》由会员分享，可在线阅读，更多相关《数模(非线性规划模型)ppt课件.ppt（90页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1数学模型电子教案数学模型电子教案重庆邮电大学重庆邮电大学数理学院数理学院沈世云沈世云“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。2第四章第四章 非线性规划非线性规划一、非线性规划引例线性规划和整数规划它们的目标函数和约束条件都是自变量的线性函数，在实际中还有大量的问题，其目标函数或约束条件很难用线性函数来表示。如果目标函数或约束条件中含有非线性函数，则称这种规划问题为非线性规划问题。先看两个实例。问题1 容器设计问题问题提出 某公司生产贮藏用容器，订货合同要求该公司制造一
2、种敞口的长方体容器，容积为12立方米，该容器的底为正方形，容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10元，重3公斤；用作容器底的材料每平方米20元，重2公斤。试问制造该容器所需的最小费用是多少？ “雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。321,xx21212040)(minxxxXf0,6821212212121221xxxxxxx模型建立 设该容器的底边长和高分别为则问题的数学模型为则问题的数学模型为 “雪亮工程是以区（县）、乡（镇）、村（社区）三级
3、综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。4“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。5 定义定义 如果目标函数或约束条件中至少有一个是非线性函数如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题时的最优化问题就叫做非线性规划问题二二 非现性规划的基本概念非现性规划的基本概念 一般形式一般形式: （1） 其中 ， 是定义在 En 上的实值函数，简记: Xfmin .,
4、.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情况其它情况: : 求目标函数的最大值或约束条件为小于等于零求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式的情况，都可通过取其相反数化为上述一般形式“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。6 定义定义1 1 把满足问题（把满足问题（1 1）中条件的解）中条件的解 称为称为可
5、行解可行解（或可行（或可行点点），所有可行点的集合称为），所有可行点的集合称为可行集可行集（或（或可行域可行域）记为）记为D D即即 问题问题(1)(1)可简记可简记为为 njiEXXhXgXD, 0, 0|)(nEX XfDXmin定义定义2 2 对于问题对于问题(1)(1)，设，设 ，若存在，若存在 , ,使得对一切使得对一切 ，且，且 ，都有，都有 ，则称，则称X X* *是是f(X)f(X)在在D D上的上的局部极小值点局部极小值点（局部最优解局部最优解）特别地当）特别地当 时，时，若若 ，则称，则称X X* *是是f(X)f(X)在在D D上的上的严格局部极小值点严格局部极小值点（严
6、格局严格局部最优解部最优解）DX *0DX *XX*XX XfXf* XfXf*定义定义3 3 对于问题对于问题(1),(1),设设 , ,对任意的对任意的 , ,都有都有 则称则称X X* *是是f(X)f(X)在在D D上的上的全局极小值点全局极小值点（全局最优解全局最优解）特别地当）特别地当 时，若时，若 ，则称，则称X X* *是是f(X)f(X)在在D D上的上的严格全局极小值严格全局极小值点点（严格全局最优解严格全局最优解）DX *DX XfXf*XX XfXf*“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视
7、频监控联网应用为重点的“群众性治安防控工程”。7 定义定义 如果目标函数或约束条件中至少有一个是非线性函数如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题时的最优化问题就叫做非线性规划问题非现性规划的基本概念非现性规划的基本概念 一般形式一般形式: : （1 1） 其中其中 ， 是定义在是定义在 E En n 上的实值函上的实值函数，简记数，简记: : Xfmin .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情况其它情况: : 求目标函数的
8、最大值或约束条件为小于等于零求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式的情况，都可通过取其相反数化为上述一般形式“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。8 定义定义1 1 把满足问题（把满足问题（1 1）中条件的解）中条件的解 称为称为可行解可行解（或可行（或可行点点），所有可行点的集合称为），所有可行点的集合称为可行集可行集（或（或可行域可行域）记为）记为D D即即 问题问题(1)(1)可简记可简记为为 njiEXXhXgXD,
9、 0, 0|)(nEX XfDXmin定义定义2 2 对于问题对于问题(1)(1)，设，设 ，若存在，若存在 , ,使得对一切使得对一切 ，且，且 ，都有，都有 ，则称，则称X X* *是是f(X)f(X)在在D D上的上的局部极小值点（局部最优解）特别地当局部极小值点（局部最优解）特别地当 时，时，若若 ，则称，则称X X* *是是f(X)f(X)在在D D上的严格局部极小值点（严格局上的严格局部极小值点（严格局部最优解）部最优解）DX *0DX *XX*XX XfXf* XfXf*定义定义3 3 对于问题对于问题(1),(1),设设 , ,对任意的对任意的 , ,都有都有 则称则称X X*
10、 *是是f(X)f(X)在在D D上的全局极小值点（全局最优解）特别地当上的全局极小值点（全局最优解）特别地当 时，若时，若 ，则称，则称X X* *是是f(X)f(X)在在D D上的严格全局极小值上的严格全局极小值点（严格全局最优解）点（严格全局最优解）DX *DX XfXf*XX XfXf*“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。9 01 01 0-1 .)( min2121222121xxxxtsxxxxf，线性规划问题：线性规划问题：用图解法求解下面的非用图解法
11、求解下面的非三三. 非线性规划的图解法非线性规划的图解法“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。10三角形表示的是可行域。三角形表示的是可行域。同心圆表示的是目标函数的等值同心圆表示的是目标函数的等值线。线。最优解为（最优解为（1/2，1/2） 最优值为最优值为1/2问题：问题：(1/2,1/2)是整体的还是局部的？是严格的还是非是整体的还是局部的？是严格的还是非严格的？严格的？1/21/2“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化
12、为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。112、非线性规划方法概述、非线性规划方法概述微分学方法的局限性：微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有需要解复杂的方程组，而方程组到目前仍没有有效的算法。效的算法。实际的问题可能含有不等式约束，微分学方法不实际的问题可能含有不等式约束，微分学方法不易处理。易处理。“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为
13、重点的“群众性治安防控工程”。12数值方法的基本思路：数值方法的基本思路：迭代迭代给定初始点给定初始点x0根据根据x0,依次迭代产生点列依次迭代产生点列xkxk的最后一点为最优解的最后一点为最优解xk有限有限xk无限无限xk收敛于最优解收敛于最优解“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。13迭代格式迭代格式xkxk+1kx kkkxxx 1pkkkkptx kkkxxx 1称称pk为第为第k轮轮搜索方向搜索方向，tk为第为第k轮沿轮沿pk方向的方向的步长步长。产生产生t
14、k和和pk的不同方法，形成了不同的算法。的不同方法，形成了不同的算法。“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。14，使使若若存存在在设设0, 0,:1 pRpRxRRfnnn), 0( ),()( txftpxf处处的的下下降降方方向向。在在点点是是函函数数则则称称向向量量xxfp)(处处下下降降最最快快的的方方向向。在在就就是是可可导导，则则在在若若xxfxfxxf)()(-)( 定义：下降方向定义：下降方向“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指
15、挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。15，使使得得若若存存在在设设0t, 0, pRpXxRXnnXtpx 的的可可行行方方向向。关关于于处处是是点点则则称称向向量量Xxp定义定义解非线性规划问题，关键在于解非线性规划问题，关键在于找到某个方向，使得在此方向找到某个方向，使得在此方向上，目标函数得到下降，同时上，目标函数得到下降，同时还是可行方向。还是可行方向。这样的方向称为可行下降方向。这样的方向称为可行下降方向。“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以
16、公共安全视频监控联网应用为重点的“群众性治安防控工程”。16第二节第二节 凸函数和凸规划凸函数和凸规划1、凸函数及其性质：、凸函数及其性质：）有，（若对是非空凸集，设10,:1RSfRSn定义定义上上是是凸凸的的。在在上上的的凸凸函函数数，或或是是则则称称SSff121212(1)() (1) (),fxxf xf xx xS 若若上上是是严严格格凸凸的的。在在上上的的严严格格凸凸函函数数，或或是是则则称称SSff凹凹的的。严严格格上上是是在在或或凹凹函函数数严严格格上上的的是是凸凸函函数数，称称严严格格上上的的是是若若)(S,)(S)(Sfff 121211fXXf Xf X 1XS 2XS
17、， “雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。17是非空凸集是非空凸集设设nRS 定理定理:上上的的凸凸函函数数；是是，则则上上的的凸凸函函数数，是是若若S0S)1(ff 上上的的凸凸函函数数。是是上上的的凸凸函函数数是是若若S,S,)2(2121ffff 关于凸函数的一些结论关于凸函数的一些结论定理定理:则集合则集合是凸函数是凸函数是非空凸集是非空凸集设设,1RcfRSn cxfSxcfHS )(|),(是凸集。是凸集。函数函数f在集合在集合S上关于上关于c的水平集的水
18、平集“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。18则则可可微微：是是非非空空开开凸凸集集，设设,S1RSfRn 条件是条件是上的凸函数的充分必要上的凸函数的充分必要是是）（S1fSxxxfxfxxxfT 2112121,),()()()(处的梯度。处的梯度。是函数在点是函数在点）（11111)(,)()(xxxfxxfxfTn 定理定理条件是条件是上的严格凸函数的充要上的严格凸函数的充要是是）（S2f212112121, ),()()()(xxSxxxfxfxxxfT n
19、=1时几何意义：可微函数是凸的等价于切线不在函数图时几何意义：可微函数是凸的等价于切线不在函数图像上方。像上方。“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。19定理定理逆逆命命题题不不成成立立）凸凸函函数数（此此时时上上的的严严格格是是上上是是正正定定矩矩阵阵时时，在在当当上上是是半半正正定定的的。在在是是上上的的凸凸函函数数的的充充要要条条件件是是则则二二阶阶连连续续可可导导是是非非空空开开凸凸集集设设,)(S)( ,:,S221SfSxfxfSfRSfRn nnnnxx
20、xfxxxfxxxfxxxfxfHessexf)(.)(.)(.)()()(2121211222矩阵，矩阵，称为称为“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。20 , 1 0 , 1 0 . miniqjxh pixgtsxfj）（）（）（2、凸规划及其性质：、凸规划及其性质： , 1 0 , 1 0 qjxhpixgRxXjin）（）（简简称称凸凸规规划划。）为为非非线线性性凸凸规规划划称称（上上的的凸凸函函数数是是是是凸凸集集若若,MPSfX凸规划定义：凸规划定义：“
21、雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。21定理定理）是凸规划。）是凸规划。（上的凸函数，则上的凸函数，则是是并且并且皆为线性函数，皆为线性函数，上的凸函数上的凸函数皆为皆为若若）（）（）（对于非线性规划对于非线性规划MPXfxhRxqjxh pixgtsxfMPjnij )(,)(g , 1 0 , 1 0 . min),(i 凸规划性质：凸规划性质：定理定理凸规划的任一局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。凸规划是以后重点讨论的一类非
22、线性规划凸规划是以后重点讨论的一类非线性规划凸函数凸函数线线性性函函数数“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。22第三节第三节 一维搜索方法一维搜索方法t为实数为实数一维搜索问题指目标函数为单变量的非线性规划问题。一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：又称线性搜索问题。其模型为：(t)min0 t什么叫一维搜索问题？什么叫一维搜索问题？(t)minmax0 tt 或或一般一维搜索问题一般一维搜索问题有效一维搜索问题有效一维搜索问题
23、“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。23一维搜索问题的算法分类：一维搜索问题的算法分类：精确一维搜索（最优一维搜索）精确一维搜索（最优一维搜索）非精确一维搜索（可接受一维搜索）非精确一维搜索（可接受一维搜索）本节内容：本节内容：两种精确一维搜索方法：两种精确一维搜索方法：0.618法，法，Newton法。法。两种非精确一维搜索方法：两种非精确一维搜索方法：Goldstein法法,Armijo法。法。“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、
24、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。241、0.618法（近似黄金分割法）法（近似黄金分割法）问题：问题：凸函数是不是单谷函数？严格凸函数是不凸函数是不是单谷函数？严格凸函数是不是单谷函数？单谷函数是不是凸函数？是单谷函数？单谷函数是不是凸函数？上的单谷函数上的单谷函数为为称称上严格递增上严格递增且在且在上严格递减上严格递减在在使得函数使得函数如果如果,)(,)(,batbttatbat 的单谷区间。的单谷区间。称为称为)(,tba 单谷函数单谷函数上唯一的极小点。上唯一的极小点。在在为为显然此时显然此时,)(batt “雪亮工程是
25、以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。25搜索法求解：搜索法求解：(t)min0 t(t)minmax0 tt 或或基本过程：基本过程：给出给出a,b,使得使得t*在在a,b中。中。a,b称为称为搜索区间搜索区间。迭代缩短迭代缩短a,b的长度。的长度。当当a,b的长度小于某个预设的值，或者导数的绝的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。对值小于某个预设的正数，则迭代终止。“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息
26、化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。26假定：已经确定了单谷区间假定：已经确定了单谷区间a,b(t)min0 t(t)minmax0 tt (t)min bta )(1t )(2t t)(1t )(2t tt1t2ababt1t2新搜索区间为新搜索区间为a,t2新搜索区间为新搜索区间为t1,b“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。27区间缩小比例的确定：区间缩小比例的确定：区间缩短比例为区间缩短比例为(t2-a)/(
27、b-a)缩短比例为缩短比例为(b-t1)/(b-a)缩短比例缩短比例 满足：满足：每次插入搜索点使得两个区间每次插入搜索点使得两个区间a,t2和和t1,b相等；相等；每次迭代都以相等的比例缩小区间。每次迭代都以相等的比例缩小区间。618. 0215 缩缩短短比比例例0.618法法)(1t )(2t )(1t )(2t t1t2ababt1t2退 出前一页后一页“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。28确定确定a,b,计算探索点计算探索点t1=a+0.382(b-a)t
28、2=a+0.618(b-a)0.618法解题步骤：法解题步骤：)()(21tt 是是否否 at2是是停止，输出停止，输出t1否否以以a,t2为新的搜索区间为新的搜索区间 1tb是是停止，输出停止，输出t2否否以以t1,b为新的搜索区间为新的搜索区间“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。29例：例：5 . 0,3 , 0 12)(min 30精度精度其中单谷区间其中单谷区间求解求解 tttt 解：解：t1t2)(1t )(2t 30t 1、第一轮：、第一轮：t1=1.1
29、46, t2=1.8546648. 3)(,2131. 0)(21 tt t200.5“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。302、第二轮：、第二轮：t2=1.146, t1=0.7082131. 0)(0611. 0)(21 tt t20=1.1460.53、第三轮：、第三轮：t1=0.438, t2=0.7082082. 0)(0611. 0)(12 tt b-t1=1.146-0.4380.51.8540t t2t11.4160 tt2t1“雪亮工程是以区（县）
30、、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。314、第四轮：、第四轮：t2=0.876, t1=0.7080798. 0)(0611. 0)(21 tt b-t1=1.146-0.7080.5输出：输出：t*=t2=0.876为最优解，最优值为为最优解，最优值为-0.07980 1.416tt1t2“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。322、Newton法法0)()(
31、),(min ttt 二二次次可可微微，其其中中考考虑虑Newton法基本思想：法基本思想：用探索点用探索点tk处的二阶处的二阶Taylor展开式近似代替目标展开式近似代替目标函数，以展开式的最小点为新的探索点。函数，以展开式的最小点为新的探索点。2)(21)()()(kkkkkttttttttg 展展开开式式：)()(:,0)(1kkkktttttg 求求导导得得的的点点的的最最小小点点即即导导数数为为“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。33解题步骤：解题步骤：给
32、定初始点给定初始点t1和精度和精度 1|( )|t 是是是是停止，输出停止，输出t10)(1 t 是是否否停止，解题失败停止，解题失败)()(1112tttt 计计算算21|tt 否否停止，输出停止，输出t2否否“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。34例：例： txdxt0arctan)(min 求求解解解：解：取取t1=1,计算：计算：211)(,arctan)(tttt 迭代过程如下表：迭代过程如下表：1.1370.11630.11693-0.00106141.
33、3258-0.5178-0.5708220.785411kkt)(kt )(kt 退 出前一页后一页“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。353、非精确一维搜索法、非精确一维搜索法数值方法的关键是从一个点迭代到下一个点。数值方法的关键是从一个点迭代到下一个点。确定下一个点的关键是确定搜索方向和步长确定下一个点的关键是确定搜索方向和步长如果已经确定了搜索方向如果已经确定了搜索方向pk,则只要确定一个最佳则只要确定一个最佳的步长即可。的步长即可。所谓的最佳步长即是在所谓的
34、最佳步长即是在pk方向上走一个最好的长方向上走一个最好的长度使得目标函数下降的最多，即下述的最优化问题：度使得目标函数下降的最多，即下述的最优化问题：)(min0kkttpxf 这样的最优化问题不需要太高的精度，只要满这样的最优化问题不需要太高的精度，只要满足某些更宽松的精度要求即可。足某些更宽松的精度要求即可。这样的搜索方法称之为这样的搜索方法称之为非精确一维搜索方法非精确一维搜索方法“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。36Goldstein法原理：法原理：yt0
35、)(ty bcda,dcbatk 在在下下面面的的直直线线上上方方。同同时时保保证证在在上上面面的的直直线线的的下下方方，使使得得选选取取)()(kkkttt Y= (0)+ (0)tY= (0)+ m2 (0)tY= (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
36、=t0, t1=(a+b)/2否否a=t0,b=b, t1=(a+b)/2 (若若b=+,则则t1= a)退 出前一页后一页“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。38Armijo法原理：法原理：yt0)(ty tk)(kt Mtk)(kMt 在在直直线线上上方方。同同时时保保证证在在直直线线的的下下方方，使使得得选选取取)()(kkkMttt 退 出前一页后一页“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、
37、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。39第四节第四节 无约束最优化方法无约束最优化方法本节课讨论本节课讨论n元函数的无约束非线性规划问题：元函数的无约束非线性规划问题：nTnRxxxxxf ).,(),(min21其其中中求解此类模型求解此类模型(UMP)的方法称为的方法称为无约束最优化方法无约束最优化方法。无约束最优化方法通常有两类：无约束最优化方法通常有两类：解析法：解析法：要使用导数的方法；要使用导数的方法；直接法：直接法：无须考虑函数是否可导，直接使用函数值。无须考虑函数是否可导，直接使用函数值。“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、
38、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。401、无约束问题的最优性条件、无约束问题的最优性条件处处可可微微，在在点点设设nnRxRRf :使使若若存存在在,nRp 0)( pxfT处处的的下下降降方方向向在在点点是是则则向向量量xfp定理定理1定理定理2,*可微可微在点在点设设nRxf 的的局局部部最最优优解解是是若若)(min*xfx0)(* xf则则梯度为梯度为0的点称为函数的的点称为函数的驻点。驻点。驻点可能是极小点，也可能是极大点，也可能即不是极大驻点可能是极小点，也可能是极大点，也可能即不是极大也不是极小，这时称为函数的也不是
39、极小，这时称为函数的鞍点。鞍点。定理定理2说明：说明：UMP问题的局部最优解必是目标函数的驻点。问题的局部最优解必是目标函数的驻点。注：注：退 出前一页后一页“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。41定理定理3存存在在，矩矩阵阵处处的的在在点点设设)(*2*xfHesseRxfn 正正定定并并且且若若)(, 0)(*2*xfxf 的的严严格格局局部部最最优优解解是是则则)(min*xfx定理定理4上上的的可可微微凸凸函函数数是是设设nnnRfRxRRf,:*1 ，则，
40、则若若0)(* xf的的整整体体最最优优解解是是则则)(min*xfx课下练习课下练习：画图理解定理：画图理解定理1、2、4的几何意义。的几何意义。退 出前一页后一页“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。42 给定初始点nEX0，允许误差0,令 k=0； 计算kXf； 检验是否满足收敛性的判别准则： kXf， 若满足，则停止迭代，得点kXX*，否则进行； 令kkXfS，从kX出发，沿kS进行一维搜索， 即求k使得： kkkkkSXfSXf0min； 令kkkkSXX1
41、，k=k+1 返回.无约束优化问题的基本算法无约束优化问题的基本算法 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位最速下降法是一种最基本的算法，它在最优化方法中占有重要地位. .最最速下降法的优点是工作量小，存储变量较少速下降法的优点是工作量小，存储变量较少, ,初始点要求不高；缺点是收初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法值点时，宜选用别种收敛快的算法. . 1 1最速下降法（共轭梯度法）算法步骤：最速下降法（共轭梯度法）算法步骤：“雪
42、亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。432 2牛顿法算法步骤：牛顿法算法步骤：(1) 选定初始点nEX0，给定允许误差0，令 k=0；(2) 求kXf,12kXf,检验：若kXf,则 停止迭代,kXX*.否则, 转向(3)；(3) 令 kkkXfXfS12（牛顿方向） ； (4) kkkSXX1,1 kk,转回(2). 如果如果f f是对称正定矩阵是对称正定矩阵A A的二次函数，则用牛顿法经过一次迭代的二次函数，则用牛顿法经过一次迭代就可达到最优点就可达到最优点, ,如
43、不是二次函数，则牛顿法不能一步达到极值点，如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似但由于这种函数在极值点附近和二次函数很近似, ,因此牛顿法的收因此牛顿法的收敛速度还是很快的敛速度还是很快的. . 牛顿法的收敛速度虽然较快，但要求牛顿法的收敛速度虽然较快，但要求HessianHessian矩阵要可逆，矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量. .“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网
44、应用为重点的“群众性治安防控工程”。443 3拟牛顿法拟牛顿法“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。45用用MatlabMatlab解无约束优化问题解无约束优化问题 1. 一一元元函函数数无无约约束束优优化化问问题题: : min f（x） 21xxx 其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。 函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：常用格式如下：（1）x= f
45、minbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2) )（2）x= fminbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2 ，options)options)（3）xx，fval= fminbndfval= fminbnd（.）（4）xx，fvalfval，exitflag= fminbndexitflag= fminbnd（.）（5）xx，fvalfval，exitflagexitflag，output= fminbndoutput= fminbnd（.）“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化
46、为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。46运行结果： xmin = 3.9270 ymin = -0.0279 xmax = 0.7854 ymax = 0.6448 例例 1 1 求 f = 2xexsin在 0 x8 中的最小值与最大值 主程序为主程序为: 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、级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。47例例2 2 对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？p156，例8-1解解先编写先编写M M文件文件fminbndtest.mfminbndtest.m如下如下: : function f=myfun(x) f=-(3-2*x).2*x;主程序调用主程序调用fminbnd:fminbnd: x,fval=fminbnd(fminbndtest,0,1.5); xmax=x fmax=-fval运算结果为运算结果为:
48、 : xmax = 0.5000,fmax =2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。48 命令格式为命令格式为: :（1 1）x= fminuncx= fminunc（fun,Xfun,X0 0 ）；或）；或x=fminsearchx=fminsearch（fun,Xfun,X0 0 ）（2 2）x= fminuncx= fminunc（fun,Xfun,X0 0 ，optionsopt
49、ions）；）； 或或x=fminsearchx=fminsearch（fun,Xfun,X0 0 ，optionsoptions）（3 3）xx，fval= fminuncfval= fminunc（.）；）； 或或xx，fval= fminsearchfval= fminsearch（.）（4 4）xx，fvalfval，exitflag= fminuncexitflag= fminunc（.）；）； 或或xx，fvalfval，exitflag= fminsearchexitflag= fminsearch（5 5）xx，fvalfval，exitflagexitflag，output=
50、 fminuncoutput= fminunc（.）；）； 或或xx，fvalfval，exitflagexitflag，output= fminsearchoutput= fminsearch（.） 2、多元函数无约束优化问题、多元函数无约束优化问题标准型为标准型为：min F(X)“雪亮工程是以区（县）、乡（镇）、村（社区）三级综治中心为指挥平台、以综治信息化为支撑、以网格化管理为基础、以公共安全视频监控联网应用为重点的“群众性治安防控工程”。493 fminunc为中型优化算法的步长一维搜索提供了两种算法， 由options中参数LineSearchType控制：LineSearchTy