回溯线搜索

回溯线搜索（backtracking line search）从一个候选正步长开始，反复按固定比例缩小，直到满足指定接受条件。下面讨论以 Armijo 充分下降为接受条件的版本；它是线搜索的具体程序，并不试图精确求出射线上的最小点。

三个候选步长的实际检验

对 $f(x)=x^2/2$，取当前点 $x=2$ 和方向 $p=-2$。初始目标为二，方向导数为 $f^{\prime }(2)p=-4$。令充分下降比例 $c=1/4$，接受条件为 $$f(2-2\alpha )=2(1-\alpha {)}^2\le 2-\alpha .$$ 展开并除以正数 $\alpha$，等价于 $0<\alpha \le 3/2$。若初始步长四、缩小比例 $\beta =1/2$，先检验四：新目标十八，高于接受上界负二；再检验二：新目标二，高于上界零；最后检验一：新目标零，低于上界一，于是接受。

四、二被拒绝，一被接受；纵坐标对应正文的实际目标值。

这个过程只需要当前点的一个方向导数，后续候选通常只评价目标。它接受的是几何序列 ${\alpha }_0,\beta {\alpha }_0,{\beta }^2{\alpha }_0,\dots$ 中遇到的第一个合格值，不是所有合格步长中的最优者。

有限终止的证明

设 $f$ 在当前点附近可微，$g=\mathrm{\nabla }f(x)$，方向满足 $g^{𝖳}p<0$，并取 $0<c<1,0<\beta <1$。可微性给出 $$f(x+\alpha p)=f(x)+\alpha g^{𝖳}p+o(\alpha ).$$ 令 $\delta =-(1-c)g^{𝖳}p/2>0$。足够小的正 $\alpha$ 满足 $|o(\alpha )|\le \delta \alpha$，因此 $$f(x+\alpha p)-f(x)\le \alpha (g^{𝖳}p+\delta )<c\alpha g^{𝖳}p.$$ 所有足够小的候选都能被接受，而几何序列趋于零，故精确算术下只需有限次回溯。这个论证无需凸性；目标若有定义域限制，还须先保证足够小的射线段在域内。

若沿相关线段的梯度为 $L$-Lipschitz，$L>0$，可用更明确的二次上界： $$f(x+\alpha p)\le f(x)+\alpha g^{𝖳}p+\frac{L}{2}{\alpha }^2\Vert p{\Vert }^2.$$ 于是任何 $0<\alpha \le T=2(1-c)(-g^{𝖳}p)/(L\Vert p{\Vert }^2)$ 都合格。若初始值大于T，到第 $j\ge \lceil \log (T/{\alpha }_0)/\log \beta \rceil$ 次缩小必已进入此范围。除初始值直接合格的情形外，最终步长还大于 $\beta T$：前一个拒绝值必大于T，否则按上界已应接受。

初值四、比例二分之一；到第三个候选一时进入不超过 3/2 的范围。

参数变式与失败边界

主例取 ${\alpha }_0=1$ 时立即接受，不必缩小。若改成更严格的 $c=3/4$，同一展开给出 $\alpha \le 1/2$，从四开始需要依次检查四、二、一、二分之一。变式终点为一，目标为二分之一；步长更保守不表示单步目标更低。

若错误地选 $p=+2$，则方向导数为正，充分下降检验对这个平方目标的任何正步长都失败：左侧为 $2+4\alpha +2{\alpha }^2$，右侧为 $2+\alpha$。有限终止证明的下降前提在此确实不可删。浮点下还可能发生步长缩到无法改变x、目标有噪声或返回非有限值；实现应明确失败状态，不能无限循环或把零步当成成功。

与正文一致的实现

函数只用标准库，输入当前点、方向、初步长及参数，返回接受步长、终点和全部检验记录，不改写输入。它专用于此平方目标，并设置最大检验次数；每次检查为常数成本，$J$ 次检查需 $O(J)$ 时间和返回历史空间。一般回溯会反复调用目标函数，复杂度应另乘评价成本。

Python 3

def backtrack_square(x=2.0, p=-2.0, initial=4.0, beta=.5, c=.25, budget=60):
    if initial <= 0 or not 0 < beta < 1 or not 0 < c < 1 or x*p >= 0:
        raise ValueError("invalid parameters or non-descent direction")
    a,trace = float(initial),[]
    for _ in range(budget):
        z = x+a*p
        f,limit = z*z/2,x*x/2+c*a*x*p
        accept = f <= limit
        trace.append((a,f,limit,accept))
        if accept:
            return a,z,trace
        a *= beta
        if x+a*p == x:
            break
    raise ArithmeticError("no accepted representable step within budget")

a,z,trace = backtrack_square()
for row in trace:
    print(row)
print("accepted",a,z)
assert backtrack_square(c=.75)[0] == .5

输出前两次为拒绝，第三次接受一；这只验证 Armijo，不保证同时满足弱或强 Wolfe 曲率条件。