步长

线搜索方法：精确与非精确

小象实战讲义 · 人工智能数学基础

在上一节确定了下降方向后，如何确定沿该方向前进的“步长”成为关键。本节将深入探讨“线搜索”这一核心优化技术，从理论上完美的“精确线搜索”到实际中广泛应用的“非精确线搜索”，并重点介绍保证算法有效性的Wolfe条件和Goldstein条件。掌握这些条件，你将能理解并正确使用主流优化库中的线搜索策略，为构建高效、稳定的优化算法奠定基础。

💡 核心导读

• 精确线搜索的困境：理论上，我们希望每一步都找到使目标函数值最小的最优步长，但这通常等价于求解一个新的优化子问题，计算代价高昂且往往没有解析解。
• 非精确线搜索的妥协：为了实用，我们放弃寻找“最优”步长，转而寻找一个“足够好”的步长，它只需满足两个关键条件：函数值充分下降，且步长不会太小。
• Wolfe条件的精妙：这是最常用的非精确线搜索准则，它通过“充分下降条件”和“曲率条件”共同界定了一个可接受的步长区间，平衡了下降量与计算成本。
• 回溯法的效率：一种极其简单高效的实用方法，它只检查充分下降条件，并从一个大步长开始不断缩小，直到条件满足，在牛顿法等算法中表现优异。

从精确线搜索到非精确线搜索

在梯度下降等迭代优化算法中，每一步的更新公式为： $$\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k$$ 其中 $\mathbf{p}_k$ 是第 $k$ 步的搜索方向（如负梯度方向 $-\nabla f(\mathbf{x}_k)$），$\alpha_k > 0$ 是待确定的步长。

一个最直接的想法是，在给定点 $\mathbf{x}_k$ 和方向 $\mathbf{p}$kpk​ 后，选择能使目标函数 $f$ 在该方向上下降最多的步长。这引出了精确线搜索的定义：寻找 $\alpha_k$，使得 $$\alpha_k = \arg\min$${\alpha > 0} \phi(\alpha) \quad \text{其中} \quad \phi(\alpha) = f(\mathbf{x}_k + \alpha \mathbf{p}_k) 即最小化一元函数 $\phi(\alpha)$。

然而，精确线搜索存在一个根本性的矛盾：求解一个优化问题的子问题，本身又是一个优化问题。对于大多数复杂的 $f$，$\phi(\alpha)$ 的最小值点没有解析解（公式解），必须通过数值迭代求解，这将耗费巨大的计算量，使得每一步的更新成本变得不可接受。

因此，在实践中我们转向非精确线搜索。我们不再要求 $\alpha_k$ 是 $\phi(\alpha)$ 的全局最小点，而是只要求它满足一些较弱的条件，保证算法整体能有效收敛即可。这些条件需要在“函数值下降足够多”和“避免步长过小”之间取得平衡。

Wolfe条件：理论与保障

Wolfe条件是一组被广泛采用的非精确线搜索准则，它包含两个部分。

充分下降条件 (Armijo Condition)

充分下降条件要求，新的函数值必须比当前函数值有“充分”的下降。其数学表述为： $$f(\mathbf{x}_k + \alpha \mathbf{p}_k) \le f(\mathbf{x}_k) + c_1 \alpha \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k$$ 其中 $c_1 \in (0, 1)$ 是一个常数，通常取一个很小的值，如 $10^{-4}$。

我们来理解这个条件：

• $\nabla f(\mathbf{x}_k)^\top \mathbf{p}_k$ 是方向导数。当 $\mathbf{p}_k$ 是下降方向时（如负梯度），该值为负。
• 不等式的右边定义了一个关于 $\alpha$ 的线性函数 $L(\alpha) = f(\mathbf{x}_k) + c_1 \alpha \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k$，其斜率为负。
• 条件要求 $\phi(\alpha) \le L(\alpha)$。由于 $L(0) = \phi(0)$，这意味着从 $\alpha=0$ 出发，$\phi(\alpha)$ 的曲线必须位于直线 $L(\alpha)$ 下方。

