Introduction

要有效使用 Ceres 求解器，需要熟悉非线性最小二乘法求解器的基本组件，因此在介绍如何配置和使用求解器之前，我们先简要了解一下 Ceres 求解器中的一些核心优化算法是如何工作的。

x∈Rnx \in \mathbb{R}^{n} 中）是一个 nn 维变量向量，F(x)=[f1(x),…,fm(x)]⊤F(x)=\left[f_{1}(x), \ldots, f_{m}(x)\right]^{\top} 是 xx 的一个 mm 维函数，fi(x)f_i(x) 是一个标量函数，映射为 Rn→R\mathbb{R}^{n}\to \mathbb{R}。 我们想解决优化问题如下

arg⁡min⁡x12∥F(x)∥2L≤x≤U\begin{array}{r} \arg \min _{x} \frac{1}{2}\|F(x)\|^{2} \\ L \leq x \leq U \end{array}

其中，LL 和 UU 是参数向量 xx 的矢量下限和上限。由于对一般的 F(x)F(x) 进行有效的全局最小化是一个难以解决的问题，所以我们只能寻求局部最小值。

F(x)F(x) 的 Jacobian J(x)J(x) 是一个 m×nm\times n 的矩阵，mm 表示残差的维度，nn 为待优化变量的维度，Jij(x)J_{i j}(x) 表示第 ii 个残差分量对第 jj 个变量的导数，fi(x)f_i(x) 为第 ii 个残差项，那么Djfi(x)D_jf_i(x)表示 fi(x)f_i(x) 对第 jj 个变量的导数，则 Jij(x)=Djfi(x)J_{i j}(x)=D_{j} f_{i}(x)，梯度向量为

g(x)=∇12∥F(x) ∣∣2=J(x)⊤F(x)g(x)=\nabla \frac{1}{2}\|F(x)\ ||^{2}=J(x)^{\top}F(x)

解决非线性优化问题的一般策略是求解原始问题的一系列近似值。每次迭代时，都要求解近似值，以确定对向量 xx 的修正 Δx\Delta x。对于非线性最小二乘法，可以使用线性化 F(x+Δx)≈F(x)+J(x)ΔxF(x+\Delta x) \approx F(x)+J(x) \Delta x 来构建近似值，从而得到下面的线性最小二乘问题：

min⁡Δx12∥J(x)Δx+F(x)∥2\min _{\Delta x} \frac{1}{2}\|J(x) \Delta x+F(x)\|^{2}

不幸的是，直接求解这些问题的序列并更新 x←x+Δxx \leftarrow x+\Delta x 可能会导致算法无法收敛。为了得到收敛算法，我们需要控制步长 Δx\Delta x 的大小。 根据如何控制步长 Δx\Delta x 的大小，非线性优化算法可以分为两大类 。

  • Trust Region 信任区域法是在搜索空间的一个子集（称为信任区域）上使用一个函数（通常是二次函数）来逼近目标函数。如果函数成功地使真正的目标函数最小化，信任区域就会扩大；反之，信任区域就会缩小，并重新解决模型优化问题。

  • Line Search 直线搜索法首先找到一个下降方向，目标函数将沿着该方向缩小，然后计算步长，决定沿着该方向移动的距离。计算下降方向的方法有多种，如梯度下降法、牛顿法和准牛顿法。步长可以精确确定，也可以不精确确定。

信任区域法在某种意义上与直线搜索法具有双重性（或者翻译成两种方法是对偶的？）：信任区域法首先选择步长（信任区域的大小），然后选择步长方向，而直线搜索法首先选择步长方向，然后选择步长。Ceres Solver 实现了这两类中的多种算法。

Line Search Method

对于

min⁡Δx12∥J(x)Δx+F(x)∥2\min _{\Delta x} \frac{1}{2}\|J(x) \Delta x+F(x)\|^{2}

假设

ℓ(Δx)≡J(x)Δx+F(x)\ell (\Delta x) \equiv J(x) \Delta x+F(x)

则

