Skip to content

Numerical Optimization

Choosing Algorithms

Links in 2024 discourse thread

Optimization.jl (1.11)

Common interface for a large collection of algorithms. Makes it easy to try alternatives.

NLopt (1.2)

Objective function requires gradient as input, even if it is not used. If gradient is not provided, NLopt returns FORCED_STOP without error message.

Errors in Objective Function

When objective function errors, return value is STOPVAL_REACHED and fVal=0.0.

One way of diagnosing such errors: print the guess to stdout at the start of each iteration. Then the objective function can be run again from the REPL with the guesses that cause the crash.

An alternative (suggested by Kristoffer Carlsson): wrap the entire objective function in try/catch. Report the error in the catch and then rethrow it.

function fmin(x)    
    dev = try
        _fmin(x);
    catch e
        bt = catch_backtrace()
        showerror(stdout, e, bt)
        rethrow(e)
    end

    return dev
end

Noisy objectives

Useful discourse threads: here

SPSA:

  • according to the author: specifically made for simulation type problems
  • basic idea seems to approximate derivatives, but instead of perturbing each parameter one-by-one (expensive), all are perturbed in the same step.
  • extremely easy to implement
  • can vary the distribution of step sizes (main algorithm uses step sizes 1 or 2 times a c( k ) ).

COBYLA

  • implemented in NLopt COBYLA
  • uses a linear approximation of the function

Subplex

  • implemented in NLopt Sbplx
  • similar to Nelder-Mead, but claims to be more robust

Bayesian optimization

Global algorithms

QuadDIRECT

  • combines ideas of DIRECT with local search
  • points from local search are used to form boxes for the global search

NODAL

  • global optimization algorithms that can run in parallel
  • possibly abandoned
  • implemented as NLopt CRS
  • starts from a random population of points (default size 10(n+1))
  • user can control the size of the initial population, but there are no warm starts.
  • then evolves these using heuristic rules. Described as "randomized Nelder-Mead".

MLSL

  • implemented as NLopt MLSL
  • basic idea: multistart a local solver, avoiding resolving points that are close to each other

TikTak

Arnoud, Antoine, Fatih Guvenen, and Tatjana Kleineberg. 2019. “Benchmarking Global Optimizers.” Working Paper 26340. National Bureau of Economic Research. https://doi.org/10.3386/w26340.

A multistart algorithm that generates new starting points as convex combinations of the current best point and Sobol points.

BlackBoxOptim

  • implements SPSA
  • currently little documentation (2020-May)
  • There is an example of distributed parallel optimization. Not clear whether multi-threaded works as well.
  • Not clear whether / how optimization history can be saved.

Surrogate Optimization

Basic idea:

  • Sample a small number of points. Evaluate the objective.
  • Fit a surrogate function to those points.
  • Optimize this function, which is cheap to evaluate, using an algorithm that
  • explores the global parameter space
  • downweights points that are far from points where the true objective has been evaluated
  • Add the optimum of the surrogate to the list of evaluated points (using the true function value).
  • Update the surrogate model based on the new point.
  • Repeat.

Packages:

Drawback: There is no good way of running the surrogate optimization in parallel (unlike Matlab).