# Introduction

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

$$x \in \mathbb{R}^{n}$$ 中）是一个 $$n$$ 维变量向量，$$F(x)=\left\[f\_{1}(x), \ldots, f\_{m}(x)\right]^{\top}$$ 是 $$x$$ 的一个 $$m$$ 维函数，$$f\_i(x)$$ 是一个标量函数，映射为 $$\mathbb{R}^{n}\to \mathbb{R}$$。 我们想解决优化问题如下

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

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

$$F(x)$$ 的 Jacobian $$J(x)$$ 是一个 $$m\times n$$ 的矩阵，$$m$$ 表示残差的维度，$$n$$ 为待优化变量的维度，$$J\_{i j}(x)$$ 表示第 $$i$$ 个残差分量对第 $$j$$ 个变量的导数，$$f\_i(x)$$ 为第 $$i$$ 个残差项，那么$$D\_jf\_i(x)$$表示 $$f\_i(x)$$ 对第 $$j$$ 个变量的导数，则 $$J\_{i j}(x)=D\_{j} f\_{i}(x)$$，梯度向量为

$$
g(x)=\nabla \frac{1}{2}|F(x)\ ||^{2}=J(x)^{\top}F(x)
$$

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

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

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

* **Trust Region** 信任区域法是在搜索空间的一个子集（称为信任区域）上使用一个函数（通常是二次函数）来逼近目标函数。如果函数成功地使真正的目标函数最小化，信任区域就会扩大；反之，信任区域就会缩小，并重新解决模型优化问题。
* **Line Search** 直线搜索法首先找到一个下降方向，目标函数将沿着该方向缩小，然后计算步长，决定沿着该方向移动的距离。计算下降方向的方法有多种，如梯度下降法、牛顿法和准牛顿法。步长可以精确确定，也可以不精确确定。

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

## Line Search Method

对于

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

假设

$$
\ell (\Delta x) \equiv J(x) \Delta x+F(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}
$$

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

$$
\mathbf{(J^T J)}\Delta x\_{gn}=-\mathbf{J^T F}
$$

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

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

> 1. 给定初始值$$\mathbf{x}\_0$$；
> 2. 对于第 k 次迭代，求解雅可比矩阵$$J$$和误差 $$F(x)$$；
> 3. 求解增量方程 $$\mathbf{H}\Delta \mathbf{x}=\mathbf{g}$$；
> 4. 若$$\Delta \mathbf{x}\_k$$ 足够下则停止迭代；
> 5. 否则，令$$\mathbf{x}\_{k+1}=\mathbf{x}\_k + \Delta \mathbf{x}\_k$$，继续第2 步。

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

## Trust Region Method

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

$$
||\mathbf{D}(x)\Delta \mathbf{x}||^2\le\mu
$$

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

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

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

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