这个条件的几何意义是：我们接受那些函数值下降“比一条很平缓的负斜率直线所预测的还要多”的步长。因为 $c_1$ 很小，直线 $L(\alpha)$ 很平缓，所以只要函数值有轻微下降，就很可能满足该条件。特别地，当 $\alpha$ 非常接近于0时，由于 $\phi’ (0) = \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k < 0$，总能满足充分下降条件。这带来了一个问题：步长可能会被选得任意小。

曲率条件 (Curvature Condition)

为了防止步长过小，我们需要曲率条件： $$\nabla f(\mathbf{x}_k + \alpha \mathbf{p}_k)^\top \mathbf{p}_k \ge c_2 \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k$$ 其中 $c_2 \in (c_1, 1)$ 是另一个常数。对于牛顿法或拟牛顿法，$c_2$ 常取0.9；对于非线性共轭梯度法，可能取0.1。

这个条件意味着：

• 不等式左边是 $\phi’(\alpha)$。
• 不等式右边是 $c_2 \phi’(0)$，且 $\phi’(0) < 0$。
• 条件要求 $\phi’(\alpha) \ge c_2 \phi’(0)$。由于 $c_2 \phi’(0)$ 是一个负数（比 $\phi’(0)$ 更接近0），这等价于要求 $\phi$ 在 $\alpha$ 处的斜率不能太陡（负得太多），即曲线不能下降得太“急”。

结合图像看，曲率条件排除了 $\alpha$ 非常小的区域（那里曲线斜率很负，下降很快），只接受那些曲线变得相对平缓（斜率接近零甚至为正）的区域所对应的 $\alpha$。

Wolfe条件的意义与存在性

将充分下降条件和曲率条件结合起来，就得到了Wolfe条件： $$\begin{cases} f(\mathbf{x}_k + \alpha \mathbf{p}_k) \le f(\mathbf{x}_k) + c_1 \alpha \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k & \text{(充分下降)} \[6pt] \nabla f(\mathbf{x}_k + \alpha \mathbf{p}_k)^\top \mathbf{p}_k \ge c_2 \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k & \text{(曲率)} \end{cases}$$ 其中 $0 < c_1 < c_2 < 1$。

Wolfe条件定义了一个可接受的步长区间。这个区间是充分下降条件定义的区域（$\phi(\alpha)$ 在 $L(\alpha)$ 下方）与曲率条件定义的区域（$\phi’(\alpha)$ 在水平线 $c_2\phi’(0)$ 上方）的交集。通常，这个交集包含两个不连续的区间：一个在 $\phi$ 的极小值点附近（曲线平缓），另一个可能在函数值上升段（但满足充分下降）。

一个重要的理论保证是：对于光滑（连续可微）且下方有界的函数 $f$，以及满足 $\nabla f(\mathbf{x}_k)^\top \mathbf{p}_k < 0$ 的下降方向 $\mathbf{p}_k$，总存在满足Wolfe条件的步长 $\alpha > 0$。这使得基于Wolfe条件的线搜索算法总是可行的。

下面的代码演示了如何为一个简单函数在给定点沿负梯度方向寻找满足Wolfe条件的步长区间。

import numpy as np

def f(x):
    """目标函数：Rosenbrock函数（简化版，便于可视化）"""
    return (1 - x[0])**2 + 100 * (x[1] - x[0]**2)**2

def grad_f(x):
    """目标函数的梯度"""
    dfdx0 = -2*(1 - x[0]) - 400*x[0]*(x[1] - x[0]**2)
    dfdx1 = 200*(x[1] - x[0]**2)
    return np.array([dfdx0, dfdx1])

def phi(alpha, xk, pk):
    """线搜索函数 phi(alpha) = f(xk + alpha * pk)"""
    return f(xk + alpha * pk)

def phi_prime(alpha, xk, pk):
    """线搜索函数的导数 phi'(alpha) = grad_f(xk+alpha*pk)^T pk"""
    x_new = xk + alpha * pk
    return grad_f(x_new) @ pk  # 点积

