《高级运筹学》无约束非线性规划.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)
《《高级运筹学》无约束非线性规划.ppt》由会员分享,可在线阅读,更多相关《《高级运筹学》无约束非线性规划.ppt(74页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、无约束非线性规划无约束非线性规划 20152015年年5 5月月研究生研究生高级运筹学高级运筹学课件课件本章内容本章内容第一节:最优性条件第一节:最优性条件第二节:一维搜索第二节:一维搜索第三节:最速下降法和共轭梯度法第三节:最速下降法和共轭梯度法第四节:牛顿法和拟牛顿法第四节:牛顿法和拟牛顿法第一节第一节:最优性条件最优性条件本章仅讨论如下无约束非线性规划问题:假定f(x)具有二阶连续偏导数。现有多元函数 f(x1,x2,xn),若点 x(0)=(x10,x20,xn0)T 存在一邻域(x(0),使对任意x(x(0),均有f(x(0)f(x),则称 x(0)是 f(x)的局部极小点。一、一、
2、无约束极小化问题的最优性条件无约束极小化问题的最优性条件无约束极小化问题的最优解必是f(x)的局部极小点。利用局部极小点的一阶必要条件,求多元函数极值问题往往化成求解 局部极小点的一阶必要条件:设函数f(x)在点x处可微,且x(0)为局部极小点,则必有即的问题该方程组很难求解,一般不采用此法。求解无约束非线性规划问题常用数值解法中的迭代法1.迭代法的基本思想:给定f(x)的极小点位置的一个初始估计x(0),依次计算产生一系列点x(k)(1,2,),希望点列x(k)的极限x*就是f(x)的一个极小点。计算公式:其中:不同算法的区别在于得出搜索方向和步长的方式不同。二、迭代法2.选择搜索方向和步长
3、的原则:(1)目标函数值逐次减小,这种算法称为下降算法。(2)算法具有收敛性。即:序列中的某一点,或序列的极限点是函数的极小点。3.迭代法的基本步骤:(1)选择初始点x(0);(2)如已得到的迭代点x(k)不是最优解,确定从x(k)点出发 的搜索方向d(k),使f(x)沿d(k)方向可以找到x(k+1),目标函数有所下降。(3)在射线x(k)+d(k)(0)上选取步长k,使从而确定下一个点(4)检验新得到的点x(k+1)是否为最优或近似最优,若是则停止迭代,否则继续迭代。检验方法:第二节:一维搜索第二节:一维搜索在在求求解解无无约约束束非非线线性性规规划划的的算算法法中中,要要进进行行一一系系
4、列列如如下下格格式式的迭代计算的迭代计算:当方向当方向d(k)给定,求最佳步长给定,求最佳步长 k,就是求一元函数就是求一元函数的极小点问题的极小点问题。这一过程称为一维搜索这一过程称为一维搜索。一、一维搜索的定义一、一维搜索的定义二、一维搜索的方法:二、一维搜索的方法:1.精确线搜索,即解方程:精确线搜索,即解方程:2.试探法;按照某种方式找试探点,通过一系列试探点试探法;按照某种方式找试探点,通过一系列试探点的比较确定极小点。的比较确定极小点。3.函数逼近法:用较简单的曲线近似代替原来的曲线,函数逼近法:用较简单的曲线近似代替原来的曲线,用近似曲线的极小点来估计原曲线的极小点。用近似曲线的
5、极小点来估计原曲线的极小点。三、一维搜索的基本思想:三、一维搜索的基本思想:1.1.单谷单谷(峰)区间峰)区间 在给定区间内仅有一个谷值在给定区间内仅有一个谷值(极大或极小极大或极小)的函数称为单的函数称为单谷函数,其区间称为单谷区间谷函数,其区间称为单谷区间xabx*f(x)函数值:大小大图形:高低高单谷区间中一定有极小点2.2.一维搜索的基本思想一维搜索的基本思想 (1 1)确定初始单谷区间)确定初始单谷区间 (2 2)根据区间消去法原理逐步缩小此区间)根据区间消去法原理逐步缩小此区间 (3 3)根据迭代精度要求确定最优解的近似值)根据迭代精度要求确定最优解的近似值(1)确定初始单谷区间的
6、进退法确定初始单谷区间的进退法基本思想:基本思想:基本思想:基本思想:对对f(x)任选一个初始点任选一个初始点a1及初始步长及初始步长h h,通过比较这,通过比较这两点函数值的大小,确定第三点位置,比较这三点的函两点函数值的大小,确定第三点位置,比较这三点的函数值大小,确定是否为数值大小,确定是否为 “高高低低高高”形态形态计算步骤计算步骤计算步骤计算步骤Step1.Step1.选定初始点选定初始点a1,初始步长,初始步长h,计算,计算 f 1f(a1),f 2f(a1+h)Step2.Step2.比较比较f 1和和f 2。(a)如)如f 1 f 2,向右前进;加大步长向右前进;加大步长 h
7、2 h,转,转step3 向前探测向前探测 (b)如)如f 1 f 2,向左后退;向左后退;h-h,转(,转(3)向后探测,)向后探测,(c)如)如f 1 f 2,极小点在,极小点在a1 a1 h 之间。之间。Step3.产生新的探测点产生新的探测点 a3a1h,f3f(a3);Step4.比较函数值比较函数值 f2与与f3:(a)如)如f20时,时,a,b=a1,a3;hf3,加大步长加大步长 h2 h,a1=a2,a2=a3,转转step3 继继 续探测续探测(2)消去法的基本原理消去法的基本原理单谷区间确定后,假定在区间内任取两点单谷区间确定后,假定在区间内任取两点a1,b1;且且 a1
8、 b1。计算函数值,计算函数值,f1f(a1),),f2f(b1)有下列三种情况有下列三种情况:f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1综合为两种情况:综合为两种情况:若若f(a1)f(b1),则取则取 a,b1为缩短后的搜索区间。为缩短后的搜索区间。若若f(a1)f(b1),则取则取 a1,b为缩短后的搜索区间。为缩短后的搜索区间。四、四、黄金分割法黄金分割法 (0.6180.618法)法)黄金分割律是公元前六世纪,希腊的大数学家毕达哥拉斯发现黄金分割律是公元前六世纪,希腊的大数学家毕达哥拉斯发现的:如果把一条线段分成两部分,长段
9、和短段的长度之比是的:如果把一条线段分成两部分,长段和短段的长度之比是1:0.6181:0.618,整条线段和长段的比也是,整条线段和长段的比也是1:0.6181:0.618时,才是和黄金一时,才是和黄金一样最完美的分割,进行分割的这个点就叫黄金分割点样最完美的分割,进行分割的这个点就叫黄金分割点 黄金分割法适用于黄金分割法适用于a,ba,b区间上的任何单谷函数求极小值问区间上的任何单谷函数求极小值问题。对函数除要求题。对函数除要求“单谷单谷”外不作其他要求,甚至可以不连续。外不作其他要求,甚至可以不连续。因此,这种方法的适应面相当广因此,这种方法的适应面相当广.黄金分割法也是建立在区间消去法
10、原理基础上的试探方法。黄金分割法也是建立在区间消去法原理基础上的试探方法。在搜索区间在搜索区间a,ba,b内适当插入两点内适当插入两点 1,2,将区间分成三段;,将区间分成三段;利用区间消去法,使搜索区间缩小,通过迭代计算,使搜索利用区间消去法,使搜索区间缩小,通过迭代计算,使搜索区间无限缩小,从而得到极小点的数值近似解区间无限缩小,从而得到极小点的数值近似解黄金分割法还要求在保留下来的区间内再插入一点所形成黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段,与原来区间的三段具有相同的比例分布的区间新三段,与原来区间的三段具有相同的比例分布1 2 将区间分成三段黄金分割法要求插入两
11、点:黄金分割法要求插入两点:黄金分割法区间消去示意:aba1a2f(a1)f(a2)aba1a2f(a1)f(a2)黄金分割法的搜索过程:黄金分割法的搜索过程:1 1)给出初始搜索区间及收敛精度)给出初始搜索区间及收敛精度,将,将 赋以赋以0.6180.618。2 2)按坐标点计算公式计算)按坐标点计算公式计算 1,2;并计算其对应的函数值并计算其对应的函数值f1,f2。3 3)根据区间消去法原理缩短搜索区间。为了能用原来的坐标)根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式,需进行区间名称的代换,并在保留区间中计算一点计算公式,需进行区间名称的代换,并在保留区间中计算一个新的试
12、验点及其函数值。个新的试验点及其函数值。如果如果f1f2,则新区间则新区间a,a,2 2,令令b=b=2,2=1,f2=f1,记记N0=0;如果如果f1 f2,则新区间则新区间 1,b,令令 a=1,1=2,f1=f2,记记N0=1;4 4)若)若b-a-1.1252-0.2360.2360.5281-1.125-1.12540.0560.2360.3480.528-1.125-1.12560.1680.2360.2790.348-1.125-1.12370.1680.279经过经过6次迭代,次迭代,b-a=0.1110.16,满足精度要求,取满足精度要求,取问题的精确最优解为问题的精确最优解
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高级运筹学 高级 运筹学 无约束 非线性 规划
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内