第三章一维优化方法.ppt

1第三章　第三章　一维优化方法一维优化方法 3.1 搜索区间的确定搜索区间的确定 进退法进退法 3.2一维搜索的最优化方法一维搜索的最优化方法3.2.1 格点法格点法3.2.2 黄金分割法黄金分割法3.2.3 二次插值法二次插值法2第三章第三章 一维优化方法一维优化方法 用数值迭代法求解一元函数的极小点和极小值方法称为一维搜用数值迭代法求解一元函数的极小点和极小值方法称为一维搜索优化方法索优化方法多维优化问题常常是通过一系列的一维优化方法来实现的因当搜多维优化问题常常是通过一系列的一维优化方法来实现的因当搜索方向索方向 确定后，新设计点确定后，新设计点 总是位于过点总是位于过点 的的 方向上步长方向上步长 不同不同, 得到的设计点和相应的函数值得到的设计点和相应的函数值就不同，即只有一个就不同，即只有一个 变量3ox1x2由前基本迭代公式由前基本迭代公式:待求待求已知已知这种在给定方向上确定最优步长的过程这种在给定方向上确定最优步长的过程, ,称一维优称一维优化。

化 称为最优步长称为最优步长 4n维问题维问题一系列一系列一维优化问题一维优化问题53.1 3.1 搜索区间的确定搜索区间的确定单峰函数单峰函数 用尽量少的计算量用尽量少的计算量,尽快确尽快确定包含定包含x* 的区间的区间[a, b] 关键关键找三点找三点: :“高高- -低低- -高高”一维搜索最优化过程可分为两步一维搜索最优化过程可分为两步: :1 1、确定极小点所在的初始搜索区间、确定极小点所在的初始搜索区间[a[a，，b]b]2 2、在区间、在区间[a[a，，b]b]中搜索极小点中搜索极小点 采用某种方法将此区间逐步缩小，使其达到包含极小点采用某种方法将此区间逐步缩小，使其达到包含极小点x*在内在内 的很小邻域（的很小邻域（ε ）） 63.1 3.1 搜索区间的确定（进退法）搜索区间的确定（进退法）函数为函数为y＝＝f(x), 给定初始点给定初始点x1,选定恰当的初始步长为选定恰当的初始步长为h0 一、试探搜索一、试探搜索由于最小点由于最小点x*的位置是未知的的位置是未知的，所以首先要试探最小点，所以首先要试探最小点x*位于初始点位于初始点x1的左方的左方或右方，然后再确定是前进还是后退或右方，然后再确定是前进还是后退比较比较y1、、y2大小大小 前进前进后退后退二、前进搜索二、前进搜索比较比较y y2 2、、y y3 3大小：大小： [a, b]确定确定继续前进继续前进置换点号置换点号7由前：由前：三、后退搜索三、后退搜索比较比较y y1 1、、y y2 2大小大小 前进前进后退后退比较比较y y2 2、、y y3 3大小：大小： [a, b]确定确定继续后退继续后退置换点号置换点号89例例题题3.1 试试用用进进退退法法确确定定函函数数f(x)=x2- -6x+9的的一一维维优优化化搜搜索索区区间间[a，，b]。

设初始点设初始点x1＝＝0，初始步长，初始步长h0=1解：按流程图解：按流程图3.4，计算过程如下：，计算过程如下： 由于由于y y2 2y>y3 3，再作前进搜索，，再作前进搜索， x x1 1←x x2 2=1=1，，y y1 1←y y2 2=4=4 x x2 2←x x3 3=3=3，，y y2 2←y y3 3=0=0 h h←2h=42h=4 x x3 3←x x2 2+h=7+h=7，，y y3 3＝＝f(xf(x3 3)=16)=16 再比较再比较y y2 2与与y y3 3，有，有y y2 2

复杂问题中 12第一种情况：第一种情况：可丢掉可丢掉 部分部分基本思想基本思想:逐步缩小搜索区间逐步缩小搜索区间,直至最小点存在的范围达到允许的直至最小点存在的范围达到允许的 误差范围为止误差范围为止.取中间点为极小点取中间点为极小点.在在[a,b]内任取两点内任取两点 , 且且 计算函数值计算函数值: 进行比较可得进行比较可得:3.2.2 黄金分割法黄金分割法13第二种情况：第二种情况：第三种情况：第三种情况：可丢掉可丢掉 部分部分问题问题1:λ= =?问题问题2:如何取点如何取点?14由此得由此得解此方程得两个根取其正根为解此方程得两个根取其正根为 =0.6180339887=0.6180339887… 15问题问题2:如何取点如何取点?取点规则取点规则:右图示右图示,第一次区间缩短第一次区间缩短:第二次区间缩短第二次区间缩短:16终止准则终止准则: :17例例题3.3试用黄金分割法求目用黄金分割法求目标函数函数f(x)=x2-6x+9的最的最优解。

