![cc](pix/cc-attrib-nc.png)
Licensed under the 
[Creative Commons attribution-noncommercial license](http://creativecommons.org/licenses/by-nc/3.0/).
Please share \& remix noncommercially, mentioning its origin.

# Optimization

## no free lunch

- [Wikipedia](https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization)
- > "any two algorithms are equivalent when their performance is averaged across all possible problems."
- a "good" optimization method is one that works on the kinds of problems you have

## implementations

**the devil is in the details**; different implementations *of the same algorithm* may differ ...

- performance
- robustness
- interface (arguments, return values)
- controls
- convergence testing

# Local optimization

## derivative-based optimization

- uses first (gradient/direction) and second (Hessian/curvature) information
- assumes smooth objective function
- R's optimization functions don't need user-supplied gradient functions - but will use **finite differences** instead

## derivative-based methods

- see @Press+1994 (or later editions)
- *gradient descent*: widely used in machine learning
    - easy, scalable
	- but can almost certainly do better!
- *Newton's method*: simple but not actually practical (unstable, expensive)	
- Levenberg-Marquardt: specifically for least squares problems	
- conjugate gradients (CG), quasi-Newton (`BFGS`, `L-BFGS-B`)
    - various fancier methods

## derivative-free methods

- for non-smooth surfaces, or when derivatives are expensive
- Nelder-Mead
- BOBYQA, COBYLA, NEWUOA (Powell) ...

# Stochastic/global optimization

## stochastic optimization

- for noisy surfaces, multi-modal problems ...
- see [CRAN optimization task view section](https://cran.r-project.org/web/views/Optimization.html#global-and-stochastic-optimization)
- classic method is *simulated annealing* (`method="SANN"`)
- **slow** and needs lots of tuning

## simulated annealing

- local search with decreasing noise
- local "jumps" according to a **candidate distribution**
- accept with probability $\exp(-\Delta G/T)$
    - high temperature: random search
	- low temperature: local ratchet
- tuning: candidate distribution, cooling schedule
- very general (don't need continuous parameters)
- compare Metropolis-Hastings in Markov chain Monte Carlo

## genetic algorithms

- population-based
- biological analogies
- reproduction, selection, mutation, recombination ("crossover")
- flexible
- parameters often coded as bit strings
- `genoud` package?

## differential evolution

- population-based
- derivative-free
- continuous parameters
- `DEoptim` package

---

![](pix/ugly2.png)

