Hacker News Reader

Comment by wenc | Hacker News Reader

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 likely the efficiency of the linear algebra (MA57) algorithm will dominate since it is as you say, constraint satisfaction.

View on HN

> 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...

isn't MA57 just a standard good sparse linear solver? For sparse problems, NonlinearSolve.jl (via LinearSolve.jl) will either use KLU or Cholmod both of which are also quite fast. Also, even if the linear solver is the bottleneck, that doesn't mean different algorithms won't make a differenc.e Different nonlinear solve algorithms can lead to needing fewer iterations (e.g. fewer linear solves).

I don’t know. I’m curious is all.

MA57 seems generic but I’ve tried different linear solvers with IPOPT even ones that were supposed to be better, but MA57 still performed the best.

Nonlinear numerical problems involve a bit of art. Theory doesn’t always pan out in practice.

MA57 is a sparse symmetric solver. IPOPT uses this because it solves a modified KKT system that includes both the Hessian and constraint information simultaneously. This differs from composite step methods, which split the optimization step into a step for feasibility (quasi-normal step) and a step for optimality (tangential step). An algorithm like NITRO uses a composite step method and as a result uses a different kind of linear system solver.

Reply on news.ycombinator.com