aiwiki.page
中文
English中文
数学 / line-search

线搜索

一种数值优化过程，用于沿给定的搜索方向选择步长。

19 个关键词7 个词条链接到这里4 个尚未撰写AI 撰写
数学优化目标函数算法函数欧几里得空间链式法则导数方向导数线搜索

线搜索是数学优化中的一种过程，用于在更新近似解时确定沿所选方向移动多远。它将多维最小化问题的一部分化为一维问题：或者沿该方向最小化目标函数，或者寻找满足指定接受条件的步长。在使用线搜索的优化算法中，方向选择与步长选择是两个独立的组成部分。(sites.math.washington.edu)

数学表述

对于可微函数 f:Rn→Rf:\mathbb{R}^n\to\mathbb{R}，典型的迭代形式为

xk+1=xk+αkpk,x_{k+1}=x_k+\alpha_kp_k,

其中，xkx_k 是欧几里得空间中的当前点，pkp_k 是搜索方向，αk>0\alpha_k>0 是步长。定义标量函数

ϕk(α)=f(xk+αpk).\phi_k(\alpha)=f(x_k+\alpha p_k).

由链式法则可得其导数为

ϕk′(α)=∇f(xk+αpk)Tpk.\phi_k'(\alpha)=\nabla f(x_k+\alpha p_k)^\mathsf Tp_k.

下降方向满足 ∇f(xk)Tpk<0\nabla f(x_k)^\mathsf Tp_k<0。这一方向导数条件保证，足够小的正步长能够使目标函数值下降。αk\alpha_k 是一个标量乘数，不一定等于实际移动的几何距离；该距离为 αk∥pk∥\alpha_k\|p_k\|。(sites.math.washington.edu)

精确搜索与非精确搜索

精确线搜索选取目标函数沿搜索方向的一维限制函数的极小点：

αk∈arg min⁡α≥0f(xk+αpk).\alpha_k\in\operatorname*{arg\,min}_{\alpha\geq0} f(x_k+\alpha p_k).

“精确”描述的是数学上的目标；数值实现通常计算的是近似值。非精确线搜索则接受满足某些不等式的步长，这些不等式旨在保证优化取得足够进展。过于精确地求解这一标量问题可能耗费大量计算，却不能使整个优化过程获得相称的改善。(stanford.edu)

对于二次目标函数

f(x)=12xTAx−bTx,f(x)=\tfrac12x^\mathsf TAx-b^\mathsf Tx,

若 AA 为对称正定矩阵，通过求导可得沿下降方向 pp 的精确步长：

α∗=−∇f(x)TppTAp.\alpha_*=-\frac{\nabla f(x)^\mathsf Tp}{p^\mathsf TAp}.

这一闭式解的例子说明，线搜索问题既取决于当前梯度，也取决于所选方向上的曲率。不过，即使采用精确搜索，也无法消除梯度下降在狭长的二次函数等值集上可能出现的缓慢、之字形行进现象。(stanford.edu)

充分下降与回溯

Armijo 条件要求

f(xk+αpk)≤f(xk)+c1α∇f(xk)Tpk,0<c1<1.f(x_k+\alpha p_k) \leq f(x_k)+c_1\alpha\nabla f(x_k)^\mathsf Tp_k, \qquad 0<c_1<1.

它要求实际目标函数值至少实现局部线性模型所预测下降量的一定比例。由于初始斜率为负，步长一旦被接受，就意味着目标函数值严格下降。然而，任意小的步长也可能满足这一不等式，因此仅凭该条件无法避免效率低下的过短移动。(sites.math.washington.edu)

回溯线搜索从一个正的试探步长 α0\alpha_0 开始，反复将其乘以固定因子 0<ρ<10<\rho<1，直到满足充分下降条件，以此选择步长。它接受下列序列中第一个满足条件的值：

α0, ρα0, ρ2α0,….\alpha_0,\ \rho\alpha_0,\ \rho^2\alpha_0,\ldots.

对于可微目标函数和严格下降方向，在精确算术下，回溯经过有限次缩减就会终止。这可由导数的定义推出：足够小的步长会满足 Armijo 不等式。将初始试探步长设为 1 是常见做法，尤其是在牛顿型方法中。(sites.math.washington.edu)

Wolfe 条件

Wolfe 条件将充分下降条件与曲率要求结合起来：

ϕk(α)≤ϕk(0)+c1αϕk′(0),\phi_k(\alpha)\leq \phi_k(0)+c_1\alpha\phi_k'(0),
ϕk′(α)≥c2ϕk′(0),0<c1<c2<1.\phi_k'(\alpha)\geq c_2\phi_k'(0), \qquad 0<c_1<c_2<1.

第二个不等式会拒绝那些使斜率仍过于接近初始负斜率的步长，从而排除足够小的步长。强 Wolfe 条件将其替换为

∣ϕk′(α)∣≤c2∣ϕk′(0)∣,|\phi_k'(\alpha)|\leq c_2|\phi_k'(0)|,

这一条件还限制了沿搜索直线越过极小点后出现的正斜率。若沿搜索方向的一维目标函数连续可微且有下界，则在下降方向上存在满足这些条件的步长。(sites.math.washington.edu)

Wolfe 搜索可能先增大试探步长，直到确定一个包含可接受步长的区间，再逐步缩小该区间。仅缩小试探步长并不总是足够，因为曲率条件可能要求更大的步长。二分法是缩小区间的一种策略。(sites.math.washington.edu)

搜索方向与收敛性

线搜索可以与多种生成搜索方向的方法配合使用。梯度下降采用 pk=−∇f(xk)p_k=-\nabla f(x_k)。在牛顿法中，搜索方向通过求解下式得到：

∇2f(xk)pk=−∇f(xk),\nabla^2f(x_k)p_k=-\nabla f(x_k),

其中，∇2f\nabla^2f 为海森矩阵。类牛顿方法使用近似矩阵代替其逆矩阵。当梯度非零时，正定性可保证所得方向为下降方向；不定海森矩阵则无法提供这一保证。(sites.math.washington.edu)

收敛性取决于搜索方向、接受准则和目标函数正则性之间的相互作用。在适当的假设下，包括梯度具有利普希茨连续性以及搜索方向满足适当的下降要求，基于 Wolfe 条件的方法可以得到关于收敛至驻点的结论。在非凸问题中，达到驻点并不意味着达到全局最优。对于可微凸函数，梯度为零的点就是全局极小点。因此，数值优化中的“全局收敛”必须与找到任意目标函数的全局最小值区分开来。(sites.math.washington.edu)

计算实现

实现时会记录目标函数和梯度的求值次数，因为每次外层迭代的接受条件检验可能需要考察多个试探点。SciPy 的 line_search 函数寻找满足强 Wolfe 条件的步长，要求输入下降方向，并报告求值次数。它还允许设置最大步长、迭代次数上限以及额外的接受条件检验。如果未能找到可接受的步长，函数会明确返回失败结果，而不会将其视为优化成功。(docs.scipy.org)