线搜索

线搜索（line search）是在优化的当前点和搜索方向已经确定以后，沿该方向选择步长的过程。方向解决往哪里走，线搜索解决走多远。它常出现在梯度法、拟牛顿法和约束优化的全局化步骤中；沿一条射线取得最优，也只解决了当前一维子问题。

把多变量移动写成一维函数

设 $f:{ℝ}^n\to ℝ$ 可微，当前点为 $x$，非零方向为 $p$。令 $\varphi (\alpha )=f(x+\alpha p)$，其中 $\alpha \ge 0$，并要求所考虑的点属于定义域。导数为 ${\varphi }^{\prime }(\alpha )=\mathrm{\nabla }f(x+\alpha p{)}^{𝖳}p$。当 ${\varphi }^{\prime }(0)<0$ 时，p为下降方向，足够小的正步长使目标下降。

例如 $f(x)=(x-2{)}^2$、当前点零、方向一，得到 $\varphi (\alpha )=(\alpha -2{)}^2$。导数 $2\alpha -4$ 在二处为零，二阶导数为二，因此精确线搜索取 ${\alpha }^{\ast }=2$。把方向改成二，精确步长便变为一，最终移动仍是二；步长参数本身不是位移长度。

曲线在 α=2 最低，位于接受上界下方的正步长直到三。

一般正定二次函数 $f(x)=x^{𝖳}Qx/2-b^{𝖳}x$，$Q$ 实对称正定、$g=Qx-b$，沿方向展开为 $\varphi (\alpha )=f(x)+\alpha g^{𝖳}p+{\alpha }^2{p}^{𝖳}Qp/2$。若 $g^{𝖳}p<0$，正分母保证 $${\alpha }^{\ast }=-\frac{g^{𝖳}p}{p^{𝖳}Qp}>0.$$ 这证明了该特殊模型中的精确公式。一般函数的射线下确界未必达到，例如 $\varphi (\alpha )=e^{-\alpha }$ 始终下降，却没有有限最小步长。

足够下降与曲率条件

实际算法常只寻找满足条件的步长。Armijo 条件用 $0<c_1<1$ 要求 $$\varphi (\alpha )\le \varphi (0)+c_1\alpha {\varphi }^{\prime }(0).$$ 右侧要求至少取得线性预测下降的一部分。只取极小步长往往也能满足，却可能进展缓慢。弱 Wolfe 曲率条件再要求 ${\varphi }^{\prime }(\alpha )\ge c_2{\varphi }^{\prime }(0)$，其中 $c_1<c_2<1$，使斜率不再过于负。强 Wolfe 则要求 $|{\varphi }^{\prime }(\alpha )|\le c_2|{\varphi }^{\prime }(0)|$，进一步控制越过谷底后的正斜率。

在主例中选 $c_1=1/4,c_2=1/2$。Armijo 化为 $(\alpha -2{)}^2\le 4-\alpha$，即 $0<\alpha \le 3$；弱曲率化为 $2\alpha -4\ge -2$，即 $\alpha \ge 1$。故两者共同允许整个 $[1,3]$，无需每次精确找到二。强 Wolfe 在本例也允许同一区间。

曲率要求 α≥1，与Armijo合并后允许区间 [1,3]；粗段标出该区间。

曲率条件还解释了 BFGS 更新的正曲率。令 $s=\alpha p$、$y=\mathrm{\nabla }f(x+\alpha p)-\mathrm{\nabla }f(x)$，则 $$s^{𝖳}y=\alpha [{\varphi }^{\prime }(\alpha )-{\varphi }^{\prime }(0)]\ge \alpha (c_2-1){\varphi }^{\prime }(0)>0.$$ 因此“目标下降”与“取得合适曲率信息”是两种不同要求。回溯线搜索通常只检验 Armijo，不能自动当作完整 Wolfe 搜索。

变式与可运行的一维求解

变式从 $x=3$ 沿 $p=-2$ 搜索，目标为 $(1-2\alpha {)}^2$，精确步长为 $1/2$。位移为负一，终点仍是二。若在原点沿负方向搜索，则初始方向导数为正，不符合上述下降前提；缩小步长也无法使这个凸平方目标下降。

下例专用于平方目标，输入当前标量、下降方向和候选步长列表，返回精确步长及各候选的目标、Armijo/Wolfe判定，不改写输入。只用标准库，检查 $K$ 个候选需 $O(K)$ 时间和输出空间；一般问题的成本主要来自每个目标和梯度评价。

Python 3

def square_line_search(x=0.0, direction=1.0, candidates=(.25,1,2,3,4)):
    slope = 2*(x-2)*direction
    if slope >= 0:
        raise ValueError("a descent direction is required")
    exact = (2-x)/direction
    rows = []
    for a in candidates:
        if a <= 0:
            raise ValueError("positive trial step required")
        f = (x+a*direction-2)**2
        derivative = 2*(x+a*direction-2)*direction
        armijo = f <= (x-2)**2+.25*a*slope
        wolfe = armijo and derivative >= .5*slope
        rows.append((a,f,armijo,wolfe))
    return exact,rows

exact,rows = square_line_search()
print("exact",exact)
for row in rows:
    print(row)
assert square_line_search(3,-2)[0] == 0.5

预算或容限使搜索停止时，应报告其接受条件；“线搜索成功”不等于整个多变量问题已达到最优。