def find_wolfe_interval(xk, pk, c1=1e-4, c2=0.9, alpha_max=2.0, n_grid=1000):
    """
    通过网格搜索，可视化地找到满足Wolfe条件的步长区间。
    注意：实际算法使用更高效的二分或插值法，此处仅为演示。
    """
    alphas = np.linspace(0, alpha_max, n_grid)
    phi_vals = np.array([phi(a, xk, pk) for a in alphas])
    phi_prime_vals = np.array([phi_prime(a, xk, pk) for a in alphas])
    
    phi0 = phi(0, xk, pk)
    phi_prime0 = phi_prime(0, xk, pk)
    
    # 充分下降条件的上界线 L(alpha)
    L_vals = phi0 + c1 * alphas * phi_prime0
    
    # 曲率条件的下界线
    curvature_line = c2 * phi_prime0
    
    # 判断条件
    armijo_ok = phi_vals <= L_vals
    curvature_ok = phi_prime_vals >= curvature_line
    wolfe_ok = armijo_ok & curvature_ok
    
    # 找出满足条件的连续区间
    intervals = []
    in_interval = False
    start = 0
    for i, ok in enumerate(wolfe_ok):
        if ok and not in_interval:
            start = alphas[i]
            in_interval = True
        elif not ok and in_interval:
            intervals.append((start, alphas[i-1]))
            in_interval = False
    if in_interval:
        intervals.append((start, alphas[-1]))
    
    return alphas, phi_vals, L_vals, phi_prime_vals, curvature_line, intervals

# 测试：在点(0, 0)沿负梯度方向搜索
xk = np.array([0.0, 0.0])
pk = -grad_f(xk)  # 负梯度方向

alphas, phi_vals, L_vals, phi_prime_vals, curv_line, intervals = find_wolfe_interval(xk, pk)

print(f"当前点 xk = {xk}")
print(f"搜索方向 pk (负梯度) = {pk}")
print(f"phi'(0) = {phi_prime(0, xk, pk):.6f}")
print(f"\n满足Wolfe条件 (c1=1e-4, c2=0.9) 的步长区间：")
for i, (a_start, a_end) in enumerate(intervals):
    print(f"  区间 {i+1}: [{a_start:.6f}, {a_end:.6f}]")
if not intervals:
    print("  未找到满足条件的区间（可能alpha_max设置过小）。")

其他非精确线搜索条件

Goldstein条件

Goldstein条件是另一个常用的非精确线搜索准则，它试图用一个更简单的形式同时避免步长过大和过小： $$f(\mathbf{x}_k) + (1-c)\alpha \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k \le f(\mathbf{x}_k + \alpha \mathbf{p}_k) \le f(\mathbf{x}_k) + c\alpha \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k$$ 其中 $c \in (0, 0.5)$。

这个条件要求 $\phi(\alpha)$ 的值被夹在两条斜率不同的直线之间。它的优点是计算简单，只需要函数值，不需要计算新点的梯度。但其缺点是，对于某些函数，可接受的区间可能非常窄，甚至“完美地”错过了函数真正的谷底（最优点附近），导致推荐的步长不够理想。因此，它不如Wolfe条件应用广泛，但在一些对精度要求不高的简单场景中仍可使用。

回溯法 (Backtracking Line Search)

回溯法是一种极其简单且高效实用的方法。它只使用充分下降条件，并采用一种试探策略来避免步长过小。

算法步骤：

1. 选择参数 $c \in (0, 1)$（控制充分下降程度），$\rho \in (0, 1)$（收缩因子），以及一个初始试探步长 $\alpha_0$（例如，在牛顿法中常取1）。
2. 当 不满足 充分下降条件 $f(\mathbf{x}_k + \alpha \mathbf{p}_k) > f(\mathbf{x}_k) + c \alpha \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k$ 时：
   • 令 $\alpha \leftarrow \rho \alpha$ （收缩步长）。
3. 返回最终的 $\alpha$。

回溯法从一个大步长开始，不断收缩，直到满足充分下降条件。因为它从一个（希望是合理的）大步长开始搜索，所以最终得到的步长通常不会太小。这种方法牺牲了Wolfe条件提供的理论严密性，但换来了极高的计算效率和实现的简便性，在牛顿法、拟牛顿法等算法中经常被采用，且效果良好。

