非线性规划 (2)精选文档.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《非线性规划 (2)精选文档.ppt》由会员分享,可在线阅读,更多相关《非线性规划 (2)精选文档.ppt(70页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、非线性规划本讲稿第一页,共七十页1.非线性规划模型:非线性规划模型:数学规划模型的一般形式:数学规划模型的一般形式:其中其中,x=(x1,x2,xn)T,f(x),gi(x),hj(x)为为x的实值函数的实值函数简记为简记为MP(Mathematical Programming)退 出前一页后一页2.1 基本概念基本概念本讲稿第二页,共七十页可行域和可行解:可行域和可行解:称称为为MP问题的约束集或可行域。问题的约束集或可行域。若若x在在X内,称内,称x为为MP的可行解或者可行点。的可行解或者可行点。退 出前一页后一页本讲稿第三页,共七十页简记形式:简记形式:引入向量函数符号:引入向量函数符号
2、:退 出前一页后一页本讲稿第四页,共七十页数学规划问题的分类:数学规划问题的分类:若若f(x),gi(x),hj(x)为线性函数,即为为线性函数,即为线性规划线性规划(LP);若若f(x),gi(x),hj(x)至少一个为非线性,即为至少一个为非线性,即为非线性规划非线性规划(NLP);对于非线性规划,对于非线性规划,若没有若没有gi(x),hj(x)即即X=Rn,称为称为无约束非线无约束非线性规划性规划或或无约束最优化问题无约束最优化问题;否则称为;否则称为约束非线性规划或约束最优约束非线性规划或约束最优化问题化问题。退 出前一页后一页本讲稿第五页,共七十页最优解和极小点最优解和极小点 对于
3、数学规划(对于数学规划(MP),若),若 ,并且有,并且有如果有如果有定义定义:退 出前一页后一页本讲稿第六页,共七十页如果有如果有定义定义退 出前一页后一页本讲稿第七页,共七十页例例退 出前一页后一页本讲稿第八页,共七十页三角形表示的是可行域。三角形表示的是可行域。同心圆表示的是目标函数的等值线。同心圆表示的是目标函数的等值线。最优解为(最优解为(1/2,1/2)最优值为最优值为1/2问题:问题:(1/2,1/2)是整体的还是局部的?是严格的还是非严是整体的还是局部的?是严格的还是非严格的?格的?1/21/2退 出前一页后一页本讲稿第九页,共七十页2.非线性规划方法概述非线性规划方法概述微分
4、学方法的局限性:微分学方法的局限性:实际的问题中,函数可能是不连续或者不可微的。实际的问题中,函数可能是不连续或者不可微的。需要解复杂的方程组,而方程组到目前仍没有有效的算法。需要解复杂的方程组,而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束,微分学方法不易处理。实际的问题可能含有不等式约束,微分学方法不易处理。退 出前一页后一页本讲稿第十页,共七十页数值方法的基本思路:数值方法的基本思路:迭代迭代给定初始点给定初始点x0根据根据x0,依次迭代产生点列依次迭代产生点列xkxk的最后一点为最优解的最后一点为最优解xk有限有限xk无限无限xk收敛于最优解收敛于最优解退 出前一页后一页
5、本讲稿第十一页,共七十页迭代格式迭代格式xkxk+1pk称称pk为第为第k轮轮搜索方向搜索方向,tk为第为第k轮沿轮沿pk方向的方向的步长步长。产生产生tk和和pk的不同方法,形成了不同的算法。的不同方法,形成了不同的算法。退 出前一页后一页本讲稿第十二页,共七十页定义:下降方向定义:下降方向退 出前一页后一页本讲稿第十三页,共七十页定义定义解非线性规划问题,关键在于找解非线性规划问题,关键在于找到某个方向,使得在此方向上,到某个方向,使得在此方向上,目标函数得到下降,同时还是可目标函数得到下降,同时还是可行方向。行方向。这样的方向称为这样的方向称为可行下降方向。可行下降方向。退 出前一页后一
6、页本讲稿第十四页,共七十页1.凸函数及其性质:凸函数及其性质:定义定义退 出前一页后一页2.2 凸函数和凸规划凸函数和凸规划本讲稿第十五页,共七十页退 出前一页后一页本讲稿第十六页,共七十页定理定理:关于凸函数的一些结论关于凸函数的一些结论定理定理:是凸集。是凸集。函数函数f在集合在集合S上关于上关于c的水平集的水平集退 出前一页后一页本讲稿第十七页,共七十页定理定理?还有什么方法判断一个函数是凸函数呢?还有什么方法判断一个函数是凸函数呢?退 出前一页后一页本讲稿第十八页,共七十页退 出前一页后一页本讲稿第十九页,共七十页2.凸规划及其性质:凸规划及其性质:凸规划定义:凸规划定义:退 出前一页
7、后一页本讲稿第二十页,共七十页凸规划性质:凸规划性质:凸规划的任一局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。凸规划是以后重点讨论的一类非线性规划凸规划是以后重点讨论的一类非线性规划凸函数凸函数线性线性函数函数退 出前一页后一页本讲稿第二十一页,共七十页解:解:(1)目标函数是不是凸函数?)目标函数是不是凸函数?(2)gi(x)是不是凸函数?是不是凸函数?退 出前一页后一页本讲稿第二十二页,共七十页t为实数为实数一维搜索问题指目标函数为单变量的非线性规划问题。又称线性一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为:搜索问题。其模型为:什么
8、叫一维搜索问题?什么叫一维搜索问题?或或一般一维搜索问题一般一维搜索问题有效一维搜索问题有效一维搜索问题退 出前一页后一页2.3一维搜索方法一维搜索方法本讲稿第二十三页,共七十页一维搜索问题的算法分类:一维搜索问题的算法分类:精确一维搜索(最优一维搜索)精确一维搜索(最优一维搜索)非精确一维搜索(可接受一维搜索)非精确一维搜索(可接受一维搜索)本节内容:本节内容:两种精确一维搜索方法:两种精确一维搜索方法:0.618法,法,Newton法。法。两种非精确一维搜索方法:两种非精确一维搜索方法:Goldstein法法,Armijo法。法。退 出前一页后一页本讲稿第二十四页,共七十页1.0.618法
9、(近似黄金分割法)法(近似黄金分割法)问题:问题:凸函数是不是单谷函数?严格凸函数是不是凸函数是不是单谷函数?严格凸函数是不是单谷函数?单谷函数是不是凸函数?单谷函数?单谷函数是不是凸函数?单谷函数单谷函数退 出前一页后一页本讲稿第二十五页,共七十页搜索法求解:搜索法求解:或或基本过程:基本过程:给出给出a,b,使得使得t*在在a,b中。中。a,b称为称为搜索区间搜索区间。迭代缩短迭代缩短a,b的长度。的长度。当当a,b的长度小于某个预设的值,或者导数的绝对值的长度小于某个预设的值,或者导数的绝对值小于某个预设的正数,则迭代终止。小于某个预设的正数,则迭代终止。退 出前一页后一页本讲稿第二十六
10、页,共七十页假定:已经确定了单谷区间假定:已经确定了单谷区间a,bt1t2ababt1t2新搜索区间为新搜索区间为a,t2新搜索区间为新搜索区间为t1,b退 出前一页后一页本讲稿第二十七页,共七十页区间缩小比例的确定:区间缩小比例的确定:区间缩短比例为区间缩短比例为(t2-a)/(b-a)缩短比例为缩短比例为(b-t1)/(b-a)缩短比例缩短比例 满足:满足:每次插入搜索点使得两个区间每次插入搜索点使得两个区间a,t2和和t1,b相等;相等;每次迭代都以相等的比例缩小区间。每次迭代都以相等的比例缩小区间。0.618法法t1t2ababt1t2退 出前一页后一页本讲稿第二十八页,共七十页确定确
11、定a,b,计算探索点计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解题步骤:法解题步骤:是是否否是是停止,输出停止,输出t1否否以以a,t2为新的搜索区间为新的搜索区间是是停止,输出停止,输出t2否否以以t1,b为新的搜索区间为新的搜索区间退 出前一页后一页本讲稿第二十九页,共七十页例:例:解:解:t1t230t1.第一轮:第一轮:t1=1.146,t2=1.854t200.5退 出前一页后一页本讲稿第三十页,共七十页2.第二轮:第二轮:t2=1.146,t1=0.708t20=1.1460.53.第三轮:第三轮:t1=0.438,t2=0.708b-t1=
12、1.146-0.4380.51.8540tt2t11.4160tt2t1退 出前一页后一页本讲稿第三十一页,共七十页4.第四轮:第四轮:t2=0.876,t1=0.708b-t1=1.146-0.7080.5输出:输出:t*=t2=0.876为最优解,最优值为为最优解,最优值为-0.0798课下练习:参阅课下练习:参阅110页表格仔细分析上述迭代过程,体会页表格仔细分析上述迭代过程,体会0.618法的实质。法的实质。01.416tt1t2退 出前一页后一页本讲稿第三十二页,共七十页2.Newton法法Newton法基本思想:法基本思想:用探索点用探索点tk处的二阶处的二阶Taylor展开式近似
13、代替目标函数,展开式近似代替目标函数,以展开式的最小点为新的探索点。以展开式的最小点为新的探索点。退 出前一页后一页本讲稿第三十三页,共七十页解题步骤:解题步骤:给定初始点给定初始点t1和精度和精度是是是是停止,输出停止,输出t1是是否否停止,解题失败停止,解题失败否否停止,输出停止,输出t2否否退 出前一页后一页本讲稿第三十四页,共七十页例:例:解:解:取取t1=1,计算:计算:迭代过程如下表:迭代过程如下表:1.1370.11630.11693-0.00106141.3258-0.5178-0.5708220.785411退 出前一页后一页本讲稿第三十五页,共七十页3.非精确一维搜索法非精
14、确一维搜索法数值方法的关键是从一个点迭代到下一个点。数值方法的关键是从一个点迭代到下一个点。确定下一个点的关键是确定搜索方向和步长确定下一个点的关键是确定搜索方向和步长如果已经确定了搜索方向如果已经确定了搜索方向pk,则只要确定一个最佳则只要确定一个最佳的步长即可。的步长即可。所谓的最佳步长即是在所谓的最佳步长即是在pk方向上走一个最好的长度方向上走一个最好的长度使得目标函数下降的最多,即下述的最优化问题:使得目标函数下降的最多,即下述的最优化问题:这样的最优化问题不需要太高的精度,只要满足某些这样的最优化问题不需要太高的精度,只要满足某些更宽松的精度要求即可。更宽松的精度要求即可。这样的搜索
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 非线性规划 2精选文档 非线性 规划 精选 文档
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内