Monday, February 2, 2015

How I Learned to Stop Worrying and Love Fminsearch

(I'd intended to write a post on subsets of null sets that are not null sets, but some lovely person has already posted it on Wikipedia!)

My field involves a lot of fitting ODE parameters to experimental data, so, as expected, I have a long and storied relationship with distance minimization algorithms.

Particularly fminsearch, MATLAB's built-in Nelder-Mead simplex direct search function.

If a network executive decided for some reason to make a sitcom based on my life, fminsearch would be the lovable goofball character whose laziness is the basis for many a cheap joke.

"FMINSEARCH!!! Stop watching football and clean up all those Funyun wrappers from off the floor!" I'd scream. To which fminsearch would reply, "I can't see them! They're not contained in my initial simplex!" Oh, fminsearch....

Fminsearch is great for converging exactly to local minima, but suffers in a couple ways, the main problem being its inability to detect global minima outside its starting range. This problem arises because the underlying algorithm is local (operates on a closed subset of parameter space) and deterministic (will return the same best fit every time if options/initial conditions are unchanged). Of course, the easiest fix is then to pair it with a global, nondeterministic fitting algorithm such as MCMC (Markov Chain Monte Carlo methods) or a genetic algorithm. The new hybrid algorithm then at least has a chance of breaking out of local minimum wells. However, fminsearch is much better at converging exactly to local minima, so it's a good idea to run fminsearch at the end, just in case.

A similar issue occurs minimizing over several parameter values. Although it is possible to use fminsearch to optimize several parameters at once, my advisors and I have had more luck fitting one parameter at a time iteratively. Beware! The order in which the parameters are fitted has a huge effect on the outcome. Less sensitive parameters may not change much if they are fitted last, and if two parameters are related by dependence, it can be difficult to fit them separately. I've had more luck implementing MCMC with Latin Hypercube Sampling (LHS).

Lastly, it can be difficult to find a local minimum in which constraints on parameter size are satisfied (for example, if the algorithm keeps assigning a negative value to a parameter that shouldn't be negative). This is again a situation that should be passed to MCMC, because reducing the average step size in parameter space will cause parameter values to stay closer to the initial conditions. Another 'cheating' fix would be to alter your distance function to output absurdly high numbers when a parameter value enters the no-no range---this is probably the best way to go if you want to stick with fminsearch.

These are, at a broad level, the most important things I've learned in my years of practically dating fminsearch. I'm cataloging them here in case someone looking for guidance can be spared a few couple fights with my favorite MATLAB function.

If any readers (ha, ha) want me to post some iterative fminsearch or MCMC code, I would be happy to provide a watered-down version!

No comments:

Post a Comment