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

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

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