Editing Levenberg–Marquardt algorithm (section)

=== Geodesic acceleration ===

When interpreting the Levenberg–Marquardt step as the velocity <math>\boldsymbol{v}_k</math> along a [[geodesic]] path in the parameter space, it is possible to improve the method by adding a second order term that accounts for the acceleration <math>\boldsymbol{a}_k</math> along the geodesic

:<math>
\boldsymbol{v}_k + \frac{1}{2} \boldsymbol{a}_k
</math>

where <math>\boldsymbol{a}_k</math> is the solution of

:<math>
\boldsymbol{J}_k \boldsymbol{a}_k = -f_{vv} .
</math>

Since this geodesic acceleration term depends only on the [[directional derivative]] <math>f_{vv} = \sum_{\mu\nu} v_{\mu} v_{\nu} \partial_{\mu} \partial_{\nu} f (\boldsymbol{x})</math> along the direction of the velocity <math>\boldsymbol{v}</math>, it does not require computing the full second order derivative matrix, requiring only a small overhead in terms of computing cost.<ref>{{cite web|url=https://www.gnu.org/software/gsl/doc/html/nls.html|title=Nonlinear Least-Squares Fitting|publisher=GNU Scientific Library|archive-url=https://web.archive.org/web/20200414204913/https://www.gnu.org/software/gsl/doc/html/nls.html|archive-date=2020-04-14}}</ref> Since the second order derivative can be a fairly complex expression, it can be convenient to replace it with a [[finite difference]] approximation

:<math>
\begin{align}
f_{vv}^i &\approx \frac{f_i(\boldsymbol{x} + h \boldsymbol{\delta}) - 2 f_i(\boldsymbol{x}) + f_i(\boldsymbol{x} - h \boldsymbol{\delta})}{h^2} \\
           &= \frac{2}{h} \left( \frac{f_i(\boldsymbol{x} + h \boldsymbol{\delta}) - f_i(\boldsymbol{x})}{h} - \boldsymbol{J}_i \boldsymbol{\delta} \right)
\end{align}
</math>

where <math>f(\boldsymbol{x})</math> and <math>\boldsymbol{J}</math> have already been computed by the algorithm, therefore requiring only one additional function evaluation to compute <math>f(\boldsymbol{x} + h \boldsymbol{\delta})</math>. The choice of the finite difference step <math>h</math> can affect the stability of the algorithm, and a value of around 0.1 is usually reasonable in general.<ref name="Transtrum2012"/>

Since the acceleration may point in opposite direction to the velocity, to prevent it to stall the method in case the damping is too small, an additional criterion on the acceleration is added in order to accept a step, requiring that

:<math>
\frac{2 \left\| \boldsymbol{a}_k \right\|}{\left\| \boldsymbol{v}_k \right\|} \le \alpha
</math>

where <math>\alpha</math> is usually fixed to a value lesser than 1, with smaller values for harder problems.<ref name="Transtrum2012"/>

The addition of a geodesic acceleration term can allow significant increase in convergence speed and it is especially useful when the algorithm is moving through narrow canyons in the landscape of the objective function, where the allowed steps are smaller and the higher accuracy due to the second order term gives significant improvements.<ref name="Transtrum2012"/>