[科普中国]-直接搜索法

简介

在历史上，许多解决优化问题的方法都借助于熟悉的“经典分析技术”，即目标函数的泰勒级数展开。实际上，我们可以根据所用的展开项数来分类数值优化的方法。采用一、二阶导数的二阶泰勒多项式构建 f 的局部二次逼近。牛顿方法是一个二阶方法。采用一阶导数的一阶泰勒多项式构建 f 的局部线性逼近的最速下降方法是一个一阶方法。在这种分类中，“零阶方法”不需要求导信息和构造 f 的逼近。这些在工程优化界被称为零阶的方法就是直接搜索法。直接搜索法完全依赖于目标函数的值，但这并不能将直接搜索法同其他优化方法完全区分。另外无约束优化的直接搜索法仅仅依赖于通过可数集的函数值的相关阶的目标函数。直接搜索法可用新的迭代来减少目标1。

经典分类直接搜索法一般被分为三类，许多在应用文献中提到的新方法都是这三种方法的基本原理的改进版本。

模式搜索法模式搜索法（Pattern search）用一系列的点模式考虑目标函数的行为的试探位移来刻划。所有都依赖于有理格。试探位移由当前迭代邻近网格的点访问的系统策略组成。在戴维森的 ANL 59902延期的序言中，他描述了最基础的一种模式搜索算法，由于这么简单而没有归类。

单纯形法单纯形搜索法（Simplex search）由指导搜索的简单策略刻划。第一个单纯形方法是在 1962 年由 Spendley et al.3在论文中提出的。他们是由于早期的直接搜索法在任何地方都需要 2n 到 2n 个目标估值完成叠代改进的搜索的事实

而提出的。他们的结果是不需要 n+1个以上的目标函数的值来确定上升（或下降）方向。这意味着，只要n+1个 f(x)图像中的点就可确定一个平面，利用 n+1 个 f(x)值的有限差分估计▽f (x)。同时， n+1 个点确定一个单纯形。这引出了单纯形搜索的基本思想：在Rn 空间中构造一个非退化单纯形并用单纯形驱动搜索。单纯形不只是简化了空间的采样，它同时还有其它特性，如果用某个点的相对于其象对面中心的对称点代替该点后仍然是单纯形，见图1。这同样简化了操作，因为在搜索最优解时一次可反射一个顶点，简化了过程。

一旦初始单纯形构造好， Spendley et al 单纯形算法的单个移动是镜像的。这个移动首先在单纯形中确定“最差”顶点（例如：最小期望目标值的），然后通过向对面映射最差单纯形。如果映射后的点仍然是最差的，则选择“次差”顶点继续这个过程。（一个图 1 的快速回顾应该确保镜像点是否不比下一个最差点好，否则如果“最差”顶点又一次被选择镜像，就会被简单的反射回原来的地方，开始了一个循环）。最终的目标是取代“最好”顶点（比如，有最期望目标值的）或者确定出最优顶点是一个最优解的候选。直到那时，算法一直在通过相对面的中心翻转顶点来移动单纯形（而不是最好顶点）。

搜索方向集适应法最后一个经典方法的家族包括 Rosenbrock 和 Powell 的方法，称作搜索方向集适应法（Methods with adaptive sets of search directions）。这些算法试图利用在搜索过程中获得的函数曲率的信息构造方向来加速搜索。

Rosenbrock 方法的初始阶段用列向量做为搜索方向。它沿着这些方向搜索，每一轮循环一次，再转到产生成功步的新的叠代（一个不成功的步是引起目标期望值变小的）。这持续到每个搜索方向。一旦如此，当前阶段就结束了。在下一阶段，就不是像局部变量方法一样重复搜索同样集的正交向量了， Rosenbrock 旋转了方向集来获得在早期移动过程中确定的目标的信息。

鲍威尔搜索法描绘了一个不用计算导数寻找最小值的方法。我们定义它为求导无关算法，它不像直接搜索法，建模是搜索的核心。鲍威尔搜索法第一次使直接搜索法和求导无关方法有服务性的收敛分析。像鲍威尔搜索法中线性搜索使用的目标一样的显性建模的需要很清诉：它使得优化方法行为的严格陈述称为可能。可以期望目标本质为二次的一个解的邻域里算法一次快速收敛到最小值。

优势直接搜索法在实践中工作的很好，实际上，许多直接搜索法的基础启发性最近被分析家证明有和全局拟牛顿法技术类似的全局收敛性。直接搜索法的成功是因为他们中的许多，包括胡克和吉夫斯的直接搜索法4是依赖于经典分析技术，方法上外观不是显然形成他们的初始规格4。

拟牛顿法不能求解所有的非线性优化问题。直接搜索法能够解决许多其它精巧算法所解决不了的问题。直接搜索法的独特特性避免了许多其它方法的缺陷1。

直接搜索法即使对于要求很高的用户也是首选。理由很简单：直接搜索法能够直接、立即地被利用来求解许多非线性优化问题。对用户的要求是最低的，算法几乎不需要设定太多参数1。