[科普中国]-一维搜索

一维搜索，又称一维优化，是指求解一维目标函数 f(X) 最优解的过程。

内容介绍求解一维目标函数 f(X) 最优解的过程，称为一维优化(一维搜索)，所使用的方法称为一维优化方法。

求某目标函数的最优值时，迭代过程每一步的格式都是从某一定点 出发，沿着某一使目标函数下降的规定方向 搜索，以找出此方向的极小点 。这一过程是各种最优化方法的一种基本过程。

一维搜索方法一般分两步进行：

首先确定一个包含函数极小点的初始区间，即确定函数的搜索区间，该区间必须是单峰区间；

然后采用缩小区间或插值逼近的方法得到最优步长，最终求出该搜索区间内的一维极小点。1

搜索区间根据函数的变化情况，可将区间分为单峰区间和多峰区间。所谓单峰区间，就是在该区间内的函数变化只有一个峰值，即函数的极小值。

目前在一维优化搜索中确定单峰区间常用的方法是进退试算法。进退试算法的基本思想为：

按照一定的规律给出若干试算点；

依次比较各试算点的函数值的大小；

直到找到相邻三点函数值按“高-低-高”变化的单峰区间为止。1

区间消去搜索区间确定之后，采用区间消去法逐步缩短搜索区间，找到极小点的数值近似解。

假定在搜索区间内[a，b] 任取两点 、 ，且 ， 。

1.若 ，新区间为 ；

2.若 ，新区间为 ；

3.若 ，新区间为 。

对于上述缩短后的新区间，可在其内再取一个新点，然后将此点和该区间内剩下的那一点进行函数值大小的比较，以再次按照上述方法，进一步缩短区间，这样不断进行下去，直到所保留的区间缩小到给定的误差范围内，而得到近似最优解。2

方法一维搜索的方法很多，常用的有试探法和插值法。试探法包括斐波那契法和黄金分割法等；插值法包括牛顿法等。

斐波那契法：在区间[a，b]内取两个不同点，并算出它们的函数值加以比较，就可以把搜索区间[a，b]缩小成 或 (缩小后的区间仍需包含极小点)。现在如果要继续缩小搜索区间 (或 )，就只需在上述区间内再取一点算出其函数值，并与 或 加以比较即可。

黄金分割法：适用于[a，b]区间上的任何单谷函数求极小值问题。对函数除要求“单峰”外不作其他要求，甚至可以不连续。适应面相当广。黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。

黄金分割法插入两点的计算公式如下：

这个方法可以看成是斐波那契法的近似，实现起来比较容易，效果也相当好，因而易于为人们所接受。

牛顿法：把非线性函数 在 处展开成泰勒级数，取其线性部分，作为非线性方程的近似方程如下：

可得 ，依此类推可得牛顿迭代公式： 。

在 处用一抛物线 代替曲线 ，相当于用一斜直线 代替曲线 。这样各个近似点是通过对作 切线求得与轴的交点找到的，所以有时牛顿法又称作切线法。牛顿法收敛速度快，但牛顿法要求初始点离极小点不太远，否则可能使极小化序列发散或收敛到非极小点。3

应用由于很多实际问题要求进一步精确化以及电子计算机的发展，使非线性规划在近几十年来得以快速发展。目前，它已成为运筹学的重要分支之一，并在最优设计、管理科学、系统控制等许多领域得到越来越广泛的应用。在利用迭代法求函数的极小点时，常常要用到一维搜索，即沿某一已知方向求目标函数的极小点。所以一维搜索在求解非线性函数极值点上发挥很大的作用。3

本词条内容贡献者为:

刘军 - 副研究员 - 中国科学院工程热物理研究所