04 第四章 一维搜索方法.ppt

第1页：一维搜索方法概述

采用数学规划法求函数极值点的迭代计算中，第 k+1 次迭代需确定搜索方向与最佳步长因子。当搜索方向给定，求最佳步长就是求一元函数的极值，称为一维搜索，是优化搜索方法的基础。求解一元函数的极小点可用解析法。

第2页：解析法的不便与数值法思路

求 α 的极值即令 α 的导数为零。对于函数关系复杂的情形，解析法十分不便。

数值法的基本思路：确定搜索区间，在不断缩小区间，最终获得近似值。

第3页：确定搜索区间的外推法

第二节 搜索区间的确定和区间消去法原理

一、确定搜索区间的外推法：从初始点出发按给定步长试探，根据函数值的变化方向确定包含极小点的区间。

第4页：正向搜索的外推法

本页为正向搜索的外推法图示（图3-2），展示沿正向逐步加大步长直到函数值回升，从而确定搜索区间的过程。

第5页：反向搜索的外推法

本页为反向搜索的外推法图示（图3-3），展示首步函数值上升时改为反向试探、确定搜索区间的过程。

第6页：区间消去法原理

三、区间消去法原理：在搜索区间内插入一点并计算其函数值，通过比较函数值大小判断极小点所在子区间，消去不含极小点的部分。

第7页：

第8页：区间消去法的三种情形

为了避免多计算函数值，将第三种情况合并到前两种情况中。

第9页：一维搜索方法的分类

三、一维搜索方法的分类：每次缩短区间只需要在区间内插入一点并计算其函数值，插入点的位置可以由不同的方法来确定，就形成了不同的一维搜索方法。

第10页：黄金分割法的基本原理

第三节 一维搜索的试探法：最常用的一维搜索试探法是黄金分割法，又称 0.618 法。

• 要求插入点 a₁、a₂ 的位置相对于区间 [a,b] 两端点具有对称性。
• 除对称要求外，还要求在保留下来的区间再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。

第11页：黄金分割比例

所谓“黄金分割”是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段的比值，由此得到 0.618 的比例关系。

第12页：

第13页：插值法与牛顿法

第四节 一维搜索的插值方法：假定要在某一区间内寻找函数极小点的位置，虽然没有函数表达式，但能够给出若干试验点处的函数值，可以根据这些点处的函数值用插值的方法建立函数的近似表达式，进而求出函数的极小点，这种方法称作插值法，也称函数逼近法。

一、牛顿法（切线法）：一个连续可微的函数在极小点附近与一个二次函数很接近，因此在近似点附近用一个二次函数逼近。

第14页：牛顿法迭代公式

求二次函数的极小点作为极小点的新近似点，依次继续下去，可得牛顿法迭代公式。

第15页：牛顿法的几何解释

牛顿法的几何解释：在近似点处作函数的切线，以切线与横轴的交点作为新的近似点，逐步逼近极小点。

第16页：牛顿法的计算步骤

牛顿法的计算步骤：给定初始点、控制误差，并令 k=0。

1. 计算一阶导数
2. 求二阶导数
3. 若满足精度要求则求得近似解、停止计算，否则转第 4 步
4. 令 k=k+1，转第 1 步

第17页：牛顿法的优缺点与二次插值

• 优点：收敛速度快。
• 缺点：每一点都要计算二阶导数，工作量大；要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。

二、二次插值（抛物线法）：利用在单谷区间中的函数值，作出如下的二次插值多项式。

第18页：二次插值多项式的条件

二次插值多项式应满足三个条件：由极值的必要条件和三个插值条件联立方程组（1）、（2）、（3），即可求出系数。

第19页：二次插值公式推导（续）

本页承接上页，令中间变量化简后得到二次插值极小点的计算公式。

第20页：

第21页：

第22页：

第23页：