知识库 › 定位仓库学习 › 核心算法 › 最小二乘问题 › 列文伯格-马夸特法
之前介绍了牛顿法、梯度下降法和高斯牛顿法，其各自有自己的优点和缺点。我们需要的是一种更加智能的算法，通过自动迭代去适应环境，然后自主决策路径的选择，实现动态调整步长，在较远处能够迈出更大的步伐，在近处能够以更加精细的步伐去接近目标。所以在实践中，我们经常采用列文伯格-马夸特法，或者说LM法或信赖域法。
首先，我们需要构造一个衡量步伐准确性的工具，作为算法自主决策的依据。我们令：
$$\rho = \frac{f(x) - f(x + \Delta x)}{L(0) - L(\Delta x)}$$
其中 $L(\Delta x)$表示函数的泰勒二阶展开式
$$L(\Delta x) = F(x) + g(x)^\top \Delta x + \tfrac{1}{2} \Delta x^\top H \Delta x$$
同时呢，我们需要求解的问题：
$$\min_{\Delta x} \tfrac{1}{2} \|f(x) + J(x)\Delta x\|^2 \quad \text{s.t.} \quad \|D \Delta x\|_2 < \mu$$
变成了一个带限制条件的最小值求解问题，我们可以直接构造拉格朗日函数，使用拉格朗日乘数法进行最值求解。
$$L(\Delta x, \lambda) = \tfrac{1}{2} \|f(x) + J(x)\Delta x\|^2 + \tfrac{\lambda}{2} (\|D \Delta x\|^2 - \mu)$$
求导然后令导数为0，得到我们需要的这个增量方程。
$$(J^\top J + \lambda D^\top D)\, \Delta x = -J^\top f$$
移项
$$\Delta x = -(J^\top J + \lambda D^\top D)^{-1} J^\top f$$
注意到这里存在一个名为 $D^TD$的项，这个是用来对限制条件进行缩放的，用于调整不同参数方向上的信任程度，在实践中一般直接采用单位矩阵 $I$，代表一个球型域。
其中的 $\lambda$ 需要带入该式子并根据初始约束条件反解出来，也就是说如果需要求出 $\lambda$ 的话，就是在求在什么时候使得步长刚好等于信赖域大小。这个式子是一个非线性方程，且不存在解析解。想要求出来需要进行复杂的迭代或者二分。在工程实践中，我们实际上会直接先带入一个初始的阻尼系数 $\lambda=0.01$（注：本项目中实际取 $\texttt{solver\_lambda}=0.05$，信任半径初始化为 10.0，且每次 $\texttt{solve()}$ 都重置）然后让本该参与后续缩放的信任域 $\mu$ 退出运算，或者说，由于拉格朗日乘数法的正常进行，导致含信赖域项本来就会自然消失掉，实际上它也并不参与阻尼系数的迭代。可以观察到，当 $\lambda$ 趋近于0，此时附加项趋向于0，对H项的影响非常小，等同于直接采用了高斯牛顿下降法，而如果趋向于正无穷，则会导致H几乎不影响变化，$\lambda$ 直接影响步长，且转换后能够看出来类似梯度下降法，控制倍率几乎只受 $\frac{1}{\lambda}$ 影响。
这样子我们能够计算得到一个评判下降合理程度的参数。一般来说，如果 $\rho>0.75$且在1附近就说明该步拟合的效果不错，可以减小 $\lambda$，放大信任域，大胆往下走；如果 $\rho<0.25$就说明这一步太大了，需要扩大 $\lambda$，让步进距离变小，稍微谨慎一点向下。如果 $\rho$小于0就说明这个步进使得函数值反而上升，需要大幅扩大 $\lambda$使得信任域收缩。
这样子来看之前的 $\mu$就真正意义上变成滚木了，后面的调控也完全是由$\lambda$来决定了。
在这个的基础上，还有别的基于信任域的下降算法，比如狗腿法等。