# Comparing non-linear least squares solvers

**URL:** <https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752>\
**Category:** Optimization (Mathematical)\
**Tags:** nonlinear, nonlinear-optimizati\
**Created:** [October 9, 2023, 1:37pm UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752 "2023-10-09T13:37:45Z")\
**Posts on this page:** 18\
**Page:** 2

<div class="post-metadata">

**Author:** ![TheLateKronos](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thelatekronos/32/12824_2.png) [@TheLateKronos](https://discourse.julialang.org/u/TheLateKronos)\
**Post date:** [October 11, 2023, 7:35am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/21 "2023-10-11T07:35:58Z")

</div>

Lovely. JuliaPackageComparisons is nowhere close to what I want it to be, but quality content like exactly what is needed to get it there!

---

<div class="post-metadata">

**Author:** ![user664303](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user664303/32/37843_2.png) [@user664303](https://discourse.julialang.org/u/user664303)\
**Post date:** [October 12, 2023, 1:15pm UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/22 "2023-10-12T13:15:18Z")

</div>

Just a note to say I’ve updated the table and graphs in the first post of this thread. They now include only those solvers that I was able to add to the benchmark code.

If you’d like to see a specific solver added to the table, please first add it to [the benchmark](https://gist.github.com/ojwoodford/789e85197b18dcddb349e1f695bffc31).

---

<div class="post-metadata">

**Author:** ![ig-or](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ig-or/32/4975_2.png) [@ig-or](https://discourse.julialang.org/u/ig-or)\
**Post date:** [October 12, 2023, 11:11pm UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/23 "2023-10-12T23:11:31Z")

</div>

What is a good simple to use solver package for the case when one single cost function evaluation takes about 100 minutes? I know this depend on the function itself, but this I do not know yet… should I start with [BlackBoxOptim.jl](https://github.com/robertfeldt/BlackBoxOptim.jl) ?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [October 13, 2023, 12:33am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/24 "2023-10-13T00:33:06Z")

</div>

> [@ig-or](#):
>
> What is a good simple to use solver package for the case when one single cost function evaluation takes about 100 minutes?

Depends a lot on your function. How many parameters does it have? Is it differentiable? (If so, it’s ideal if you can compute derivatives, but even if not there are derivative-free algorithms that internally exploit the existence of derivatives.) What kind of constraints?

---

<div class="post-metadata">

**Author:** ![pkofod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pkofod/32/2179_2.png) [@pkofod](https://discourse.julialang.org/u/pkofod)\
**Post date:** [October 13, 2023, 7:53am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/25 "2023-10-13T07:53:08Z")

</div>

The Rosenbrock function has a global minimum of 0. You may want to include another variant of the Rosenbrock function, say something like

 ![Skærmbillede 2023-10-13 kl. 07.52.51](https://global.discourse-cdn.com/julialang/original/3X/f/e/fec9caa313131e7a7843f0b78c5d1fa769e6ed24.png)

that I got from “METHODS FOR NON-LINEAR LEAST SQUARES PROBLEMS” by K. Madsen, H.B. Nielsen, O. Tingleff (link: [http://www2.imm.dtu.dk/pubdb/edoc/imm3215.pdf](http://www2.imm.dtu.dk/pubdb/edoc/imm3215.pdf) ). Why? Because LM and some other NLS specific algorithms can have poor convergence properties when the residual at the optimum is significantly different from 0. You can control the final residual by varying at lambda.

If you’re using this to solve nonlinear equations you’re fine because the residual will be 0 at the solution (convergence rates emerge from local properties so it’s the residual at the solution that’s important), otherwise you should maybe consider some curve fitting (to data) examples as well. However, using nonlinear least squares to solve systems of equations has it’s own set of issues, because local solutions to the nonlinear least squares problem does not necessarily have zero residuals, and as such they may not solve the underlying nonlinear equations you’re trying to solve.

For several reason, including the non-zero residual error issue above, I personally have great experience with _not_ using LM for NLS. There are so many other algorithms out there for nonlinear optimization that can be more robust and often converge quite quickly. LM was an excellent invention that brought a trust region-like approach to NLS, but I’m actually not quite sure that LM is seen as a leading algorithm in 2023. Looking at CERES it seems like they have made the same conclusion and they include N-CG, BFGS, etc as well.

I never got around to reimplementing LM for NLSolvers.jl, but my point is just that “any optimizer” is a “NLLS/NLS solver”. Can you exploit structure? Yes. Is it necessarily the most important part when picking a solver? Not sure. I’m not an expert on this topic, but the JuliaSmoothOptimizers people have their solver and have actually published in the field, so maybe they have more to say. The scale of the problem also plays a role.

---

<div class="post-metadata">

**Author:** ![user664303](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user664303/32/37843_2.png) [@user664303](https://discourse.julialang.org/u/user664303)\
**Post date:** [October 13, 2023, 9:52am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/26 "2023-10-13T09:52:29Z")

</div>

> [@pkofod](#):
>
> LM and some other NLS specific algorithms can have poor convergence properties when the residual at the optimum is significantly different from 0.

Thanks for this. Very interesting. I am sceptical about the claim, and have studied the reference you gave (which I’m familiar with). I really don’t understand how they can claim this. The quadratic problem at each step will be identical (given the same x), so the step taken can only be affected by the value of the damping factor. The damping factor update will only be impacted by the offset in so much as the offset will reduce the accuracy of the change in cost, due to floating point round off. I would expect this to have minimal impact. I’ve written a [gist here](https://gist.github.com/ojwoodford/4d14f1bb79d551909c332f0b93ed1308) to test the claim, and it does indeed show that the non-zero residual makes almost no difference. Most of the steps taken are identical, then very close to the minimum the damping factor of the augmented problem drops faster, so the optimizer actually converges faster. Here’s the output (I’ve adjusted the cost of the augmented problem in the graph, so the two costs are directly comparable):

 ![Screenshot 2023-10-13 at 10.51.18](https://global.discourse-cdn.com/julialang/original/3X/e/d/ed7c78ff3712fb86280a29f37515d0232f838dc7.jpeg)

The code is an interactive plot, allowing you to select different starting points in the state space.

> [@pkofod](#):
>
> Looking at CERES it seems like they have made the same conclusion and they include N-CG, BFGS, etc as well.

I think the presence of these solvers in Ceres is more so people can compare, rather than they’re better. For the types of problems that people tend to solve with Ceres (visual geometry problems), which do end up with non-zero residuals, LM is usually the best. See [Bundle Adjustment - A Modern Synthesis](https://inria.hal.science/inria-00548290/file/Triggs-va99.pdf).

> [@pkofod](#):
>
> “any optimizer” is a “NLLS/NLS solver”

Yes. But they don’t exploit Gauss’ approximation to the Hessian. NLLS-specific solvers do, such that:

1. The approximate Hessian can be computed using only the 1st derivative of the residuals (as opposed to twice differentiating the squared cost function). It’s simpler and more efficient.
2. The Hessian is positive (semi-)definite, so the gauss-newton step is always a minimum of the quadratic approximation.

This is why (I believe) general solvers tend to have worse performance. But I’m very happy to be proved wrong. I’d love to find a better solver than LM.

---

<div class="post-metadata">

**Author:** ![pkofod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pkofod/32/2179_2.png) [@pkofod](https://discourse.julialang.org/u/pkofod)\
**Post date:** [October 13, 2023, 9:54am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/27 "2023-10-13T09:54:14Z")

</div>

You point about the specific example seems quite valid. I agree.

---

<div class="post-metadata">

**Author:** ![user664303](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user664303/32/37843_2.png) [@user664303](https://discourse.julialang.org/u/user664303)\
**Post date:** [October 13, 2023, 9:57am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/28 "2023-10-13T09:57:38Z")

</div>

Perhaps it’s different if the non-zero residuals actually depend on the variables. Not sure. But I find in practice, on real problems with non-zero residuals, that LM works very well.

---

<div class="post-metadata">

**Author:** ![pkofod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pkofod/32/2179_2.png) [@pkofod](https://discourse.julialang.org/u/pkofod)\
**Post date:** [October 13, 2023, 10:01am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/29 "2023-10-13T10:01:02Z")

</div>

LM can work while being suboptimal 🙂 But yes, I took the example because it was easy, but in the examples I had it mind, it would be nonzero in a slightly more complicated manner. But I’m happy to be proven wrong.

---

<div class="post-metadata">

**Author:** ![user664303](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user664303/32/37843_2.png) [@user664303](https://discourse.julialang.org/u/user664303)\
**Post date:** [October 13, 2023, 4:15pm UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/30 "2023-10-13T16:15:45Z")

</div>

> [@TheLateKronos](#):
>
> Would you concider making a PR to add it to [JuliaPackageComparisons](https://github.com/JuliaPackageComparisons/JuliaPackageComparisons.github.io)

@TheLateKronos There’s [a PR](https://github.com/JuliaPackageComparisons/JuliaPackageComparisons.github.io/pull/19) waiting to be merged. 😄

---

<div class="post-metadata">

**Author:** ![mateuszbaran](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mateuszbaran/32/221842_2.png) [@mateuszbaran](https://discourse.julialang.org/u/mateuszbaran)\
**Post date:** [October 20, 2023, 9:01am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/31 "2023-10-20T09:01:20Z")

</div>

Regarding non-Euclidean variables (especially those from non-Hadamard manifolds like sphere or SO(3)), I think it is important to note that there are two standard ways of handling the issue of not being able to cover the entire manifold with one chart. The most common one is using retractions, vector transports and bases of tangent spaces. This is what Manopt.jl does. The other one is chart switching, which is easier to integrate with generic Euclidean solvers, and is the way Manifolds.jl handles integrating geodesics. I don’t see how NLLSsolver.jl does either?

---

<div class="post-metadata">

**Author:** ![user664303](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user664303/32/37843_2.png) [@user664303](https://discourse.julialang.org/u/user664303)\
**Post date:** [October 20, 2023, 9:47am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/32 "2023-10-20T09:47:03Z")

</div>

> [@mateuszbaran](#):
>
> retractions, vector transports and bases of tangent spaces… chart switching

Unfortunately I’m not familiar with these terms.

In NLLSsolver, each variable type has an `update` function implemented, that essentially takes a Euclidean vector in the tangent space of the current variable state (i.e. passing in a vector of zeros for the update vector will return the current variable state), and updates the variable state accordingly. This generally involves a projection onto the manifold. Perhaps that’s what you mean by retraction? At each iteration, the Euclidean space that the linear solver works in is updated to the current tangent space of each variable - perhaps this is what you mean by chart switching?

To summarize, the update function takes in a variable type and a Euclidean vector in the current tangent space of the variable, and outputs a suitably updated variable. NLLSsolver is agnostic to what the update method does under the hood, or indeed anything else about the variable.

My implementation for SO(3) matrices can be seen [here](https://github.com/ojwoodford/NLLSsolver.jl/blob/1c7c5a24153062e9b9558a43ca41f23fa7ede1e8/src/visualgeometry/geometry.jl#L61). The `rodrigues` method computes the exponential map from {\mathfrak {so}}(3) to SO(3).

I think it would be easy to use any `Manifolds.jl` type, simply by implementing this `update` function, plus an `nvars` function that returns the dimensionality of the tangent space. Is there an abstract `Manifolds` type for which it can be defined?

---

<div class="post-metadata">

**Author:** ![mateuszbaran](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mateuszbaran/32/221842_2.png) [@mateuszbaran](https://discourse.julialang.org/u/mateuszbaran)\
**Post date:** [October 20, 2023, 10:14am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/33 "2023-10-20T10:14:57Z")

</div>

> [@user664303](#):
>
> n NLLSsolver, each variable type has an `update` function implemented, that essentially takes a Euclidean vector in the tangent space of the current variable state (i.e. passing in a vector of zeros for the update vector will return the current variable state), and updates the variable state accordingly. This generally involves a projection onto the manifold. Perhaps that’s what you mean by retraction?

Yes, `update` is similar to retraction.

> [@user664303](#):
>
> Euclidean space that the linear solver works in is updated to the current tangent space of each variable - perhaps this is what you mean by chart switching?

No, chart switching is different. It sounds more similar the retraction-based approach. SO(3) is not an ideal example here because you can just use Lie algebra which simplifies things but in general you can’t assume that a tangent vector at one point can just be used at another one. Vector transport is what adapts tangent vectors between points. Very often just doing a projection is enough (that’s what Optim.jl does) but Manopt.jl is more generic.

---

<div class="post-metadata">

**Author:** ![user664303](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user664303/32/37843_2.png) [@user664303](https://discourse.julialang.org/u/user664303)\
**Post date:** [October 20, 2023, 10:26am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/34 "2023-10-20T10:26:37Z")

</div>

> [@mateuszbaran](#):
>
> in general you can’t assume that a tangent vector at one point can just be used at another one. Vector transport is what adapts tangent vectors between points

Unless I’ve misunderstood what you’re saying, my solver doesn’t transport tangent vectors (Euclidean vectors in the tangent space?) between different points/tangent spaces. But I’m very happy to engage in a private chat to get to the bottom of what you’re saying.

---

<div class="post-metadata">

**Author:** ![mateuszbaran](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mateuszbaran/32/221842_2.png) [@mateuszbaran](https://discourse.julialang.org/u/mateuszbaran)\
**Post date:** [October 20, 2023, 10:46am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/35 "2023-10-20T10:46:32Z")

</div>

I see, NLLSolver.jl algorithms just don’t require vector transport, thanks for clarification.

---

<div class="post-metadata">

**Author:** ![user664303](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user664303/32/37843_2.png) [@user664303](https://discourse.julialang.org/u/user664303)\
**Post date:** [October 20, 2023, 10:50am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/36 "2023-10-20T10:50:26Z")

</div>

Correct. NLLSsolver never uses information computed in one tangent space to compute an update step in another tangent space (indeed, I’m aware of the problem associated with doing this). Hence vector transport is never required.

---

<div class="post-metadata">

**Author:** ![user664303](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user664303/32/37843_2.png) [@user664303](https://discourse.julialang.org/u/user664303)\
**Post date:** [October 25, 2023, 2:37pm UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/37 "2023-10-25T14:37:40Z")

</div>

The comparison I published in the original post has now been published in [juliapackagecomparisons.github.io](https://juliapackagecomparisons.github.io/pages/nonlinear_solvers/#nonlinear_least_squares_solvers).

Thanks, @TheLateKronos, for creating that resource. I hope it takes off.

---

<div class="post-metadata">

**Author:** ![user664303](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user664303/32/37843_2.png) [@user664303](https://discourse.julialang.org/u/user664303)\
**Post date:** [March 5, 2024, 9:34am UTC](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752/38 "2024-03-05T09:34:42Z")

</div>

The comparison has moved, to [here](https://juliapackagecomparisons.github.io/comparisons/math/nonlinear_solvers/#nonlinear_least_squares_solvers).

[Previous page](https://discourse.julialang.org/t/comparing-non-linear-least-squares-solvers/104752.md?page=1)