Part I · 第 6 章优化 · 6.5

线搜索与信赖域

6.3 节里，学习率 $\eta$ 是你拍脑袋定的常数：大了发散，小了爬不动。这一节让算法自己决定每一步迈多大。有两种思路：线搜索先定方向，再沿着这个方向试探走多远；信赖域先定"在多大范围内我信得过局部模型"，再在这个范围里找最好的一步。两者背后是同一个问题：局部信息能信多远？

约 30 分钟前置：6.3 梯度下降家族 · 3.5 Hessian · 2.4 泰勒展开 5 个交互

1为什么机器人需要它

机器人的优化往往要在没人调参的情况下可靠地运行：控制循环里每个周期要解一次逆运动学，SLAM 后端每来一批新帧要重新优化整张位姿图，无人值守的标定程序要对从没见过的数据收敛。如果步长要人手调，这些系统在真实世界里早就崩了。

所以工程上用的优化器几乎都带"步长控制"：Ceres、g2o、GTSAM 等非线性最小二乘库默认使用信赖域（Levenberg–Marquardt 与 dogleg，6.6、6.9 节）；L-BFGS 之类的拟牛顿法几乎总是配Wolfe 线搜索；轨迹优化里常见的"限制每一步关节变化量"，本质就是一个信赖域。这一节讲清楚这两种机制是怎样工作、为什么有效。

2直觉：两种"小心"

你在浓雾中下山，手里只有脚下一小片的地形图（梯度，还可能有曲率）。有两种稳妥的走法。

线搜索：先选方向，再量步长。你认定了一个下坡方向，然后问："沿这个方向走，走多远合适？"你先迈一大步，看看是不是真的降低了足够多的海拔；没有，就把步子减半再试（回溯）。关键是要定义"降低得足够多"，那就是 Armijo 条件。

信赖域：先选半径，再选方向。你对地形图说："这张图只在我周围 $\Delta$ 米内可信。"然后在半径 $\Delta$ 的圆盘内，找地形图预测的最低点。走完之后检查：实际降低的海拔，是地形图预测的几成？如果大致吻合，下次放大半径；如果差很多，缩小半径并撤销这一步。这个"实际/预测"的比值 $\rho$ 是信赖域的核心。

3动手玩：什么样的步长算"好"

左图是 Rosenbrock 地形（和 6.3 节同一形状，代价乘 $\tfrac12$，这样 6.6 节能写成 $\tfrac12\|\mathbf r\|^2$）。拖动黄色的起点 $\x_k$，从它出发沿负梯度方向有一条射线。右图把代价沿射线展开成一元函数 $\varphi(\alpha)=f(\x_k+\alpha\mathbf p)$（$\mathbf p$ 是单位长度的下降方向，所以 $\alpha$ 就是走的距离）。

两个条件把"好步长"夹出来：Armijo（充分下降）要求 $\varphi(\alpha)$ 在黄色虚线（斜率为 $c_1\varphi'(0)$ 的直线）之下；曲率条件要求此处的斜率 $|\varphi'(\alpha)|\le c_2|\varphi'(0)|$，也就是"坡已经变缓了"。两个条件都满足就是（强）Wolfe 条件。

FIG 1Armijo 与 Wolfe 条件

右图底部的三行横条，自下而上：绿色是满足 Armijo 的 $\alpha$ 区间，蓝色是满足（强）曲率条件的区间，最上面一行是两者的交集，即 Wolfe 区间（左图射线上也用粗绿段标出）。拖动右图的黄点改变 $\alpha$；拖动左图的起点 $\x_k$ 则换一条射线。"回溯"从最右端 $\alpha_0$ 开始，每次减半，直到满足 Armijo：红叉是被拒绝的试探，绿勾是被接受的步长。工程中常用 $c_1=10^{-4}$，$c_2=0.9$（拟牛顿）；这里把 $c_1$ 默认设大，以便看清直线。

试一试

找一个满足 Armijo、却不满足曲率条件的 $\alpha$（提示：非常小的步长）。它为什么没有用？
把 $\alpha$ 放进 Wolfe 区间（右图三行横条中最上面、标着"Wolfe"的那一行，也是左图射线上的粗绿段）。再把 $c_2$ 调小到 0.15 左右（它必须大于 $c_1$）：区间变窄了还是变宽了？
点"回溯"，数一数被拒绝了几次，再换一个起点重来。

