Part I · 第 6 章优化 · 6.5Part I · Ch. 6 Optimization · 6.5

线搜索与信赖域Line Search & Trust Regions

6.3 节里，学习率 $\eta$ 是你拍脑袋定的常数：大了发散，小了爬不动。这一节让算法自己决定每一步迈多大。有两种思路：线搜索先定方向，再沿着这个方向试探走多远；信赖域先定"在多大范围内我信得过局部模型"，再在这个范围里找最好的一步。两者背后是同一个问题：局部信息能信多远？ In Lesson 6.3 the learning rate $\eta$ was a constant you guessed: too big diverges, too small crawls. This lesson lets the algorithm decide for itself how far to step. There are two ideas: line search fixes the direction first, then probes how far to go along it; a trust region first fixes "how far I trust my local model" and then finds the best step inside that range. Behind both sits one question: how far can local information be trusted?

约 30 分钟~30 min 前置：6.3 梯度下降家族 · 3.5 Hessian · 2.4 泰勒展开Prereqs: 6.3 Gradient descent family · 3.5 Hessian · 2.4 Taylor expansion 5 个交互5 interactives

1为什么机器人需要它Why robots need this

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

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

Robot optimization often has to run reliably with nobody tuning it: an IK problem is solved every control cycle, a SLAM back end re-optimizes the whole pose graph whenever a batch of frames arrives, and an unattended calibration routine must converge on data it has never seen. If step sizes needed hand tuning, such systems would have collapsed in the real world long ago.

So the optimizers used in practice nearly all control the step: nonlinear least-squares libraries such as Ceres, g2o and GTSAM default to a trust region (Levenberg–Marquardt and dogleg, Lessons 6.6 and 6.9); quasi-Newton methods such as L-BFGS almost always come with a Wolfe line search; and the familiar trajectory-optimization trick "limit the joint change per step" is a trust region in disguise. This lesson explains how the two mechanisms work and why they work.

2直觉：两种"小心"Intuition: two ways to be careful

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

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

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

You descend a mountain in thick fog with only a small map of the ground underfoot (the gradient, perhaps the curvature as well). There are two safe ways to walk.

Line search: choose the direction, then measure the step. You commit to one downhill direction and ask "how far along it is sensible?" You try a long step and check whether it really lowered the altitude enough; if not, halve the step and try again (backtracking). The crux is defining "enough", which is the Armijo condition.

Trust region: choose the radius, then the direction. You tell the map "you are only reliable within $\Delta$ meters of me", then look inside the disk of radius $\Delta$ for the lowest point the map predicts. After stepping you check: what fraction of the predicted drop did the real altitude achieve? If roughly all of it, grow the radius next time; if far less, shrink the radius and undo the step. That ratio $\rho$ of "actual to predicted" is the heart of a trust region.

3动手玩：什么样的步长算"好"Play: what makes a step length "good"

左图是 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 条件。

On the left is the Rosenbrock terrain (the same shape as in Lesson 6.3, with the cost scaled by $\tfrac12$ so that Lesson 6.6 can write it as $\tfrac12\|\mathbf r\|^2$). Drag the amber start $\x_k$; from it a ray runs along the negative gradient. The right panel unrolls the cost along that ray as a one-variable function $\varphi(\alpha)=f(\x_k+\alpha\mathbf p)$ ($\mathbf p$ is a unit descent direction, so $\alpha$ is the distance travelled).

