一维搜索.pptx

1 1首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:51 18:51第三章第三章第三章第三章 一维搜索方法一维搜索方法一维搜索方法一维搜索方法3.1概述概述3.2搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理3.3一维搜索的试探方法一维搜索的试探方法3.4一维搜索的插值方法一维搜索的插值方法重点2 2首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:51 18:513.13.1概述概述概述概述q回顾当采用数学规划法寻求多元函数 的极值点 时一般要进行一系列迭代计算：其中 为第 次迭代的搜索方向，为沿 搜索的最佳步长因子（通常也称作最佳步长）。当方向 给定，求最佳步长 就是求一元函数 的极值问题，它称作一维搜索。3 3首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:52 18:52q求多元函数极值点，需要进行一系列的一维搜索。可见一维搜索是优化搜索方法的基础。q求解一元函数 的极小点 ，可采用解析解法，在用函数 的导数求 时，所用的函数 是仅以步长因子 为变量的一元函数，而不是以设计点 为变量的多元函数 。1.利用一元函数的极值条件 求 。4 4首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:52 18:522.为了直接利用 的函数式求解最佳步长因子 。可把 或它的简写形式 进行泰勒展开，取到二阶项，即 将上式对 进行微分并令其等于零，给出 极值点 应满足的条件 从而求得5 5首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:52 18:52这里是直接利用函数 而不需要把它化成步长因子 。的函数 。不过，此时需要计算 点处的梯度 和海赛矩阵 。解析解法的缺点需要进行求导计算。对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。q因此，在优化设计中，求解最佳步长因子 主要采用数值解法，利用计算机通过反复迭代计算求得最佳步长因子的近似值。数值解法的基本思路是：首先确定 所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得 的数值近似解。返回返回6 6首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:52 18:523.23.2搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理q欲求一元函数 的极小点 ，首先必须先确定 所在的区间。确定搜索区间的外推法在一维搜索时，我们假设函数 具有如右图所示的单谷性，即在所考虑的区间内部，函数 有唯一的极小点 。为了确定极小点 所在的区间 ，应使函数 的 值在 区间里形成“高低高”趋势。7 7首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:53 18:53从 开始，以初始步长 向前试探。如果函数值上升，则步长变号，即改变试探方向。如果函数值下降，则维持原来的试探方向，并将步长加倍。区间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的“高低高”趋势。单谷区间8 8首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:53 18:53q外推法（进退法）确定搜索区间的步骤：v1）试探搜索v2）前进搜索v3）后退搜索9 9首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:53 18:53右图表示沿 的正向试探。每走一步都将区间的始点、中间点沿试探方向移动一步（进行换名）。经过三步最后确定搜索区间 ，并且得到区间始点、中间点和终点 所对应的函数值 。正向搜索的外推法1010首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:53 18:53右图所表示的情况是：开始是沿 的正方向试探，但由于函数值上升而改变了试探方向，最后得到始点，中间点和终点 及它们的对应函数值 ，从而形成单谷区间为一维搜索区间 。1111首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:54 18:54上述确定搜索区间的外推法，其程序框图如下图所示（P50）1212首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:54 18:54q要求一元函数 的极小点 ，在确定 所在的区间之后，就需要不断的缩小这个区间，直到确定 的近似解。区间消去法原理在搜索区间 内任取两点 ，并计算函数值 。于是将有下列三种可能情形：1.，如下图（a）所示。由于函数为单谷，所以极小点必在区间 内。2.，如下图（b）所示。同理，极小点应在区间 内。3.，如下图（c）所示，这时极小点应在 内。1414首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:54 18:54根据以上所述，只要在区间 内取两个点，算出它们的函数值并加以比较，就可以把搜索区间 缩短成 或 。对于第一种情况，我们已算出区间 内 点的函数值，如果要把搜索区间 进一步缩短，只需在其内再取一点算出函数值并与 加以比较，即可达到目的。对于第二种情况，同样只需再计算一点函数值就可以把搜索区间继续缩短。1515首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:54 18:54第三种情形与前面两种情形不同，因为在区间 内缺少已算出的函数值。要想把区间 进一步缩短，需在其内部取两个点（而不是一个点）计算出相应的函数值再加以比较才行。如果经常发生这种情形，为了缩短搜索区间，需要多计算一倍数量的函数值，这就增加了计算工作量。1616首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:55 18:55程序设计技巧为了避免多计算函数值，我们把第三种情形合并到前面两种情形中去。例如，可以把前面三种情形改为下列两种情形：1.若 ，则取 为缩短后的搜索区间。2.若 ，则取 为缩短后的搜索区间。从上述的分析中可知，为了每次缩短区间，只需要在区间内再插入一点并计算其函数值。如此反复进行下去，当搜索区间长度足够小时，可用区间内的某点作为极小点的近似值。q一维搜索方法的分类可以用不同的方法来确定的插入点的位置，这样就形成了不同的一维搜索方法。概括起来，可将一维搜索方法分成两大类：1717首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:55 18:55试探法（直接法）按某种给定的规律来确定区间内插入点的位置。此点位置的确定仅仅按照区间缩短如何加快，而不顾及函数值的分布关系。属于试探法一维搜索的有黄金分割法，裴波纳契（Fibonacci）法等。插值法（函数逼近法、间接法）根据某些点处的某些信息，如函数值、一阶导数、二阶导数等，构造一个插值函数来逼近原来函数，用插值函数的极小点作为区间的插入点。属于插值法一维搜索的有牛顿法（切线法）、二次插值法（抛物线法）、三次插值法等。以下我们分别讨论这两类一维搜索方法。1818首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:55 18:553.33.3一维搜索的试探方法一维搜索的试探方法一维搜索的试探方法一维搜索的试探方法0.6180.618法法法法q概述在搜索区间 内适当插入两点 ，并计算其函数值。将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。在实际计算中，最常用的一维搜索试探方法是黄金分割法，又称作0.618法。我们可以通过学习黄金分割法来了解一维搜索试探方法的基本思想。1919首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:55 18:55q黄金分割法黄金分割法是建立在区间消去法原理基础上的试探方法。适用于 区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。黄金分割法对插入点的要求：1）要求插入点 的位置相对于区间 两端点具有对称性，即 其中 为待定常数。2020首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:56 18:562）黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。即每次缩小所得的新区间长度与缩小前区间长度之比（即：区间收缩率）为定值。2121首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:56 18:56设原区间 长度为1如下图所示，保留下来的区间 长度为 ，区间缩短率为 。为了保持相同的比例分布，新插入点 应在 位置上，在原区间的 位置应相当于在保留区间的 位置。故有 取方程正数解，得2222首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:56 18:56若保留下来的区间为 ，根据插入点的对称性，也能推得同样的 值。所谓“黄金分割”是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值，即 算得 。黄金分割法能使相邻两次搜索区间都具有相同的缩短率0.618，所以黄金分割法又被称作0.618法。2323首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:56 18:56黄金分割法的搜索过程1.给出初始搜索区间 及收敛精度 ，将 赋以0.618。2.按坐标点计算公式计算 和 ，并计算其对应的函数值 。3.根据区间消去法原理缩短搜索区间程序设计技巧 为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。4.检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足则返回到步骤2。5.如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。2424首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:57 18:57黄金分割法的程序框图如右图所示（P52）。例子2525首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:57 18:573.43.4一维搜索的插值方法一维搜索的插值方法一维搜索的插值方法一维搜索的插值方法q概述插值法和试探法都是利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值近似解。一维搜索问题是在某一确定区间内寻求一元函数的极小点的位置，在某些情况下，如果没有函数表达式，但能够给出若干试验点处的函数值，就可以根据这些点处的函数值，利用插值法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。这种方法称作插值法，又称作函数逼近法。2626首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:57 18:57多项式是函数逼近的一种常用工具。在搜索区间内可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。常用的插值多项式为二次多项式。1.牛顿法（切线法）利用一点的函数值、一阶导数值和二阶导数值来构造二次函数。2.二次插值法（抛物线法）利用三个点的函数值形成一个抛物线来构造二次函数。2727首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:57 18:57q牛顿法（切线法）对于一维搜索函数 ，假定已给出极小点的一个较好的近似点 ，因为一个连续可微的函数在极小点附近与一个二次函数很接近，所以可在 点附近用一个二次函数 来逼近函数 ，即在 点将 进行泰勒展开并保留到二次项，有2828首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:58 18:58然后以二次函数 的极小点作为 极小点的一个新近似点 。根据极值必要条件 ：即 得 依此继续下去，可得牛顿法迭代公式2929首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:58 18:58右图是对牛顿法所作的几何解释 的极小点 应满足极值必要条件 。所以求 的极小点也就是求解 方程的根。故在 处用一抛物线 代替曲线 相当于用一斜线 代替曲线 。抛物线顶点 作为第一个近似点应处于斜线 与 轴的交点处。这样各个近似点是通过对 作切线求得与 轴的交点而找到的，所以牛顿法又称作切线法。3030首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:58 18:58牛顿法的计算步骤是：给定初始点 ，控制误差 ，并令 。1.计算 。2.求 。3.若 则求得近似解 ，停止计算，否则作4。4.令 转1。3131首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:58 18:58牛顿法的特点牛顿法最大的优点是收敛速度快。但是在每一点处都要计算函数的二阶导数，因而增加了每次迭代的工作量。特别是用数值微分代替二阶导数时，舍人误差会影响牛顿法的收敛速度。另外，牛顿法要求初始点选得比较好（离极小点不能太远），否则有可能使极小化序列发散或收敛到非极小点。3232首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:58 18:58q二次插值法（抛物线法）二次插值法是利用 在单谷区间中的三点 的相应函数值 ，作出如下的二次插值多项式 则它应满足条件3333首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:59 18:59则多项式 的极值点可从极值的必要条件求得为了确定这个极值点，只需计算出系数 和 。其方法法是利用 的联立方程组中相邻两个方程消去 ，从而得到关于 的方程组3434首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:59 18:59解得所以3535首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:59 18:59如果令 则 这样就得到了 极小点 的近似解 。如果区间长度 足够小，则由 便得出所要求的 的足够精确的极小点 。3636首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:59 18:59如果区间长度 不是足够小，则必须缩小区间 。根据区间消去法原理，需要已知区间内两点的函数值。其中点 的函数值 已知，另外一点可取 点并计算其函数值 。当 时取 为缩短后的搜索区间（如右图）。当 时取 为缩短后的搜索区间。3737首页上页下页末页结束2024/8/27 2024/8/27 周二周二 19:00 19:00在缩短后的新区间内再用二次插值法插人新的极小点近似值 （如右图）。如此不断进行下去，直到满足迭代精度要求为止。3838首页上页下页末页结束2024/8/27 2024/8/27 周二周二 19:00 19:00程序设计技巧为了在每次计算插入点的坐标时能应用同一计算公式，新区间端点的坐标及函数值名称需换成原区间端点的坐标及函数值名称。在每个新区间上仍取 三点及其相应函数值 。这样当计算插入点（即抛物线极小点 ）位置时仍可以应用原来的计算公式。3939首页上页下页末页结束2024/8/27 2024/8/27 周二周二 19:00 19:00根据 与 的相对位置，与 的大小以及正向搜索（）或反向搜索（）的不同，具体换名有如下表所示的八种情况。（P56)4040首页上页下页末页结束2024/8/27 2024/8/27 周二周二 19:01 19:014141首页上页下页末页结束2024/8/27 2024/8/27 周二周二 19:01 19:01上表中的中的 就是在进行外推法时求初始搜索区间过程中所形成的最后步长，可正可负，分别对应于沿 正向或反向进行的一维搜索。分析上述八种换名情况可知，如果乘积 的符号相同，那么正向搜索和反向搜索将采取同样的换名方式，从而可将上述八种情况合并成四种情况，从而可将程序框图简化。4242首页上页下页末页结束2024/8/27 2024/8/27 周二周二 19:01 19:01二维插值法的程序框图（P57）4343首页上页下页末页结束2024/8/27 2024/8/27 周二周二 19:01 19:01q插值法和试探法的比较试探法中试验点位置是由某种给定的规律确定的，它不考虑函数值的分布。例如，黄金分割法是按等比例0.618缩短率确定的。插值法中，试验点位置是按函数值近似分布的极小点确定的。试探法仅仅利用了试验点函数值大小的比较，而插值法还要利用函数值本身或者其导数信息。4444首页上页下页末页结束2024/8/27 2024/8/27 周二周二 19:02 19:02试探法仅对试验点函数值的大小进行比较，而函数值本身的特性没有得到充分利用，这样即使对一些简单的函数，例如二次函数，也不得不象一般函数那样进行同样多的函数值计算。插值法是利用函数在已知试验点的值（或导数值）来确定新试验点的位置。当函数具有比较好的解析性质时（例如连续可微性），插值法比试探法效果更好。返回返回1 1、掌握一维搜索的概念和基本过程；、掌握一维搜索的概念和基本过程；2 2、掌握进退法和区间消去法原理；、掌握进退法和区间消去法原理；3 3、掌握黄金分割法的算法步骤及应用；了解切线法、掌握黄金分割法的算法步骤及应用；了解切线法的算法原理；的算法原理；4 4、理解并掌握抛物线法的算法步骤及应用。、理解并掌握抛物线法的算法步骤及应用。本章学习要求：本章学习要求：本本章章习习题题1用黄金分割法求一元函数用黄金分割法求一元函数的极小点，已知的极小点，已知初始搜索区间为初始搜索区间为，试给出经两次迭代后的搜索区，试给出经两次迭代后的搜索区间。间。2.何为一维搜索？简述优化方法中一维搜索的基本过程。何为一维搜索？简述优化方法中一维搜索的基本过程。