核心洞见

Armijo 防止"走过头"：步子太大，函数值不降反升，或者降得不如线性预测。曲率条件防止"走得太保守"：只要 $\alpha$ 足够小，Armijo 总是满足，所以单靠 Armijo 会让算法退化成蚂蚁爬。回溯法只有 Armijo，却不会太保守，因为它是从大步长开始往小缩的，第一个被接受的步长已经够大了。

4三种步长策略赛跑：比的是"总计算量"

线搜索不是免费的：每次回溯试探要多算一次 $f$。公平的比较要看"总共评估了多少次函数和梯度"，而不是迭代了多少次。下面三个方法都用最速下降方向 $-\nabla f$：固定步长；回溯线搜索（Armijo，$c_1=10^{-4}$，每次减半，初始步长用上一次的两倍）；精确线搜索（每次沿射线把 $\varphi$ 精确最小化，用黄金分割）。横轴是评估次数。

FIG 2固定步长、回溯、精确线搜索

f − f⋆ 对评估次数

三条路径从同一个起点出发（点击地图可更换起点），评估预算 3000 次。"评估"指一次 $f$ 或一次 $\nabla f$。固定步长的 $\eta$ 太大会发散（✗）；精确线搜索的相邻两步互相垂直，在弯曲的山谷里照样"之"字走。

把固定步长 $\eta$ 调大到让它发散，而回溯线搜索安然无恙。
让三个方法都用完 3000 次评估的预算，比较最终的 $f-f^\star$ 和每次迭代的平均评估次数（精确线搜索约 35 次，回溯约 3 次）：多花评估换来的"更准的步长"值得吗？

5信赖域：模型、半径与 $\rho$

信赖域用一个二次模型代替真实函数：$m(\mathbf p)=f+\mathbf g^\top\mathbf p+\tfrac12\mathbf p^\top B\mathbf p$，其中 $\mathbf g=\nabla f$，$B$ 是 Hessian（或它的近似）。模型是 $f$ 在 $\x_k$ 处的二阶泰勒展开，离 $\x_k$ 越远越不准。所以只在半径 $\Delta$ 的圆盘内最小化它：

$$ \mathbf p_k=\arg\min_{\|\mathbf p\|\le\hl{radius}{\Delta}}\ \hl{model}{\cw{m(\mathbf p)}},\qquad \hl{rho}{\rho_k}=\frac{f(\x_k)-f(\x_k+\mathbf p_k)}{m(\mathbf 0)-m(\mathbf p_k)}=\frac{\text{actual reduction}}{\text{predicted reduction}} $$

下图画出 $f$ 的真实等高线（青色）和模型的等高线（紫色）。拖动起点 $\x_k$ 和圆周上的手柄（或滑块）改变 $\Delta$：小圆盘里两套等高线几乎重合，$\rho\approx1$；半径越大，模型与真实函数分歧越大，$\rho$ 下降。右下角的曲线是 $\rho$ 随 $\Delta$ 的变化：这就是算法调节半径时要读取的"信任度表"。

FIG 3信赖域子问题

ρ 随半径 Δ 的变化

黄色圆是信赖域；实心点是子问题的精确解 $\mathbf p_k$（颜色：$\rho>0.75$ 绿，$0.25$–$0.75$ 琥珀，$<0.25$ 红）；空心点是 Newton 步（仅当 $B\succ0$ 且在圆内）；小方块是 Cauchy 点（沿 $-\mathbf g$ 方向的模型最小点，被限制在圆内）。精确解由 $B$ 的特征分解与对乘子 $\lambda$ 的二分求得。"鞍"地形里 $B$ 不定，模型无下界，但圆盘让它仍有有限的最小值。

在 Rosenbrock 上把 $\Delta$ 调到很小（$<0.08$）：$\rho$ 应接近 1，模型可信。
把 $\Delta$ 加大，直到 $\rho<0.25$：模型的预测已经离谱，这一步应当被缩小或拒绝。
切换到"鞍"地形：Hessian 有负特征值，模型的等高线是双曲线，最小点被推到圆周上。

6交锋：线搜索 Newton 与信赖域

