Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Nonlinearsolve.jl: Fast and Robust Solvers for Nonlinear Equations in Julia

arxiv.org

Post reply on HN
Print view View original

31–37 of 37 posts

Re: Nonlinearsolve.jl: Fast and Robust Solvers for Nonlinear Equations in Julia

#31

Post by ChrisRackauckas »

kxyvr wrote: post #30
ChrisRackauckas wrote: post #27

Earlier quoted context omitted.

> It's very robust, matrix-free, and doesn't require an excessive amount of code to implement. Further, the method can be preconditioned with a positive definite preconditioner. It is not robust, in fact it's well-known as a numerically unstable method. g'(x)*g'(x)` is numerically unstable because it squares the condition number of the matrix. If you have a condition number of 1e-10, which is true for many examples i…

Yes, care must be taken to stabilize the algorithm. However, I do not believe it to be true that no digits of accuracy can be obtained. The algorithm falls back to the Cauchy (steepest-descent) point on the first iteration and this will give reduction. That said, I'm willing to solve this particular problem and see. Where's your code for the DFN battery model? The page here leads to a dead github link: https://help.j…

The full DFN has a lot more going on. Use the benchmark-ified version from the benchmarks:

https://docs.sciml.ai/SciMLBenchmarksOutput/dev/NonlinearPro...

But as Avik states, this same kind of thing is done as part of the trust region methods, and so the trust region stuff with some ways to avoid J'J is effectively doing the same thing, though of course that cannot target a symmetric linear solver because J is not generally symmetric and it needs to do the L2 solve so it needs a QR/GMRES.

But indeed, let's get IPOPT in this interface and benchmarks and show it in the plots.

Re: Nonlinearsolve.jl: Fast and Robust Solvers for Nonlinear Equations in Julia

#32

Post by guyomes »

wenc wrote: post #20
ChrisRackauckas wrote: post #14

Earlier quoted context omitted.

Definitely an interesting response I didn't see coming. This is one of the reasons to share preprints! IPOPT is a nonlinear optimization tool, not a nonlinear solver. Generally from what I've seen it's not a good idea to solve nonlinear systems with a nonlinear optimizer, but you can phrase it as a "constraint satisfaction problem", i.e. a nonlinear optimization with a trivial `maximize 0` loss function but with equa…

Yes tribal knowledge says NLP solvers aren’t tailored to NLE solvers as NLE solvers are. There have been papers in this past showing this but in my experience, it’s not obvious in practice. Nonlinear systems can often surprise us. The initial point (and randomness) has more influence on the solution time than almost anything else. I forget the exact internal formulation of the problem in IPOPT but for an NLE it’s lik…

> The initial point (and randomness) has more influence on the solution time than almost anything else.

On that remark, a theoretical tool to choose the initial point is the Newton Polygon. For univariate polynomials, this leads to some of the fastest solver [1]. The idea to choose the initial point in this case is notably described in Section 6 of this paper [2].

A very rough intuition of the idea is that a polynomial p(z) doesn't vanish if one of its monomials is significantly larger than all the other. Reciprocally, the polynomial has more chances to vanish for values z such that two monomials have the same order of magnitude. Hence this is a good value to choose your initial point. Finally, deciding if two monomials have the same order of magnitude can be done by taking their log, and then it becomes geometry with polygons, hence the name Newton Polygon.

[1]: https://numpi.dm.unipi.it/scientific-computing-libraries/mps...

[2]: https://woelen.homescience.net/science/math/exps/polynomials...

Re: Nonlinearsolve.jl: Fast and Robust Solvers for Nonlinear Equations in Julia

#33

Post by kxyvr »

ChrisRackauckas wrote: post #31
kxyvr wrote: post #30

Earlier quoted context omitted.

Yes, care must be taken to stabilize the algorithm. However, I do not believe it to be true that no digits of accuracy can be obtained. The algorithm falls back to the Cauchy (steepest-descent) point on the first iteration and this will give reduction. That said, I'm willing to solve this particular problem and see. Where's your code for the DFN battery model? The page here leads to a dead github link: https://help.j…

The full DFN has a lot more going on. Use the benchmark-ified version from the benchmarks: https://docs.sciml.ai/SciMLBenchmarksOutput/dev/NonlinearPro... But as Avik states, this same kind of thing is done as part of the trust region methods, and so the trust region stuff with some ways to avoid J'J is effectively doing the same thing, though of course that cannot target a symmetric linear solver because J is not ge…

