+++ title = "Nonlinear Solvers" +++
This section is still missing a lot of content. If you have used or developed Julia packages in this domain, we would love your help! Please visit the "Contributing" section of the repository that hosts this website for information on contributions. Table of contents: \toc
This section will be split into two categories; Numerical nonlinear solvers, and symbolic nonlinear solvers.
The most complete one is NonlinearSolve.jl, which is part of the SciML ecosystem. It takes the role of a meta-package, and build on top of other packages that implement the actual algorithms. The benefit is that you can define the problem once, and then solve it with a number of different solvers by changing a keyword argument.
The JuMP.dev framework provides a simple grammar for defining optimization cost functions, or models. It allows non-linear models to be defined, which can then be optimized using any of the compatible solvers, such as Ipopt.jl
There are also a number of other packages that provide nonlinear solver algorithms. Several of them are part of the JuliaNLSolvers organization, such as NLSolve.jl and Optim.jl. There is also Roots.jl and SIAMFANLEquations.jl.
Finally, there are a number of packages that specialize in optimizing nonlinear least-squares functions, discussed below.
Nonlinear Least Squares (NLLS) solvers are a particular class of numerical nonlinear solvers that optimize problems of the form:
\begin{align*}\argmin_{\mathbf{x}} & \frac12 \sum_i \rho_i\left(| f_i(\mathbf{x})|^2\right), \
\mathrm{s.~to} & c_j(\mathbf{x}) < b_j ~~\forall j, \
& c_k(\mathbf{x}) = e_k ~~\forall k, \end{align*}
where
-
$\mathbf{x}$ is the set of variables to be optimized over. -
$f_i()$ are (potentially multi-dimensional) nonlinear functions of$\mathbf{x}$ , whose squared norms are to be minimized. -
$\rho_i()$ are monotonically increasing robustification functions, that can be used to downweight larger errors. -
$c_j()$ are linear or nonlinear scalar functions of$\mathbf{x}$ on the output of which bound constraints$b_j$ are placed. -
$c_k()$ are linear or nonlinear scalar functions of$\mathbf{x}$ on the output of which equality constraints$e_k$ are placed.
A number of packages and solvers exist for this class of problem:
- From JuliaNLSolvers: LsqFit.jl for curve fitting
- From Julia Smooth Optimizers: tron and trunk (in JSOsolvers.jl), for bound constrained and unconstrained problems, and CaNNOLeS.jl for equality constrained problems.
- LeastSquaresOptim.jl for problems with bound constrained variables.
- NLLSsolver.jl for problems with robustified cost functions and non-Euclidean variables (e.g. variables on a manifold).
More general nonlinear solvers can also often be used to optimize NLLS problems, e.g.
However, the more specialized packages tend to offer better performance.
Different packages and solvers offer different features. Here's a summary of the important ones:
Ipopt | tron | trunk | CaNNOLeS.jl | NLLSsolver.jl | LeastSquaresOptim.jl | |
---|---|---|---|---|---|---|
Registered | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
Uses JuMP model definition | ✅ | ✅ | ✅ | ✅ | ❌ | ❌ |
Bound constraints | ✅ | ✅ | ❌ | ❌ | ❌ | ✅ |
Equality constraints | ✅ | ❌ | ❌ | ✅ | ❌ | ❌ |
Non-linear constraints | ✅ | ❌ | ❌ | ✅ | ❌ | ❌ |
Robustified cost functions | ❌ | ❌ | ❌ | ❌ | ✅ | ❌ |
Non-Euclidean variables | ❌ | ❌ | ❌ | ❌ | ✅ | ❌ |
Dense auto-differentiation | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
Supports sparsity | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
Sparse auto-differentiation | ✅ | ✅ | ✅ | ✅ | ✅ | ❌ |
- Registered: The solver can be installed automatically using Julia's package manager.
- Uses JuMP model definition: The JuMP.dev framework provides a simple grammar for defining optimization cost functions, or models. Some solvers support these models.
- Bound constraints: Solvers can require some function output to be above or below a certain value.
- Equality constraints: Solvers can require some function output to equal to a certain value.
- Non-linear constraints: Functions used in constraints can be some nonlinear function of the variables.
- Robustified cost functions: A scalar, monotonic function,
$\rho : \mathbb{R}^+ \rightarrow \mathbb{R}^+$ can be used to downweight larger errors. - Non-Euclidean variables: Variables can exist on a non-linear manifold in a higher dimensional space, e.g. 3D rotations represented by a 9-element 3x3 matrix.
- Dense auto-differentiation: The solver supports auto-differentiation of a dense Jacobian of the cost function.
- Supports sparsity: The solver can exploit sparsity within the Jacobian to optimize very large, sparse problems.
- Sparse auto-differentiation: The solver supports auto-differentiation of a sparse Jacobian of the cost function.
Different solvers provide different performance on different problems, so any evaluation is subjective. Here, performance is evaluated on unconstrained, unrobustified problems, some small and dense, others larger and sparse. Only solvers able to optimize all problems are included. Performance is evaluated by the time taken to optimize the cost function. This script was used to evaluate the algorithms, on an Apple M1 Pro CPU. Except where timings are omitted, solvers converged to the global optimum.
A nonlinear symbolic problem could for example be to solve