现在把完整的算法跑起来。三个对手，都用精确的 Hessian：GD + 回溯；Newton + 回溯（Newton 方向 $-H^{-1}\mathbf g$，若 $H$ 不正定则退回 $-\mathbf g$）；信赖域（精确子问题；$\rho<0.25$ 时 $\Delta\leftarrow\tfrac14\|\mathbf p\|$，$\rho>0.75$ 且步长顶到边界时 $\Delta\leftarrow2\Delta$，$\rho>0.1$ 才接受这一步）。三种地形：Rosenbrock、病态的二次函数（$\kappa=100$）、以及起点恰好落在鞍点的稳定方向上的"鞍"。

FIG 4三种完整算法

f − f⋆ 对迭代次数

圆圈是信赖域在每个迭代点的半径（绿：接受，红：拒绝，淡色）。点击地图可更换起点。表格里的"评估"是 $f$ 与 $\nabla f$ 的总次数（Hessian 的计算另算，Newton 与信赖域各用一次）。

在 Rosenbrock 上让三者都跑完：GD + 回溯 400 步都到不了，Newton 与信赖域只要二十来步。
在"鞍"地形里：GD 和 Newton 都停在鞍点 $(0,0)$（梯度为零，但 $f-f^\star=0.25$），信赖域沿负曲率方向逃出，落入 $(0,\pm1)$。

7再看数学

提示：悬停在带底色的符号上，FIG 3 中对应的元素（半径、模型、$\rho$ 曲线）会被强调。

线搜索

迭代为 $\x_{k+1}=\x_k+\alpha_k\mathbf p_k$，$\mathbf p_k$ 是下降方向（$\nabla f(\x_k)^\top\mathbf p_k<0$）。记 $\varphi(\alpha)=f(\x_k+\alpha\mathbf p_k)$，$\varphi'(0)=\nabla f_k^\top\mathbf p_k<0$。给定 $0<c_1<c_2<1$：

$$ \text{Armijo:}\ \ \varphi(\alpha)\le\varphi(0)+c_1\,\alpha\,\varphi'(0)\qquad\quad \text{curvature:}\ \ \varphi'(\alpha)\ge c_2\,\varphi'(0)\ \ \big(\text{strong: }|\varphi'(\alpha)|\le c_2|\varphi'(0)|\big) $$

两者合称（强）Wolfe 条件。典型取值 $c_1=10^{-4}$，$c_2=0.9$（Newton、拟牛顿）或 $0.1$（共轭梯度）。只要 $\varphi$ 有下界，Wolfe 区间必然非空。回溯法只用 Armijo：取 $\alpha\leftarrow\alpha_0$，当条件不满足时 $\alpha\leftarrow\tau\alpha$（常取 $\tau=\tfrac12$）。由于 $\varphi(\alpha)=\varphi(0)+\alpha\varphi'(0)+o(\alpha)$ 而 $c_1<1$，足够小的 $\alpha$ 一定满足 Armijo，所以回溯必定终止。

为什么这样就能收敛？著名的 Zoutendijk 定理说：若每一步都满足 Wolfe，且 $f$ 下有界、梯度 Lipschitz 连续，则 $\sum_k\cos^2\theta_k\,\|\nabla f_k\|^2<\infty$，其中 $\theta_k$ 是 $\mathbf p_k$ 与 $-\nabla f_k$ 的夹角。因此只要方向不与负梯度"几乎垂直"（$\cos\theta_k\ge\delta>0$），就有 $\|\nabla f_k\|\to0$。线搜索把"步长怎么选"这个难题，化成了一个有保证的小问题。

信赖域

$$ \min_{\mathbf p}\ \tfrac12\mathbf p^\top B\mathbf p+\mathbf g^\top\mathbf p\ \ \text{s.t.}\ \ \|\mathbf p\|\le\Delta \quad\Longleftrightarrow\quad (B+\hl{lam}{\lambda}I)\mathbf p=-\mathbf g,\ \ \lambda\ge0,\ \ \lambda(\Delta-\|\mathbf p\|)=0,\ \ B+\lambda I\succeq0 $$

右边是精确解的充要条件（6.7 节的 KKT 条件的一个特例）：若 $B\succ0$ 且 Newton 步 $-B^{-1}\mathbf g$ 在圆内，就取 Newton 步（$\lambda=0$）；否则解落在圆周上，对应一个 $\lambda>0$，使得 $(B+\lambda I)\mathbf p=-\mathbf g$ 且 $\|\mathbf p\|=\Delta$。$\lambda$ 越大，步越短、越接近 $-\mathbf g$ 方向：这正是 6.6 节 Levenberg–Marquardt 的阻尼项。信赖域半径和 LM 阻尼是同一个旋钮的两种表示。