def backtracking_line_search(xk, pk, alpha_init=1.0, c=1e-4, rho=0.5, max_iters=100):
    """
    回溯线搜索实现。
    """
    alpha = alpha_init
    fk = f(xk)
    grad_fk_dot_pk = grad_f(xk) @ pk
    
    for i in range(max_iters):
        x_new = xk + alpha * pk
        f_new = f(x_new)
        armijo_condition = f_new <= fk + c * alpha * grad_fk_dot_pk
        
        if armijo_condition:
            print(f"回溯法在第 {i+1} 次迭代后接受步长 alpha = {alpha:.6f}")
            print(f"  新函数值: {f_new:.6f}, 旧函数值: {fk:.6f}")
            return alpha
        else:
            alpha *= rho
    
    print(f"回溯法在 {max_iters} 次迭代后未找到可接受步长，返回最后尝试的 alpha = {alpha:.6f}")
    return alpha

# 使用回溯法在相同点搜索步长
alpha_bt = backtracking_line_search(xk, pk, alpha_init=1.0)
print(f"回溯法得到的步长: {alpha_bt:.6f}")

📝 动手练一练

1. 条件理解：对于同一个点 $\mathbf{x}_k$ 和下降方向 $\mathbf{p}_k$，假设我们固定 $c_1=10^{-4}$。如果将 Wolfe 条件中的 $c_2$ 从 0.1 增大到 0.9，你认为可接受的步长区间通常会变大还是变小？为什么？

2. 回溯法实验：修改上面回溯法代码中的参数 rho（收缩因子）。分别尝试 rho=0.1、rho=0.5 和 rho=0.9，观察并解释：

   • 找到可接受步长所需的平均迭代次数有何变化？
   • 最终得到的步长 $\alpha$ 大小有何变化？
   • 哪个 rho 值在“搜索效率”和“获得较大步长”之间可能取得更好的平衡？

参考答案：

1. 可接受的步长区间通常会变小。因为曲率条件 $\phi’(\alpha) \ge c_2 \phi’(0)$ 要求新点的方向导数不能太负。$c_2$ 越大，$c_2\phi’(0)$ 越接近0（即要求更平缓），条件越严格，满足条件的 $\alpha$ 就越少，区间也就越窄。当 $c_2$ 接近1时，几乎要求 $\phi’(\alpha) \approx 0$，即接近驻点，区间会收缩到极小值点附近。
2. • 迭代次数：rho 越小（如0.1），步长收缩得越快，更容易快速满足充分下降条件，因此迭代次数通常更少。rho 越大（如0.9），每次收缩幅度小，可能需要更多次迭代才能满足条件。
   • 步长大小：rho 越小，步长收缩剧烈，最终接受的步长可能更小。rho 越大，步长收缩平缓，最终可能保留一个相对较大的步长。
   • 平衡点：rho=0.5 是一个常用的折中选择。它既不会像0.1那样因收缩过快而可能得到一个过小的保守步长，也不会像0.9那样因收缩过慢而进行太多无效的函数值计算。在实际的优化库（如 SciPy）中，rho 常取在 0.1 到 0.8 之间，0.5是一个稳健的默认值。

本章小结

本节深入探讨了最优化算法中决定步长的核心方法——线搜索。

• 精确线搜索寻求理论最优步长，但计算成本高，通常不实用。
• 非精确线搜索寻求“足够好”的步长，是实践中的主流。
• Wolfe条件是最重要的非精确线搜索准则，它通过充分下降条件保证函数值有效降低，通过曲率条件防止步长过小，两者共同确保算法的收敛性。
• Goldstein条件是另一种更简单的准则，但可能不够精确。
• 回溯法是一种高效实用的简化策略，只使用充分下降条件，并通过从大步长开始收缩来规避步长过小的问题，在牛顿法等算法中广泛应用。

行动清单

1. 理解条件内涵：重绘图解，在脑海中明确Wolfe条件中两条线（$L(\alpha)$ 和 $c_2\phi’(0)$）如何共同“切割”出可接受的步长区间。
2. 代码验证：运行本节提供的代码，修改目标函数 f、起始点 xk 和参数（c1, c2, rho），直观观察不同条件下可接受区间的变化以及回溯法的行为。
3. 库函数探查：在后续学习或使用 scipy.optimize.minimize 等优化库时，留意其 method 参数中不同算法（如 'BFGS', 'CG'）对应的线搜索选项，尝试指定 options={'gtol': 1e-5} 等参数，理解它们与本节理论条件的联系。

— 小象教研组