Two conditions pin down a "good" step: Armijo (sufficient decrease) demands that $\varphi(\alpha)$ lies below the amber dashed line (the line of slope $c_1\varphi'(0)$); the curvature condition demands $|\varphi'(\alpha)|\le c_2|\varphi'(0)|$, meaning "the slope has already flattened". Both together are the (strong) Wolfe conditions.

FIG 1Armijo 与 Wolfe 条件The Armijo and Wolfe conditions

右图底部的三行横条，自下而上：绿色是满足 Armijo 的 $\alpha$ 区间，蓝色是满足（强）曲率条件的区间，最上面一行是两者的交集，即 Wolfe 区间（左图射线上也用粗绿段标出）。拖动右图的黄点改变 $\alpha$；拖动左图的起点 $\x_k$ 则换一条射线。"回溯"从最右端 $\alpha_0$ 开始，每次减半，直到满足 Armijo：红叉是被拒绝的试探，绿勾是被接受的步长。工程中常用 $c_1=10^{-4}$，$c_2=0.9$（拟牛顿）；这里把 $c_1$ 默认设大，以便看清直线。 The three rows of bars at the bottom right, from the bottom up: green marks the $\alpha$-intervals satisfying Armijo, blue those satisfying the (strong) curvature condition, and the top row is their intersection, the Wolfe interval (also shown as a thick green segment on the ray on the left). Drag the amber dot on the right to change $\alpha$; drag the start $\x_k$ on the left to pick a new ray. "Backtrack" starts from the far-right $\alpha_0$ and halves until Armijo holds: red crosses are rejected trials, the green tick is the accepted step. In practice $c_1=10^{-4}$ and $c_2=0.9$ (quasi-Newton) are typical; $c_1$ defaults larger here so the line is visible.

试一试Try this

找一个满足 Armijo、却不满足曲率条件的 $\alpha$（提示：非常小的步长）。它为什么没有用？Find an $\alpha$ that satisfies Armijo but fails the curvature condition (hint: a very short step). Why is it useless?
把 $\alpha$ 放进 Wolfe 区间（右图三行横条中最上面、标着"Wolfe"的那一行，也是左图射线上的粗绿段）。再把 $c_2$ 调小到 0.15 左右（它必须大于 $c_1$）：区间变窄了还是变宽了？Place $\alpha$ inside the Wolfe interval (the top one of the three bar rows on the right, labelled "Wolfe"; also the thick green segment on the ray on the left). Now lower $c_2$ to about 0.15 (it must stay above $c_1$): does the interval get narrower or wider?
点"回溯"，数一数被拒绝了几次，再换一个起点重来。Press "Backtrack" and count how many trials are rejected; then pick another start and repeat.

核心洞见Key insight

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

Armijo prevents overshooting: with too long a step the function value does not fall, or falls less than the linear prediction. The curvature condition prevents over-caution: Armijo holds for any small enough $\alpha$, so by itself it would let the algorithm degrade into an ant's crawl. Backtracking uses Armijo only yet is not overly timid, because it starts large and shrinks, so the first accepted step is already reasonably long.

4三种步长策略赛跑：比的是"总计算量"Three step-size strategies, racing on total cost

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

Line search is not free: every backtracking trial costs one more evaluation of $f$. A fair comparison counts how many function and gradient evaluations were made in total, not how many iterations. The three methods below all use the steepest-descent direction $-\nabla f$: a fixed step; backtracking line search (Armijo, $c_1=10^{-4}$, halving, the initial trial being twice the previous step); and exact line search (minimize $\varphi$ along the ray precisely, by golden-section search). The horizontal axis counts evaluations.

FIG 2固定步长、回溯、精确线搜索Fixed step, backtracking, exact line search

f − f⋆ 对评估次数f − f⋆ vs. evaluations

三条路径从同一个起点出发（点击地图可更换起点），评估预算 3000 次。"评估"指一次 $f$ 或一次 $\nabla f$。固定步长的 $\eta$ 太大会发散（✗）；精确线搜索的相邻两步互相垂直，在弯曲的山谷里照样"之"字走。 All three paths start from the same point (click the map to move it) with a budget of 3000 evaluations; an "evaluation" is one $f$ or one $\nabla f$. A fixed step with $\eta$ too large diverges (✗); exact line search takes successive steps that are mutually perpendicular, and still zig-zags down the curved valley.

把固定步长 $\eta$ 调大到让它发散，而回溯线搜索安然无恙。Raise the fixed $\eta$ until it diverges while backtracking carries on unharmed.
让三个方法都用完 3000 次评估的预算，比较最终的 $f-f^\star$ 和每次迭代的平均评估次数（精确线搜索约 35 次，回溯约 3 次）：多花评估换来的"更准的步长"值得吗？Let all three use up the 3000-evaluation budget and compare the final $f-f^\star$ and the average evaluations per iteration (about 35 for exact, about 3 for backtracking): is the "more accurate step length" worth the extra evaluations?

5信赖域：模型、半径与 $\rho$Trust region: model, radius and $\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$ 的圆盘内最小化它：

A trust region replaces the true function with a quadratic model: $m(\mathbf p)=f+\mathbf g^\top\mathbf p+\tfrac12\mathbf p^\top B\mathbf p$, where $\mathbf g=\nabla f$ and $B$ is the Hessian (or an approximation). The model is the second-order Taylor expansion of $f$ at $\x_k$, increasingly wrong the farther you go from $\x_k$. So it is minimized only inside a disk of radius $\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$ 的变化：这就是算法调节半径时要读取的"信任度表"。

The figure shows the true contours of $f$ (cyan) and the model's contours (purple). Drag the base point $\x_k$ and the handle on the circle (or use the slider) to change $\Delta$: inside a small disk the two sets of contours nearly coincide and $\rho\approx1$; the larger the radius, the more model and truth disagree, and $\rho$ falls. The curve at the lower right plots $\rho$ against $\Delta$: the "trust gauge" the algorithm reads when adjusting its radius.

FIG 3信赖域子问题The trust-region subproblem

ρ 随半径 Δ 的变化ρ vs. radius Δ

黄色圆是信赖域；实心点是子问题的精确解 $\mathbf p_k$（颜色：$\rho>0.75$ 绿，$0.25$–$0.75$ 琥珀，$<0.25$ 红）；空心点是 Newton 步（仅当 $B\succ0$ 且在圆内）；小方块是 Cauchy 点（沿 $-\mathbf g$ 方向的模型最小点，被限制在圆内）。精确解由 $B$ 的特征分解与对乘子 $\lambda$ 的二分求得。"鞍"地形里 $B$ 不定，模型无下界，但圆盘让它仍有有限的最小值。 The amber circle is the trust region; the filled dot is the exact subproblem solution $\mathbf p_k$ (colored: $\rho>0.75$ green, $0.25$–$0.75$ amber, $<0.25$ red); the hollow dot is the Newton step (only when $B\succ0$ and inside the disk); the little square is the Cauchy point (the model minimizer along $-\mathbf g$, restricted to the disk). The exact solution is found by eigen-decomposing $B$ and bisecting on the multiplier $\lambda$. On the "saddle" terrain $B$ is indefinite and the model is unbounded below, yet the disk keeps its minimum finite.

在 Rosenbrock 上把 $\Delta$ 调到很小（$<0.08$）：$\rho$ 应接近 1，模型可信。On Rosenbrock shrink $\Delta$ below 0.08: $\rho$ should approach 1, the model is trustworthy.
把 $\Delta$ 加大，直到 $\rho<0.25$：模型的预测已经离谱，这一步应当被缩小或拒绝。Enlarge $\Delta$ until $\rho<0.25$: the model's prediction is off, so this step should be shrunk or rejected.
切换到"鞍"地形：Hessian 有负特征值，模型的等高线是双曲线，最小点被推到圆周上。Switch to "saddle": the Hessian has a negative eigenvalue, the model contours are hyperbolas, and the minimizer is pushed onto the circle.

6交锋：线搜索 Newton 与信赖域Showdown: line-search Newton versus trust region

现在把完整的算法跑起来。三个对手，都用精确的 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$）、以及起点恰好落在鞍点的稳定方向上的"鞍"。

Now run complete algorithms. Three contenders, all with the exact Hessian: GD + backtracking; Newton + backtracking (Newton direction $-H^{-1}\mathbf g$, falling back to $-\mathbf g$ if $H$ is not positive definite); and a trust region (exact subproblem; $\Delta\leftarrow\tfrac14\|\mathbf p\|$ when $\rho<0.25$, $\Delta\leftarrow2\Delta$ when $\rho>0.75$ and the step hits the boundary, and the step is accepted only if $\rho>0.1$). Three terrains: Rosenbrock, an ill-conditioned quadratic ($\kappa=100$), and the "saddle" with the start exactly on the saddle's stable direction.

FIG 4三种完整算法Three complete algorithms

f − f⋆ 对迭代次数f − f⋆ vs. iteration

圆圈是信赖域在每个迭代点的半径（绿：接受，红：拒绝，淡色）。点击地图可更换起点。表格里的"评估"是 $f$ 与 $\nabla f$ 的总次数（Hessian 的计算另算，Newton 与信赖域各用一次）。 Circles are the trust-region radius at each iterate (green accepted, red rejected, faint). Click the map to move the start. "Evals" in the table counts $f$ and $\nabla f$ evaluations (one Hessian per iteration for Newton and for the trust region, counted separately).

在 Rosenbrock 上让三者都跑完：GD + 回溯 400 步都到不了，Newton 与信赖域只要二十来步。Run all three to the end on Rosenbrock: GD + backtracking does not get there even in 400 steps, while Newton and the trust region need about twenty.
在"鞍"地形里：GD 和 Newton 都停在鞍点 $(0,0)$（梯度为零，但 $f-f^\star=0.25$），信赖域沿负曲率方向逃出，落入 $(0,\pm1)$。On "saddle": GD and Newton both stop at the saddle $(0,0)$ (zero gradient yet $f-f^\star=0.25$); the trust region escapes along the negative-curvature direction and lands in $(0,\pm1)$.

7再看数学The math

提示：悬停在带底色的符号上，FIG 3 中对应的元素（半径、模型、$\rho$ 曲线）会被强调。Tip: hover the highlighted symbols; the matching elements of FIG 3 (radius, model, $\rho$ curve) light up.

线搜索Line search

迭代为 $\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$：

The iteration is $\x_{k+1}=\x_k+\alpha_k\mathbf p_k$ with $\mathbf p_k$ a descent direction ($\nabla f(\x_k)^\top\mathbf p_k<0$). Let $\varphi(\alpha)=f(\x_k+\alpha\mathbf p_k)$, so $\varphi'(0)=\nabla f_k^\top\mathbf p_k<0$. For constants $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，所以回溯必定终止。

Together they are the (strong) Wolfe conditions. Typical values: $c_1=10^{-4}$, $c_2=0.9$ (Newton, quasi-Newton) or $0.1$ (conjugate gradient). If $\varphi$ is bounded below, a Wolfe interval always exists. Backtracking uses Armijo alone: start from $\alpha\leftarrow\alpha_0$ and while the condition fails set $\alpha\leftarrow\tau\alpha$ (usually $\tau=\tfrac12$). Since $\varphi(\alpha)=\varphi(0)+\alpha\varphi'(0)+o(\alpha)$ and $c_1<1$, a small enough $\alpha$ always satisfies Armijo, so backtracking terminates.

为什么这样就能收敛？著名的 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$。线搜索把"步长怎么选"这个难题，化成了一个有保证的小问题。

Why does this converge? Zoutendijk's theorem says: if every step satisfies the Wolfe conditions, $f$ is bounded below and its gradient is Lipschitz, then $\sum_k\cos^2\theta_k\,\|\nabla f_k\|^2<\infty$, where $\theta_k$ is the angle between $\mathbf p_k$ and $-\nabla f_k$. Hence as long as the direction is never "almost perpendicular" to the negative gradient ($\cos\theta_k\ge\delta>0$), $\|\nabla f_k\|\to0$. Line search turns the hard problem "how to choose the step" into a small problem with a guarantee.

信赖域Trust region

$$ \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 用的规则）：

The right-hand side is the necessary and sufficient condition for the exact solution (a special case of the KKT conditions of Lesson 6.7): if $B\succ0$ and the Newton step $-B^{-1}\mathbf g$ lies inside the disk, take it ($\lambda=0$); otherwise the solution sits on the circle with some $\lambda>0$ such that $(B+\lambda I)\mathbf p=-\mathbf g$ and $\|\mathbf p\|=\Delta$. The larger $\lambda$, the shorter the step and the closer it points along $-\mathbf g$: this is exactly the damping term of Levenberg–Marquardt in Lesson 6.6. Trust-region radius and LM damping are two representations of the same knob.

You need not solve exactly every time. The Cauchy point is the model minimizer along $-\mathbf g$ within the disk: $\mathbf p^C=-\tau\tfrac{\Delta}{\|\mathbf g\|}\mathbf g$, with $\tau=1$ (if $\mathbf g^\top B\mathbf g\le0$) or $\tau=\min\!\big(1,\tfrac{\|\mathbf g\|^3}{\Delta\,\mathbf g^\top B\mathbf g}\big)$. As long as each step achieves at least a fixed fraction of the Cauchy decrease, the algorithm has a global convergence guarantee; the dogleg method walks a broken line between the Cauchy point and the Newton point, cheap and close to exact.

The radius update is driven by $\rho_k$ (the rule used in 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} $$

	线搜索Line search	信赖域Trust region
先定什么decides first	方向 $\mathbf p_k$the direction $\mathbf p_k$	半径 $\Delta_k$the radius $\Delta_k$
再定什么then decides	沿方向的步长 $\alpha_k$the length $\alpha_k$ along it	圆盘内的最佳方向和长度the best direction and length inside the disk
Hessian 不正定indefinite Hessian	需要修正（或退回 $-\mathbf g$）needs a fix (or a fall-back to $-\mathbf g$)	天然可用，还能利用负曲率works naturally and can exploit negative curvature
每次失败的代价cost of a failed trial	多一次 $f$one more $f$ evaluation	多解一个子问题（$B$ 不变）one more subproblem (same $B$)

8机器人中的它：每个控制周期的"关节步长上限"In robotics: a per-cycle joint-step limit

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

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

A real-time IK controller must output new joint targets every cycle (say 10 ms). A joint-velocity limit (say 2 rad/s) means a joint can turn at most $\Delta_{\max}=0.02$ rad per cycle. Use that physical limit directly as the trust-region radius: each cycle solves one trust-region subproblem, so the step can never exceed what the joints can physically turn; it grows when the model is doing well and shrinks when it is not. The result is an inverse-kinematics solver with a built-in speed limit that does not diverge when the step is too big.

In the figure a two-link arm chases a target from its initial posture. On the right is joint space with the trust circles of each cycle; on the left the arm in the workspace. Drag the target, tune the maximum turn per cycle $\Delta_{\max}$ and watch how the "control cycles to converge" change. At the start the Hessian is indefinite, so a pure Newton step does not even apply; the trust region does not care.

FIG 5带关节步长上限的 IKIK with a joint-step limit

连杆长 1.0 与 0.8，目标可拖动。每个控制周期用有限差分得到的 Hessian 解一个信赖域子问题，半径上限为 $\Delta_{\max}$；$\rho$ 过小就缩小半径并拒绝该步。右图的圆是每个周期的半径，绿色表示该步被接受。读数里的"最大关节速度"按周期 10 ms 折算。 Link lengths 1.0 and 0.8; the target is draggable. Each control cycle solves a trust-region subproblem with a finite-difference Hessian, capping the radius at $\Delta_{\max}$; a too-small $\rho$ shrinks the radius and rejects the step. Circles on the right are each cycle's radius, green when the step was accepted. The "max joint speed" readout assumes a 10 ms cycle.

先用 $\Delta_{\max}\ge1$ rad 跑一遍，再用 $\Delta_{\max}\le0.1$ rad 跑一遍：后者慢多少个周期？它换来了什么？（每周期的关节位移不超过上限，运动平滑。）Run once with $\Delta_{\max}\ge1$ rad and once with $\Delta_{\max}\le0.1$ rad: how many more cycles does the latter take, and what did it buy? (Joint displacement per cycle never exceeds the limit: smooth motion.)

真实系统里In real systems

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

Nonlinear least-squares solvers (Ceres with its LEVENBERG_MARQUARDT and DOGLEG strategies, g2o, GTSAM) default to a trust region, and the initial and maximum radii are among the most commonly tuned parameters; in visual odometry with few features and degenerate geometry, a trust region keeps a single step from throwing the pose far away. Model predictive control (MPC) and sequential quadratic programming (SQP) for trajectory optimization also often bound the change of the variables per iteration (trust-region SQP). Whenever you see "change by at most this much per step", a trust region is almost certainly behind it.

9常见误区Common pitfalls

误区 1：线搜索方向可以随便选Pitfall 1: any direction will do for a line search

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

Armijo presupposes that $\mathbf p$ is a descent direction ($\mathbf g^\top\mathbf p<0$). If a quasi-Newton Hessian approximation loses positive definiteness, or the Newton direction points uphill in a non-convex region, backtracking shrinks to zero without ever finding an acceptable step. Always check $\mathbf g^\top\mathbf p<0$ in code, otherwise fall back to $-\mathbf g$ or fix the Hessian.

误区 2：把线搜索用在随机梯度上Pitfall 2: running a line search on stochastic gradients

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

Armijo compares the values of one function at two points. With minibatches (Lesson 6.4) the function itself changes with every batch, and the comparison loses its meaning. That is one reason deep learning uses learning-rate schedules rather than line searches. Line searches suit full-batch (or fixed-batch) problems.

误区 3：只看 $\rho$ 是否为正Pitfall 3: judging only by whether $\rho$ is positive

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

$\rho>0$ only says the function did go down, not that the model is reliable. Accepting a step with a tiny positive $\rho$ may cause trouble on the next one, so the acceptance threshold $\eta$ is usually about 0.1 and the radius is shrunk already when $\rho<0.25$. Conversely, $\rho\gg1$ (the real decrease far exceeds the prediction) means the model is too conservative, and also deserves a larger radius.

误区 4：信赖域"只是" Levenberg–MarquardtPitfall 4: a trust region is "just" Levenberg–Marquardt

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

LM controls the step indirectly by tuning the damping $\lambda$; a trust region sets the radius directly and derives $\lambda$ from it. They are equivalent, but setting a radius directly maps more easily onto physical quantities (maximum joint turn, maximum pose change) and makes failures easier to interpret (FIG 5).

10小练习Check yourself

1. 单靠 Armijo（充分下降）条件，为什么不能保证算法走得足够快？1. Why can the Armijo (sufficient-decrease) condition alone not guarantee decent progress?

Armijo 的右边随 $\alpha\to0$ 趋于 $\varphi(0)$，而 $\varphi$ 连续，所以足够小的 $\alpha$ 必然满足。要排除"过短的步"，需要曲率条件（Wolfe），或者像回溯那样从大步长往小缩，使第一个被接受的步长不会过短。过冲反而是 Armijo 能防止的事情。As $\alpha\to0$ the right-hand side tends to $\varphi(0)$ and $\varphi$ is continuous, so a small enough $\alpha$ always passes. Excluding "too short" steps needs the curvature (Wolfe) condition, or the backtracking approach of starting large and shrinking so the first accepted step is not too short. Overshoot is in fact what Armijo does prevent.

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$。最终接受的步长是多少？2. In a line search $\varphi(0)=10$, $\varphi'(0)=-4$, $c_1=0.25$, backtracking factor $\tfrac12$, initial $\alpha=1$. Given $\varphi(1)=9.5$, $\varphi(0.5)=9.4$, $\varphi(0.25)=9.6$, which step is finally accepted?

阈值 $\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 处就已经停下，得到的是第一个合格的、也就是较大的步长。）The threshold is $\varphi(0)+c_1\alpha\varphi'(0)=10-\alpha$. $\alpha=1$: threshold 9, $\varphi(1)=9.5>9$, rejected. $\alpha=0.5$: threshold 9.5, $\varphi(0.5)=9.4\le9.5$, accepted, and backtracking stops. ($\alpha=0.25$ is never even tried; it would also have passed, $9.6\le9.75$, but the search stopped at 0.5, returning the first acceptable, i.e. the larger, step.)

3. 信赖域的一步结果是 $\rho=-0.4$（$f$ 实际升高了）。算法应该怎么做？3. A trust-region step yields $\rho=-0.4$ ($f$ actually went up). What should the algorithm do?

$\rho<\eta$（$\eta\approx0.1$）时拒绝，$\rho<0.25$ 时缩小半径。保持半径不变重新求解会得到完全相同的子问题和相同的坏步（$B$、$\mathbf g$ 都没变），徒劳无功。缩小半径，模型在更小的圆盘里更准，下次的 $\rho$ 会好得多。Reject when $\rho<\eta$ ($\eta\approx0.1$) and shrink the radius when $\rho<0.25$. Re-solving with the same radius gives the identical subproblem and the identical bad step ($B$ and $\mathbf g$ have not changed). Shrinking makes the model more accurate on the smaller disk, so the next $\rho$ will be far better.

4. 在一个 Hessian 有负特征值的点，纯 Newton 步 $-H^{-1}\mathbf g$ 有什么问题？信赖域怎样处理？4. At a point where the Hessian has a negative eigenvalue, what is wrong with the pure Newton step $-H^{-1}\mathbf g$, and how does a trust region cope?

$H$ 有负特征值时二次模型沿该方向向下无界，其驻点 $-H^{-1}\mathbf g$ 是鞍点而非最小点，沿它走可能升高 $f$。信赖域子问题在紧致圆盘上必有最小值，且最优解满足 $B+\lambda I\succeq0$：所用的 $\lambda\ge-\lambda_{\min}(B)$ 自动给 Hessian 加上足够的"阻尼"，并让解沿负曲率方向走到圆周（FIG 3 的"鞍"、FIG 4 的鞍点逃逸）。With a negative eigenvalue the quadratic model is unbounded below along that direction; its stationary point $-H^{-1}\mathbf g$ is a saddle, not a minimum, and walking there can raise $f$. The trust-region subproblem on a compact disk always has a minimum whose solution satisfies $B+\lambda I\succeq0$: the $\lambda\ge-\lambda_{\min}(B)$ it uses automatically adds enough "damping" and sends the solution along the negative-curvature direction to the circle (the "saddle" of FIG 3, the saddle escape of FIG 4).

11延伸阅读Further reading

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) — 本节内容的标准教材，推导完整The standard text for this lesson, with full derivations
S. Boyd & L. Vandenberghe, Convex Optimization, Sec. 9.2 — 回溯线搜索与精确线搜索的收敛分析（可免费下载）Convergence analysis of backtracking and exact line search (free to download)
A. R. Conn, N. I. M. Gould & Ph. L. Toint, Trust-Region Methods, SIAM, 2000 — 信赖域方法的权威专著The authoritative monograph on trust-region methods
S. Agarwal, K. Mierle et al., Ceres Solver documentation — "Solving" 一章描述了机器人领域最常用的信赖域与线搜索策略及其参数The "Solving" chapter describes the trust-region and line-search strategies most used in robotics and their parameters

	线搜索Line search	信赖域Trust region
先定什么decides first	方向 \(\mathbf p_k\)the direction \(\mathbf p_k\)	半径 \(\Delta_k\)the radius \(\Delta_k\)
再定什么then decides	沿方向的步长 \(\alpha_k\)the length \(\alpha_k\) along it	圆盘内的最佳方向和长度the best direction and length inside the disk
Hessian 不正定indefinite Hessian	需要修正（或退回 \(-\mathbf g\)）needs a fix (or a fall-back to \(-\mathbf g\))	天然可用，还能利用负曲率works naturally and can exploit negative curvature
每次失败的代价cost of a failed trial	多一次 \(f\)one more \(f\) evaluation	多解一个子问题（\(B\) 不变）one more subproblem (same \(B\))