解给定初始区定初始区间[1，，7]，收，收敛精度精度ε＝＝0.4解：第一次区间缩短：解：第一次区间缩短： 计算两内点及对应函数值：计算两内点及对应函数值：         x1=a+0.382(b-a)=3.292，，y1=f(x1)=0.085264         x2=a+0.618(b-a)=4.708，，y2=f(x2)=2.917264 作函数值比较，可见作函数值比较，可见y1ε 第二次区间缩短第二次区间缩短: 置换置换：： x2←x1=3.292，，y2←y1=0.085 264      增补增补: x1=a(1)+0.382(b(1)- -a(1))＝＝2.416456，，                  y1=f(x1)=0.340524 18各次各次缩短区短区间的的计算数据算数据见表表3.2第六次区第六次区间缩短的端点短的端点a(6)＝＝2.750 917，，b(6)＝＝3.085 305，，b(6)-a(6)＝＝0.334 388<ε，，满足精度要求，足精度要求，终止止计算。

算取最取最优解解为:19基本原理基本原理: :利用一个低次插值多项式来逼近原目标函数利用一个低次插值多项式来逼近原目标函数, ,然然后求该多项式的极小点后求该多项式的极小点, ,并以此作为目标函数的近似极并以此作为目标函数的近似极小点小点, ,……反复使用此法反复使用此法, ,逐次拟合逐次拟合, ,直到满足给定的精直到满足给定的精度为止度为止. . 常用的插值多项式为二次或三次多项式常用的插值多项式为二次或三次多项式, ,分别称为二分别称为二次插值法或三次插值法次插值法或三次插值法一、二次插值函数的构成一、二次插值函数的构成：：p(x)=Axp(x)=Ax2 2+Bx+C +Bx+C 式中式中A A、、B B、、C C为待定系数，为待定系数，可由可由P P1 1、、P P2 2、、P P3 3三个插值结点三个插值结点的信息按下列线性方程组确定的信息按下列线性方程组确定3.2.3 二次插值法二次插值法20f(x)搜索区间为搜索区间为[a，，b]取点取点x1、、x2、、x3，构成二次函数，构成二次函数开始时开始时:计算计算得三点得三点:作插值函数作插值函数p(x)解方程组，得待定系数解方程组，得待定系数A、、B、、C 求求p(x)的极小点的极小点x*P ，与，与x2比较比较→→区间缩短区间缩短x1=ax3=b21一、二次插值函数的构成一、二次插值函数的构成 解方程组，得待定系数解方程组，得待定系数A、、B、、C 22求二次插值函数的极小点：求二次插值函数的极小点： 23二、二、区间区间的的缩短缩短24区间区间的的缩短程序框图缩短程序框图25三、终止准则三、终止准则 2627在在流流程程图图中中有有两两个个判判别别框框的的内内容容需需稍稍加加说说明明。

其其一一是是c2=0？？若若成成立，即：立，即：或写作或写作这这说说明明三三个个插插值值结结点点P1(x1，，f1)、、P2(x2，，f2)、、P3(x3，，f3)在在同同一一条条直直线上；其二是线上；其二是( - -x1)(x3- - )≤0？？(3.14)若成立，则说明若成立，则说明 落在区间落在区间[x1，，x3]之外以以上上两两种种情情况况只只是是在在区区间间已已缩缩得得很很小小，，三三个个插插值值结结点点已已十十分分接接近近的的时时候候，，由由于于计计算算机机的的舍舍人人误误差差才才可可能能导导致致其其发发生生因因此此对对这这种种情情况的合理处置就是把中间插值点况的合理处置就是把中间插值点x2及其函数值及其函数值f2作为最优解输出作为最优解输出 282930小小 结结一维优化方法一维优化方法一维优化方法一维优化方法直接法直接法直接法直接法: : 直接利用直接利用直接利用直接利用原函数原函数原函数原函数f f( (x x) )的信息来决定区间的缩短的信息来决定区间的缩短的信息来决定区间的缩短的信息来决定区间的缩短间接法间接法间接法间接法：：：：利用利用利用利用原函数原函数原函数原函数f f( (x x) )的的的的信息构造一简单函数信息构造一简单函数信息构造一简单函数信息构造一简单函数 p p( (x x) )来近似代来近似代来近似代来近似代替替替替 原函数原函数原函数原函数f f( (x x) ) ，求得，求得，求得，求得p p( (x x) )的极小点的极小点的极小点的极小点，用，用，用，用p p( (x x) )的极小点的极小点的极小点的极小点 所对应的所对应的所对应的所对应的原函数原函数原函数原函数f f( (x x) )的信息来决定区间的缩短的信息来决定区间的缩短的信息来决定区间的缩短的信息来决定区间的缩短直接法：直接法：直接法：直接法：格点法、黄金分割法格点法、黄金分割法格点法、黄金分割法格点法、黄金分割法间接法：间接法：间接法：间接法：二次插值法二次插值法二次插值法二次插值法311 1、进退法、格点法、黄金分割法、二次插值法的、进退法、格点法、黄金分割法、二次插值法的、进退法、格点法、黄金分割法、二次插值法的、进退法、格点法、黄金分割法、二次插值法的 基本原理？基本原理？基本原理？基本原理？2 2、、、、P P5252题题题题1 1和题和题和题和题4 4。