# Numerical Optimization¶

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

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.

## 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¶

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

- global optimization algorithms that can run in parallel
- possibly abandoned

### Controlled Random Search¶

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

- Surrogates.jl: a variety of algorithms and sampling methods.
- SurrogateModelOptim.jl

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