^Box, M. J.; Davies, D.; Swann, W. H. Non-Linear optimisation Techniques. Oliver & Boyd. 1969.
一月 13, 2023
线搜索, 最优化问题中, 是一种寻找目标函数, displaystyle, mathbb, mathbb, 的局部最小值, displaystyle, mathbf, 的近似方法, 它是最基础的迭代近似方法之一, 另一种是置信域方法, 近似首先找到一个使目标函数, displaystyle, 下降的方向, 然后计算, displaystyle, mathbf, 应该沿着这个方向移动的步长, 下降方向可以通过多种方法计算, 比如梯度下降法, 牛顿法和拟牛顿法, 英语, quasi, newton, method, 计. 最优化问题中 线搜索 是一种寻找目标函数 f R n R displaystyle f mathbb R n to mathbb R 的局部最小值 x displaystyle mathbf x 的近似方法 它是最基础的迭代近似方法之一 另一种是置信域方法 线搜索近似首先找到一个使目标函数 f displaystyle f 下降的方向 然后计算 x displaystyle mathbf x 应该沿着这个方向移动的步长 下降方向可以通过多种方法计算 比如梯度下降法 牛顿法和拟牛顿法 英语 Quasi Newton method 计算出的步长不一定是精确的 目录 1 应用举例 2 算法 2 1 直接搜索方法 3 参阅 4 参考应用举例 编辑以一个梯度法作为例子 其中第四步中使用到了线搜索 令迭代计数器 k 0 displaystyle displaystyle k 0 为最小值做一个初始估计 x 0 displaystyle mathbf x 0 重复以下步骤 计算下降方向 英语 descent direction p k displaystyle mathbf p k 选择 a k displaystyle displaystyle alpha k 以在 a R displaystyle alpha in mathbb R 上粗略地最小化 h a f x k a p k displaystyle h alpha f mathbf x k alpha mathbf p k 更新 x k 1 x k a k p k displaystyle mathbf x k 1 mathbf x k alpha k mathbf p k 以及 k k 1 displaystyle displaystyle k k 1 直到 f x k displaystyle nabla f mathbf x k 小于容忍度 在第四步的线搜索中算法可以通过解方程 h a k 0 displaystyle h alpha k 0 来精确地 或者只是通过寻找一个 h displaystyle h 的充分下降来粗略地最小化 h displaystyle h 前者的一个例子是共轭梯度法 后者被称作不精确线搜索 有很多种实现方法 比如回溯线搜索 英语 backtracking line search 或者是使用沃尔夫条件 英语 Wolfe conditions 与其它的最优化方法类似 线搜索也可以跟模拟退火结合以越过一些局部最小值 算法 编辑直接搜索方法 编辑 这种方法里 必须先把最小值括在一个范围内 也就是说这个算法必须能够找到 x 1 displaystyle x 1 和 x 2 displaystyle x 2 使得要找的最小值在它们之间 接着通过计算这个区间内部的两个点 x 3 displaystyle x 3 和 x 4 displaystyle x 4 把区间分成几个子区间 抛弃掉外面两个点中与 x 3 displaystyle x 3 和 x 4 displaystyle x 4 中函数值更小的那个点不相邻的那一个 接下来的每一步中 只需要计算 额外的一个内部的点 在各种划分区间的方法中 1 黄金分割法是一种特别简单而高效的方法 它的划分比例在搜索进行中始终保持不变 1 ϕ x 2 x 1 x 4 x 1 x 2 x 3 ϕ x 2 x 4 ϕ x 3 x 1 ϕ 2 x 4 x 3 displaystyle frac 1 phi x 2 x 1 x 4 x 1 x 2 x 3 phi x 2 x 4 phi x 3 x 1 phi 2 x 4 x 3 where ϕ 1 2 1 5 1 618 displaystyle phi frac 1 2 1 sqrt 5 approx 1 618 参阅 编辑割线法 牛顿法 黄金分割法参考 编辑 Box M J Davies D Swann W H Non Linear optimisation Techniques Oliver amp Boyd 1969 取自 https zh wikipedia org w index php title 线搜索 amp oldid 39667717, 维基百科,wiki,书籍,书籍,图书馆,