What's your convergence metric? It looks like x_sol gives a residual on the order of 1e-7. That's fine, but I'd like to measure an equivalent number to the benchmark.

Re: Nonlinearsolve.jl: Fast and Robust Solvers for Nonlinear Equations in Julia

#34

Post by FreakLegion »

wenc wrote: post #18
FreakLegion wrote: post #6

Earlier quoted context omitted.

> all nonlinear equation systems are nonconvex Maybe you have something more particular in mind when you say "systems", but not all nonlinear functions are non-convex. Least squares, for example, is nonlinear and convex. Also note that IPOPT, while wonderful, is a local solver. It may not be limited to convex problems, but those are the only ones it's guaranteed to solve to optimality.

I was talking in terms of convex optimization. The criteria for convex optimization is convex objective, convex inequality constraints and convex feasible region, and linear (not just convex) equality constraints. I’m aware that ipopt is a local solver.

> all nonlinear equation systems are nonconvex

> I was talking in terms of convex optimization

I'm not sure what subtlety you're pointing to here. As far as non-convex problems, though, my point is that IPOPT isn't special in this regard. Any convex solver can be a non-convex solver if you don't care about global optimality.

Re: Nonlinearsolve.jl: Fast and Robust Solvers for Nonlinear Equations in Julia

#35

Post by wenc »

FreakLegion wrote: post #34
wenc wrote: post #18

Earlier quoted context omitted.

I was talking in terms of convex optimization. The criteria for convex optimization is convex objective, convex inequality constraints and convex feasible region, and linear (not just convex) equality constraints. I’m aware that ipopt is a local solver.

> all nonlinear equation systems are nonconvex > I was talking in terms of convex optimization I'm not sure what subtlety you're pointing to here. As far as non-convex problems, though, my point is that IPOPT isn't special in this regard. Any convex solver can be a non-convex solver if you don't care about global optimality.

> Any convex solver can be a non-convex solver if you don't care about global optimality.

Aside: Structurally I’m not sure how this would be true.

Convex solvers have very specific forms. For instance a QP solver requires a very particular form and does not admit any arbitrary non convex form except for one: the non-PSD Hessian which is the concave problem.

My point is that all NLEs power inside an optimization problem gives rise to a non convex optimization problem with no guarantee of a global solution. So convex optimization is not applicable here.

Re: Nonlinearsolve.jl: Fast and Robust Solvers for Nonlinear Equations in Julia

#36

Post by ChrisRackauckas »

kxyvr wrote: post #33
ChrisRackauckas wrote: post #31

Earlier quoted context omitted.

The full DFN has a lot more going on. Use the benchmark-ified version from the benchmarks: https://docs.sciml.ai/SciMLBenchmarksOutput/dev/NonlinearPro... But as Avik states, this same kind of thing is done as part of the trust region methods, and so the trust region stuff with some ways to avoid J'J is effectively doing the same thing, though of course that cannot target a symmetric linear solver because J is not ge…

What's your convergence metric? It looks like x_sol gives a residual on the order of 1e-7. That's fine, but I'd like to measure an equivalent number to the benchmark.

It's varied, that's why it's measured as work-precision. It would be good to similarly produce a full work-precision line as point estimates do not tell the full story.

Note that we are preparing an extension to easily use the optimizers https://github.com/SciML/NonlinearSolve.jl/pull/395 to add it to the benchmarks.

Re: Nonlinearsolve.jl: Fast and Robust Solvers for Nonlinear Equations in Julia

#37

Post by akutlay »

ChrisRackauckas wrote: post #16
affinepplan wrote: post #15

Earlier quoted context omitted.

those are indeed very popular tools but for a slightly different kind of problem than this package is attempting to solve

Yes, especially Highs is completely unrelated because it's for (mixed integer) linear programming problems and quadratic programming problems, so it's not able to solve the types of problems described in this manuscript. IPOPT is a bit of a stretch but I do know that there are some people in the mathematical programming space that use IPOPT's constraint satisfaction piece for solving a nonlinear system in a pinch, bu…

Thank you very much for your answer!
Post reply on HN