LeastSquaresOptim.jl

Dense and Sparse Least Squares Optimization
Popularity
42 Stars
Updated Last
1 Year Ago
Started In
September 2015

Motivation

This package solves non linear least squares optimization problems. This package is written with large scale problems in mind (in particular for sparse Jacobians).

Simple Syntax

The symple syntax mirrors the `Optim.jl` syntax

```using LeastSquaresOptim
function rosenbrock(x)
[1 - x[1], 100 * (x[2]-x[1]^2)]
end
x0 = zeros(2)
optimize(rosenbrock, x0, Dogleg())
optimize(rosenbrock, x0, LevenbergMarquardt())```

You can also add the options : `x_tol`, `f_tol`, `g_tol`, `iterations`, `Δ` (initial radius), `autodiff` (`:central` to use finite difference method or `:forward` to use ForwardDiff package) as well as `lower` / `upper` arguments to impose boundary constraints.

Choice of Optimizer / Least Square Solver

• You can specify two least squares optimizers, `Dogleg()` and `LevenbergMarquardt()`
• You can specify three least squares solvers (used within the optimizer)
• `LeastSquaresOptim.QR()` or `LeastSquaresOptim.Cholesky()` for dense jacobians

• `LeastSquaresOptim.LSMR()`. A conjugate gradient method (LSMR with diagonal preconditioner). Beyond `Matrix` and `SparseMatrixCSC`, the jacobian can be any type that defines the following interface:

• `mul!(y, A, x, α::Number, β::Number)` updates y to αAx + βy
• `mul!(x, A', y, α::Number, β::Number)` updates x to αA'y + βx
• `colsumabs2!(x, A)` updates x to the sum of squared elements of each column
• `size(A, d)` returns the nominal dimensions along the dth axis in the equivalent matrix representation of A.
• `eltype(A)` returns the element type implicit in the equivalent matrix representation of A.

Similarly, `x` or `f(x)` may be custom types. An example of the interface can be found in the package SparseFactorModels.jl.

Moreover, you can optionally specifying a function `preconditioner!` and a matrix `P` such that `preconditioner!(P, x, J, λ)` updates `P` as a preconditioner for `J'J + λ`. The preconditioner can be any type that supports `A_ldiv_B!(x, P, y)`. By default, the preconditioner is chosen as the diagonal of the matrix `J'J + λ`.

The optimizers and solvers are presented in more depth in the Ceres documentation. For dense jacobians, the default option is `Doglel(QR())`. For sparse jacobians, the default option is `LevenbergMarquardt(LSMR())`

```optimize(rosenbrock, x0, Dogleg(LeastSquaresOptim.QR()))
optimize(rosenbrock, x0, LevenbergMarquardt(LeastSquaresOptim.LSMR()))```

Alternative in-place Syntax

The alternative syntax is useful when specifying in-place functions or the jacobian. Pass `optimize` a `LeastSquaresProblem` object with:

• `x` an initial set of parameters.
• `f!(out, x)` that writes `f(x)` in `out`.
• the option `output_length` to specify the length of the output vector.
• Optionally, `g!` a function such that `g!(out, x)` writes the jacobian at x in `out`. Otherwise, the jacobian will be computed following the `:autodiff` argument.
```using LeastSquaresOptim
function rosenbrock_f!(out, x)
out[1] = 1 - x[1]
out[2] = 100 * (x[2]-x[1]^2)
end
optimize!(LeastSquaresProblem(x = zeros(2), f! = rosenbrock_f!, output_length = 2, autodiff = :central), Dogleg())

# if you want to use gradient
function rosenbrock_g!(J, x)
J[1, 1] = -1
J[1, 2] = 0
J[2, 1] = -200 * x[1]
J[2, 2] = 100
end
optimize!(LeastSquaresProblem(x = zeros(2), f! = rosenbrock_f!, g! = rosenbrock_g!, output_length = 2), Dogleg())```

Related packages

Related:

• MINPACK.jl] solves least squares problem (without boundary constraints)
• Optim.jl solves general optimization problems.
• NLSolve.jl solves non linear equations by least squares minimization.
• LSqfit.jl fits curves (i.e. models of the form y = f(x, β))

References

• Nocedal, Jorge and Stephen Wright An Inexact Levenberg-Marquardt method for Large Sparse Nonlinear Least Squares (1985) The Journal of the Australian Mathematical Society
• Fong, DC. and Michael Saunders. (2011) LSMR: An Iterative Algorithm for Sparse Least-Squares Problems. SIAM Journal on Scientific Computing
• Agarwal, Sameer, Keir Mierle and Others. (2010) Ceres Solver

Installation

To install the package,

```using Pkg