不必每次都精确求解。Cauchy 点是模型沿 $-\mathbf g$ 方向在圆盘内的最小点：$\mathbf p^C=-\tau\tfrac{\Delta}{\|\mathbf g\|}\mathbf g$，其中 $\tau=1$（若 $\mathbf g^\top B\mathbf g\le0$）或 $\tau=\min\!\big(1,\tfrac{\|\mathbf g\|^3}{\Delta\,\mathbf g^\top B\mathbf g}\big)$。只要每步的模型下降不少于 Cauchy 点下降的一个固定比例，算法就有全局收敛保证；dogleg 法在 Cauchy 点与 Newton 点之间走一条折线，便宜又接近精确。

半径的更新由 $\rho_k$ 决定（FIG 4 用的规则）：

$$ \Delta_{k+1}=\begin{cases}\tfrac14\|\mathbf p_k\| & \rho_k<\tfrac14\\[2pt] \min(2\Delta_k,\ \Delta_{\max}) & \rho_k>\tfrac34\ \text{and}\ \|\mathbf p_k\|=\Delta_k\\[2pt] \Delta_k & \text{otherwise}\end{cases}\qquad \x_{k+1}=\begin{cases}\x_k+\mathbf p_k & \rho_k>\eta\ \ (\eta\approx0.1)\\ \x_k & \text{otherwise}\end{cases} $$

	线搜索	信赖域
先定什么	方向 $\mathbf p_k$	半径 $\Delta_k$
再定什么	沿方向的步长 $\alpha_k$	圆盘内的最佳方向和长度
Hessian 不正定	需要修正（或退回 $-\mathbf g$）	天然可用，还能利用负曲率
每次失败的代价	多一次 $f$	多解一个子问题（$B$ 不变）

8机器人中的它：每个控制周期的"关节步长上限"

实时 IK 控制器每个周期（比如 10 ms）要给出新的关节目标。关节速度上限（例如 2 rad/s）意味着每个周期关节最多能转 $\Delta_{\max}=0.02$ rad。把这个物理限制直接当作信赖域半径：每个周期解一个信赖域子问题，步长天然不会超过关节能转的角度；算得好就放大，算得差就缩小。你得到的是一个自带速度限制、又不会因为步子太大而发散的逆运动学求解器。

下图中，两连杆臂从初始姿态出发追踪目标。右侧是关节空间，圆是各周期的信赖域；左侧是工作空间里的手臂。拖动目标，调节每周期最大转角 $\Delta_{\max}$，看"收敛所需的控制周期数"怎样变化。起点处 Hessian 不定，纯 Newton 步根本不适用，信赖域则毫不在意。

FIG 5带关节步长上限的 IK

连杆长 1.0 与 0.8，目标可拖动。每个控制周期用有限差分得到的 Hessian 解一个信赖域子问题，半径上限为 $\Delta_{\max}$；$\rho$ 过小就缩小半径并拒绝该步。右图的圆是每个周期的半径，绿色表示该步被接受。读数里的"最大关节速度"按周期 10 ms 折算。

先用 $\Delta_{\max}\ge1$ rad 跑一遍，再用 $\Delta_{\max}\le0.1$ rad 跑一遍：后者慢多少个周期？它换来了什么？（每周期的关节位移不超过上限，运动平滑。）

真实系统里

非线性最小二乘求解器（Ceres 的 LEVENBERG_MARQUARDT 与 DOGLEG 策略、g2o、GTSAM）默认使用信赖域，初始半径和最大半径是最常调的参数之一；视觉里程计在特征很少、几何退化时，信赖域能防止一步把位姿"炸飞"。模型预测控制 (MPC) 和轨迹优化中的"序列二次规划 (SQP)"也经常给每次迭代的变量变化加上边界（trust-region SQP）。凡是看到"每步最多改变这么多"，背后几乎都是信赖域的想法。

9常见误区

误区 1：线搜索方向可以随便选

Armijo 的前提是 $\mathbf p$ 是下降方向（$\mathbf g^\top\mathbf p<0$）。拟牛顿的近似 Hessian 若失去正定性，或 Newton 方向在非凸区域指向上坡，回溯会一直缩到 0 也找不到合格步长。实现里必须检查 $\mathbf g^\top\mathbf p<0$，否则退回 $-\mathbf g$ 或修正 Hessian。

