Trust Region Methodd

基本的信任区域算法是这样的：

1. Given an initial point $x$ and a trust region radius $\mu$ .

2. Solve

   $$\begin{array}{c} \arg \min _{\Delta x} \frac{1}{2}\|J(x) \Delta x+F(x)\|^{2} \\ \text { such that }\|D(x) \Delta x\|^{2} \leq \mu \\ L \leq x+\Delta x \leq U . \end{array}$$
3. $ho=\frac{|F(x+\Delta x)|^{2}-|F(x)|^{2}}{|J(x) \Delta x+F(x)|^{2}-|F(x)|^{2}}$

4. if $ho>\epsilon$ then $x=x+\Delta x$ .

5. if $ho>\eta_{1}$ then $\mu=2 \mu$

6. else if $ho<\eta_{2}$ then $\mu=0.5 * \mu$

7. Go to 2.

这里，$\mu$ 是信任区域半径，$D(x)$ 是某个矩阵，用于定义 $F(x)$ 域上的度量，$ho$ 衡量 $\Delta x$ 的质量，即线性模型预测非线性目标值下降的程度。我们的想法是根据线性化对非线性目标行为的近似预测程度来增大或减小信任区域的半径，这反映在 $ho$ 的值上。

信任区域算法的关键计算步骤是解决约束优化问题

$$\begin{aligned} \arg \min _{\Delta x} & \frac{1}{2}\|J(x) \Delta x+F(x)\|^{2} \\ \text { such that } & \|D(x) \Delta x\|^{2} \leq \mu \\ & L \leq x+\Delta x \leq U \end{aligned}$$

解决这个问题有多种不同的方法，每种方法都会产生不同的具体信任区域算法。目前，Ceres 实现了两种信任区域算法 Levenberg-Marquardt 算法和 Dogleg 算法，如果存在边界限制，每种算法都会使用线性搜索进行增强 。用户可以通过设置 Solver::Options::trust_region_strategy_type 来进行指定。

Levenberg-Marquardt

Levenberg-Marquardt 算法[Levenberg] [Marquardt] 是解决非线性最小二乘法问题的最流行算法。它也是第一个被开发出来的信任区域算法[Levenberg] [Marquardt] 。Ceres 实现了精确步长的[Madsen] 和非精确步长的 Levenberg-Marquardt 算法变体[WrightHolt] [NashSofer] 。

将上面的约束优化问题转换为无约束优化问题如下：

$$\arg \min _{\Delta x} \frac{1}{2}\|J(x) \Delta x+F(x)\|^{2}+\lambda\|D(x) \Delta x\|^{2}$$

其中，$\lambda$ 是与 $\mu$ 成反比关系的拉格朗日乘数。在 Ceres 中，我们求解

$$\arg \min _{\Delta x} \frac{1}{2}\|J(x) \Delta x+F(x)\|^{2}+\frac{1}{\mu}\|D(x) \Delta x\|^{2}$$

矩阵 $D(x)$ 是一个非负对角矩阵，通常是矩阵 $J(x)^{\top} J(x)$ 对角线的平方根。

在进一步讨论之前，我们先做一些符号上的简化。

我们将假设矩阵 $\frac{1}{\sqrt{\mu}} D$ 已被连接到矩阵 $J(x)$ 的底部，而相应的零向量已被添加到 $F(x)$ 的底部，即

$$J(x)=\left[\begin{array}{c} J(x) \\ \frac{1}{\sqrt{\mu}} D \end{array}\right], \quad F(x)=\left[\begin{array}{c} F(x) \\ 0 \end{array}\right] .$$

然后重写优化问题如下：

$$\min _{\Delta x} \frac{1}{2}\|J(x) \Delta x+F(x)\|^{2} .$$

后面只讨论 $J(x)$ 和 $F(x)$。在 Levenberg-Marquardt 算法的每次迭代中求解上述问题都是主要的计算成本。Ceres 提供了多种不同的方法来求解。主要有两类方法，因式分解法和迭代法。

因式分解方法的基础是利用 Cholesky 或 QR 因式分解计算 $\arg \min _{\Delta x} \frac{1}{2}\|J(x) \Delta x+F(x)\|^{2}+\frac{1}{\mu}\|D(x) \Delta x\|^{2}$ 的精确解，并由此产生了所谓的精确步骤 Levenberg-Marquardt 算法。但目前还不清楚精确解是否是Levenberg-Marquardt 算法每一步的必要条件。我们已经看到有证据表明情况可能并非如此，因为$\arg \min _{\Delta x} \frac{1}{2}\|J(x) \Delta x+F(x)\|^{2}+\frac{1}{\mu}\|D(x) \Delta x\|^{2}$本身就是最初优化问题的正则化版本。事实上，我们可以构建非线性优化算法，在这种算法中，线性化问题可以近似求解。这些算法被称为非精确牛顿法或截断牛顿法[NocedalWright]。

非精确牛顿法需要两个要素。首先，一种近似求解线性方程组的廉价方法。通常，[NocedalWright/] 会使用像共轭梯度法（Conjugate Gradients method）这样的线性迭代求解器。第二，迭代求解器的终止规则。典型的终止规则如下

$$\|H(x) \Delta x+g(x)\| \leq \eta_{k}\|g(x)\|$$

这里，$k$ 表示 Levenberg-Marquardt 的迭代次数，$0<\eta_{k}<1$ 称为强迫序列。WrightHolt 证明，基于上述策略的截断式 Levenberg-Marquardt 算法使用不精确的牛顿步，对于任意序列 $\eta_{k}\le \eta_0 <1$ 都收敛。收敛速度取决于强迫序列 $\eta_{k}$ 的选择。

Ceres 同时支持精确和非精确的分步求解策略。当用户选择基于因式分解的线性求解器时，将使用精确步长的 LevenbergMarquardt 算法。当用户选择迭代线性求解器时，则使用非精确步长的 Levenberg-Marquardt 算法。

我们将在 "线性求解器 "中详细介绍各种线性求解器。

Dogleg

Non-monotonic Steps

请注意，Trust Region Methods 中描述的基本信任区域算法是一种下降算法，它只接受严格降低目标函数值的点。放宽这一要求可以提高算法的长期效率，但代价是目标函数值的局部增加。这是因为以一种原则性的方式允许目标函数值不递减，该方法在保持其收敛特性的同时，不局限于进入局部极小值点。

设置 Solver::Options::use_nonmonotonic_steps 为 true 将开启由Conn, Gould & Toint in [Conn].设计的 non-monotonic trust region algorithm。即使目标函数值可能大于优化过程中遇到的最小值，最终返回给用户的参数也是所有迭代中成本最小的参数。所有信任区域策略都可以选择非单调步骤。