Dogleg算法

作为一种信任域方法的拓展，狗腿算法同样使用了一个圆域用来对路径进行选择，但是直接使用几何方法构建了下降路径，避免了LM法中迭代反解的步骤，每一次运算都大概率能够正常下降。降低了运算难度。

之前提到了为了解决高斯牛顿法的步进过于大胆、以及单纯梯度下降面临的速度太慢、迭代困难的问题，该项目采用了狗腿法，通过设定自主迭代的信任域半径r以及两种方法分别对应的终点折线，得到一种自适应的下降策略。

对于每次解算，我们先设置默认半径r，计算当前下降步骤的两段折线，如果r大于高斯牛顿的步长，就直接取高斯牛顿的距离；如果处于梯度下降步长到高斯牛顿步长之间，就直接取圆与折线交点位置作为下降终点，显然此时步进距离就是r；如果小于梯度下降步进距离，此时的下降方向被梯度下降方向截断，步进距离依旧选取r。

在这个逐级下降的过程中，r并不是一成不变的，事实上，r受到一套计算法则的规范，最开始初始化为10之后，每次迭代的运算都会和一个步骤正确率rou的影响：

ρ ≤ 1e-3  或  ρ 是 NaN
    →  拒绝这一步，回滚状态
    →  r 减半；如果减半后 r 仍大于 ‖Δ_gn‖，就继续减半
       （直到 r < ‖Δ_gn‖ 为止，确保下次走一个不同的、更短的步）

1e-3 < ρ < 0.25
    →  接受
    →  r 减半

0.25 ≤ ρ ≤ 0.75
    →  接受
    →  r 不变（死区）

ρ > 0.75
    →  接受
    →  r = max(r, 3 × ‖Δ‖)
       若这一步本来就受半径限制（‖Δ‖ = r），r 变成 3 倍
       若这一步没受半径限制（‖Δ‖ 较小），r 不变

这个rou的计算方法是用实际下降除以预测下降，其中实际下降是直接用原代价函数带入得到的步进终点，与原位置代价作差得到；预测下降是对高斯牛顿法得到的二次估计函数进行展开，然后带入步进值和曲率计算得出。计算这两个数据并不用消耗多少算力，所以算是一个很廉价的方式，就能得到“预估模型和实际模型相似度”的这么一个参数。通过带入上面的判断法则，我们就能够判断当前步骤是否符合预测，进而调整r的大小，从代码上看就是直接折半，事实也证明这种折半的思路能够帮我们更快收敛到合适的步进距离。

哦对了，刚才提到的梯度下降距离还没有给出详细的计算步骤呢。按照一般的思路，沿着特定函数梯度下降的距离直接采用梯度大小的特定系数倍即可，经过足够时间的迭代，就一定能够收敛于某个极值点。在当前项目中，作者创新性地使用了dogleg中的半径r，用这个r除以梯度行列式来作为这个系数。

$$\Delta = -\frac{r}{\|\nabla F\|}\nabla F,\qquad\alpha = \frac{r}{\|\nabla F\|}$$

在工程实践中，该梯度下降距离也随着r的变化而变化，从定性的角度来看也确实能够在梯度下降中间接反映出之前函数形状对下降路径的调节作用，进而在每一步下降中体现出某种意义上的负反馈。