[ANN] IterativeNelderMead.jl - A Robust Nelder-Mead Solver

Package Announcements
1

IterativeNelderMead.jl

This flavor of Nelder-Mead is based on the Matlab algorithm available here with additional tweaks. Some details:

  1. The solver performs multiple iterations of full-dimensional simplex calls followed by a series of two-dimensional simplex calls, providing local improvements by subspaces, updating both the nominal solution and full-dimensional simplex.

  2. Parameter bounds are implemented by penalizing the objective function with a linear function. If finite parameter bounds are provided, the internal parameter exploration space is linearly transformed to [0, 1].

  3. An interface for passing and using bounded parameters is provided in a simple API. Alternatively, usual vectors can be used instead.

  4. Convergence for the objective must be met 3 (configurable) times in a row for convergence (for each iteration/subspace).

More applications will lead to a more robust solver. More tests and tips are encouraged!

Last bit - A similar method may be to wrap the Nelder-Mead solver from Optim.jl with the steps described in 1 above. I have not done any comparisons with Optim.jl and welcome any insight from there as well. The goal is for this solver to be eventually callable through the SciML Optimization interface.

Documentation and examples

Repo

16 Likes
2

Do you think IterativeNelderMead.jl could work without DataFrames? It’s quite a heavy dependency …

julia> @time_imports import IterativeNelderMead
      0.3 ms    ┌ IteratorInterfaceExtensions
    233.1 ms  ┌ TableTraits
      1.1 ms  ┌ Compat
     61.3 ms  ┌ DataStructures
      0.2 ms  ┌ DataValueInterfaces
      2.7 ms  ┌ InvertedIndices
      0.2 ms  ┌ Reexport
      0.8 ms    ┌ DataAPI
     13.2 ms  ┌ Tables
     15.0 ms  ┌ PooledArrays
     31.8 ms    ┌ Crayons
      0.5 ms    ┌ SortingAlgorithms
      0.6 ms      ┌ Formatting
     95.2 ms    ┌ PrettyTables
      7.4 ms    ┌ Missings
    928.4 ms  ┌ DataFrames
   1271.7 ms  IterativeNelderMead
6 Likes
3

Bored, so I briefly took a look. Would be easy to drop the DataFrames.jl dependency in favor of more general Tables.jl compatibility. Looks like the only place it is used is the to_df() method which builds a table of parameter names, values, and bounds.

Would encourage OP to put more thought into

mutable struct Parameter
    name::Union{String, Nothing}
    value::Float64
    lower_bound::Float64
    upper_bound::Float64
    vary::Bool
    latex_str::Union{String, Nothing}
end

which leads me to believe there is a lot left on the table here. For one, I believe this makes it difficult or impossible to compose this package with AD packages (correct me if I am wrong).

5 Likes
4

That’s right - there’s currently no support with any AD packages. Should a derivative-free solver necessarily support AD?

The parameters API is not necessary, although I find using the parameters API directly is easier when using an appreciable number of parameters (say > 5) so one doesn’t need to remember which index corresponds to which parameter (see example 2 on the docs). However the function to_df() is never used during a solve and may be dropped in a future release along with DataFrames.jl. However however, the parameters API is still used internally.

5

What method/output would you recommend instead utilizing Tables.jl? I think this also raises a bigger question - do I leave such functionality to the user to create, leaving the DataFrames.jl dependency on them? If such functionality is appropriate for my package, is it really appropriate to include DataFrames.jl as a dependency for a single data type?

In my case, the Parameters related code could be an independent package and the IterativeNelderMead package could ultimately do without it, anyway.

6

This question was something I had to deal often in the context of plotting. Makie is absolutely great, but there is also absolutely no way I would let my package have it as a dependency. So I made two packages:

module QuantumClifford
struct Stabilizer end
end

module QuantumCliffordPlots
import QuantumClifford
import Makie
function Makie.some_plotting_function(s::QuantumClifford.Stabilizer) end
end

A two package solution seems like a reasonable way to structure this type of requirements in Julia.

2 Likes
7

Ah I see, thank you. That makes sense to minimize code loading time in general. I think the best plan for IterativeNelderMead.jl is to pull out CurveFitParameters.jl (or something like that) and rework the internals of IterativeNelderMead.jl to not depend on Parameters objects. I will keep this all in mind for a future release, but let me know if you have any other suggestions.

8

If you wanted to be more integrated with the Julia ecosystem you could also adopt the Optim.jl interface, IIRC it’s not super complicated, you need to declare you optimizer as a ZerothOrderOptimizer (and add a corresponding State with a few fields), and you need to define a initial_state and a update_state! method that will be called at the start and during the optimisation loop. There’s also optional methods like assess_convergence if you want a custom convergence.

It’s a bit of work but then you get a lot of things for free and it avoids a lot of code duplication (you don’t need to write the main loop, the options handling, etc). Plus users get a unified interface they are familiar with.

See e.g. Optim’s N-M or an old attempt at CMAES implementation.

9

If you want to return a Table, there’s no need to depend on any package at all. There are two table types in Base Julia already: rowtable that is a vector of namedtuples, and columntable that is a namedtuple of vectors.
Then, users would choose table types they prefer, potentially converting the result returned from your package. I guess lots of usages won’t involve DataFrames at all, working with a plain vector of namedtuples is pretty convenient.

4 Likes