误区 2：把线搜索用在随机梯度上

Armijo 要求比较同一个函数在两点的值。小批量（6.4 节）里每次换一批数据，函数本身在变，条件的比较就失去意义。这是深度学习里通常用学习率日程而不是线搜索的原因之一。全批量（或固定批量）的问题才适合线搜索。

误区 3：只看 $\rho$ 是否为正

$\rho>0$ 只说明函数确实下降了，不说明模型靠谱。$\rho$ 很小但为正时接受这一步，下一步可能立刻出问题，所以接受门槛 $\eta$ 通常取 0.1 左右，并且在 $\rho<0.25$ 时就缩小半径。另一方面，$\rho\gg1$（实际下降远超预测）表示模型太保守，也值得扩大半径。

误区 4：信赖域"只是" Levenberg–Marquardt

LM 通过调节阻尼 $\lambda$ 间接控制步长；信赖域直接设定半径，再反推 $\lambda$。二者等价，但直接设半径更容易向物理量（关节最大转角、位姿最大变化）看齐，也更便于解释失败（FIG 5）。

10小练习

1. 单靠 Armijo（充分下降）条件，为什么不能保证算法走得足够快？

Armijo 的右边随 $\alpha\to0$ 趋于 $\varphi(0)$，而 $\varphi$ 连续，所以足够小的 $\alpha$ 必然满足。要排除"过短的步"，需要曲率条件（Wolfe），或者像回溯那样从大步长往小缩，使第一个被接受的步长不会过短。过冲反而是 Armijo 能防止的事情。

2. 某次线搜索中 $\varphi(0)=10$，$\varphi'(0)=-4$，取 $c_1=0.25$，回溯因子 $\tfrac12$，初始 $\alpha=1$。已知 $\varphi(1)=9.5$，$\varphi(0.5)=9.4$，$\varphi(0.25)=9.6$。最终接受的步长是多少？

阈值 $\varphi(0)+c_1\alpha\varphi'(0)=10-\alpha$。$\alpha=1$：阈值 9，$\varphi(1)=9.5>9$，拒绝。$\alpha=0.5$：阈值 9.5，$\varphi(0.5)=9.4\le9.5$，接受，回溯停止。（$\alpha=0.25$ 根本不会被试探；它其实也能通过，$9.6\le9.75$，但回溯在 0.5 处就已经停下，得到的是第一个合格的、也就是较大的步长。）

3. 信赖域的一步结果是 $\rho=-0.4$（$f$ 实际升高了）。算法应该怎么做？

$\rho<\eta$（$\eta\approx0.1$）时拒绝，$\rho<0.25$ 时缩小半径。保持半径不变重新求解会得到完全相同的子问题和相同的坏步（$B$、$\mathbf g$ 都没变），徒劳无功。缩小半径，模型在更小的圆盘里更准，下次的 $\rho$ 会好得多。

4. 在一个 Hessian 有负特征值的点，纯 Newton 步 $-H^{-1}\mathbf g$ 有什么问题？信赖域怎样处理？

$H$ 有负特征值时二次模型沿该方向向下无界，其驻点 $-H^{-1}\mathbf g$ 是鞍点而非最小点，沿它走可能升高 $f$。信赖域子问题在紧致圆盘上必有最小值，且最优解满足 $B+\lambda I\succeq0$：所用的 $\lambda\ge-\lambda_{\min}(B)$ 自动给 Hessian 加上足够的"阻尼"，并让解沿负曲率方向走到圆周（FIG 3 的"鞍"、FIG 4 的鞍点逃逸）。

11延伸阅读

J. Nocedal & S. Wright, Numerical Optimization, 2nd ed., Ch. 3 (line search: Armijo, Wolfe, backtracking, Zoutendijk) & Ch. 4 (trust region: Cauchy point, dogleg, exact solution) — 本节内容的标准教材，推导完整
S. Boyd & L. Vandenberghe, Convex Optimization, Sec. 9.2 — 回溯线搜索与精确线搜索的收敛分析（可免费下载）
A. R. Conn, N. I. M. Gould & Ph. L. Toint, Trust-Region Methods, SIAM, 2000 — 信赖域方法的权威专著
S. Agarwal, K. Mierle et al., Ceres Solver documentation — "Solving" 一章描述了机器人领域最常用的信赖域与线搜索策略及其参数