12∥J(x)Δx+F(x)∥2≡12ℓ(Δx)⊤ℓ(Δx)=12F⊤F+Δx⊤J⊤F+12Δx⊤J⊤JΔx\begin{aligned} \frac{1}{2}\|J(x) \Delta x+F(x)\|^{2}& \equiv \frac{1}{2} \ell(\Delta \mathbf{x})^{\top} \ell(\Delta \mathbf{x}) \\ & =\frac{1}{2} \mathbf{F}^{\top} \mathbf{F}+\Delta \mathbf{x}^{\top} \mathbf{J}^{\top} \mathbf{F}+\frac{1}{2} \Delta \mathbf{x}^{\top} \mathbf{J}^{\top} \mathbf{J} \Delta \mathbf{x} \end{aligned}

在 xx 处进行的泰勒展开，则认为 xx 是已知的，现在的损失函数是一个关于 Δx\Delta x 的函数，其最小值，则令关于 Δx\Delta x 的导数为 00 即可。可以得到：

(JTJ)Δxgn=−JTF\mathbf{(J^T J)}\Delta x_{gn}=-\mathbf{J^T F}

上面这个形式就是我们在论文或者各种SLAM问题中经常见到的形式了，HΔx=b\mathbf{H \Delta x =b}，也叫做 normal equation。

可见，高斯牛顿法利用JTJ\mathbf{J}^T\mathbf{J} 来近似二阶海塞矩阵从而忽略了海塞矩阵的计算过程。求解增量方程就是整个优化问题的核心所在。基于此，高斯牛顿法的步骤为：

  1. 给定初始值x0\mathbf{x}_0；

  2. 对于第 k 次迭代，求解雅可比矩阵JJ和误差 F(x)F(x)；

  3. 求解增量方程 HΔx=g\mathbf{H}\Delta \mathbf{x}=\mathbf{g}；

  4. 若Δxk\Delta \mathbf{x}_k 足够下则停止迭代；

  5. 否则，令xk+1=xk+Δxk\mathbf{x}_{k+1}=\mathbf{x}_k + \Delta \mathbf{x}_k，继续第2 步。

从算法步骤可以看出，求解增量方程是最重要的。原则上，它要求JTJ\mathbf{J}^T\mathbf{J} 是可逆（并且是正定）的。但实际中，计算所得的JTJ\mathbf{J}^T\mathbf{J} 常常是半正定的。因此，在高斯牛顿法中，可能出现JTJ\mathbf{J}^T\mathbf{J} 是奇异阵或者病态的情况。此时求的Δx\Delta\mathbf{x} 不稳定，算法可能不收敛。就算 HH 满足要求，回想泰勒展开的一个隐含前提是：近似只在xk\mathbf{x}_k 附近有效。如果我们求得的步长Δx\Delta\mathbf{x} 太大，也会使得近似不够准确。

Trust Region Method

Levenberg (1944) 和 Marquardt (1963) 先后对高斯牛顿法进行了改进，泰勒展开只在展开点附近有较好的近似效果，而在高斯牛顿法并没有对这个“附近”有明确的定义。那么很自然地，我们就想给Δx\Delta \mathbf{x} 定义一个范围，限制它的大小。这个范围就叫做信赖区域 (trust region)，这类方法就叫信赖区域法。在信赖区域内，我们认为近似是有效的；在信赖区域外则近似会出现问题。例如限制

∣∣D(x)Δx∣∣2≤μ||\mathbf{D}(x)\Delta \mathbf{x}||^2\le\mu

μ\mu 就是我们给定的信赖区域，在列文伯格的方法中，DD是单位矩阵，以三维空间为例，意味着将增量Δx\Delta \mathbf{x} 限制在一个圆球中，认为只有在这个球中的增量才是有效的；而马夸尔特将DD取成非负对角矩阵，实际中常用JTJ\mathbf{J}^T\mathbf{J} 的对角元素的平方根，则是将增量限制在一个椭球之中。

此时问题就变成了如何确定信赖区域。一个比较直观也比较好的方法就是依据近似模型和实际函数之间的差异来确定，考虑使用:

ho=∥F(x+Δx)∥2−∥F(x)∥2∥J(x)Δx+F(x)∥2−∥F(x)∥2ho=\frac{\|F(x+\Delta x)\|^{2}-\|F(x)\|^{2}}{\|J(x) \Delta x+F(x)\|^{2}-\|F(x)\|^{2}}

来判断泰勒展开是否较好地近似了原模型。上式的分子是函数实际值，而分母是用来近似的泰勒展开得到的近似值。至于定性和定量分析应当如何更新我们放在后续小节。

PreviousBiCubicInterpolatorNextTrust Region Methodd

Last updated