线搜索

维基百科,自由的百科全书
跳到导航 跳到搜索

最优化问题中,线搜索 是一种寻找目标函数 局部最小值 的近似方法。它是最基础的迭代近似方法之一,另一种是置信域方法

线搜索近似首先找到一个使目标函数 下降的方向,然后计算 应该沿着这个方向移动的步长。下降方向可以通过多种方法计算,比如梯度下降法牛顿法拟牛顿法英语Quasi-Newton method。计算出的步长不一定是精确的。

应用举例[编辑]

以一个梯度法作为例子,其中第四步中使用到了线搜索。

  1. 令迭代计数器 ,为最小值做一个初始估计
  2. 重复以下步骤:
  3.     计算下降方向英语descent direction
  4.     选择 以在 上粗略地最小化
  5.     更新 , 以及
  6. 直到 小于容忍度。

在第四步的线搜索中算法可以通过解方程 精确地,或者只是通过寻找一个 的充分下降来粗略地最小化 。前者的一个例子是共轭梯度法。后者被称作不精确线搜索,有很多种实现方法,比如回溯线搜索英语backtracking line search或者是使用沃尔夫条件英语Wolfe conditions

与其它的最优化方法类似,线搜索也可以跟模拟退火结合以越过一些局部最小值

算法[编辑]

直接搜索方法[编辑]

这种方法里,必须先把最小值括在一个范围内,也就是说这个算法必须能够找到 使得要找的最小值在它们之间。接着通过计算这个区间内部的两个点 ,把区间分成几个子区间,抛弃掉外面两个点中与 中函数值更小的那个点不相邻的那一个。接下来的每一步中,只需要计算 额外的一个内部的点。在各种划分区间的方法中,[1] 黄金分割法是一种特别简单而高效的方法,它的划分比例在搜索进行中始终保持不变。

where

参阅[编辑]

参考[编辑]

  1. ^ Box, M. J.; Davies, D.; Swann, W. H. Non-Linear optimisation Techniques. Oliver & Boyd. 1969.