c - Levenberg–Marquardt 算法如何以一种易于理解的方式详细工作？

Question

我是一名程序员，想了解 Levenberg–Marquardt 曲线拟合算法的工作原理，以便自己实现。是否有任何好的教程可以详细解释它是如何与作为程序员而不是数学家的读者一起工作的。

我的目标是在 opencl 中实现这个算法，这样我就可以让它运行硬件加速。

Answer 1

最小化函数就像试图找到曲面上的最低点。想象一下你自己走在丘陵表面上，你正试图到达最低点。你会找到下坡的方向，然后一直走，直到它不再下坡为止。然后你会选择一个新的下坡方向，然后沿着那个方向走，直到它不再下坡，等等。最终(希望如此)你会到达一个不再有方向下坡的点。然后您将处于(本地)最低限度。

LM 算法和许多其他最小化算法都使用这种方案。

假设被最小化的函数是 F 并且我们在迭代中位于点 x(n)。我们希望找到下一个迭代 x(n+1) 使得 F(x(n+1)) < F(x(n))，即函数值更小。为了选择 x(n+1)，我们需要两件事，x(n) 的方向和步长(在那个方向上走多远)。 LM 算法确定这些值如下 -

首先，在点 x(n) 处计算 F 的线性近似值。很容易找出线性函数的下坡方向，因此我们使用线性逼近函数来确定下坡方向。接下来，我们需要知道在这个选择的方向上我们能走多远。如果我们的近似线性函数是 F 对于 x(n) 周围大面积的良好近似，那么我们可以采取相当大的步骤。如果它是一个非常接近 x(n) 的良好近似值，那么我们只能采取非常小的步骤。

这就是 LM 所做的——计算 F 在 x(n) 处的线性逼近，从而给出下坡方向，然后它根据线性函数在 x(n) 处逼近 F 的程度计算出要采取多大的步长). LM 通过基本上在确定的方向上迈出一步并将对 F 的线性逼近减少了多少与实际函数 F 减少了多少进行了比较，从而计算出逼近函数有多好。如果它们很接近，则逼近函数很好，我们可以采取更大的步骤。如果它们不接近，则近似函数不好，我们应该后退并采取更小的步骤。