# Massively parallel unconstrained minimization; f is a black box

My objective function, f, is complicated and embodies several disparate constraints I want my simulation to optimize simultaneously. So I can't really even assume it's continuous; it is probably close, in that small changes in the parameter space won't produce big shifts in f, but the gradient, etc. will be undefined all over the place. Also I'm interested in solutions that won't require me to derive the gradient, hessian, etc. every time I make a change to the model.

In my corner, I've got a Tesla K20X. I know that any reasonable N-dimensional grid around the region of likely minima will contain numerous cells that will be nowhere close to optimal. That is, the error of most combinations of the N free parameters will be essentially infinite.

So far I've just been using a standard unconstrained search function (Matlab's fminsearch) on the CPU from numerous different starting points. This takes too long, and I'm worried about local minima (which will always be a concern, but perhaps less so with a better approach). Aside from just implementing that on the GPU (each thread doing its own fminsearch, which seems wasteful), I've thought of a kind of divide-and-conquer approach--evaluate the model at a relatively coarse N-dimensional grid of points in parameter space, throw out those cells with the most error, refine the grid, re-evaluate keeping the total number of evaluations about the same, and keep iterating until the error falls below threshold/won't shrink any more. What else is there? My searching has mainly come up with algorithms that expect you to do some math on the equations, but for the models I eventually plan to run (input-driven dynamical systems with dozens of state variables) this looks to be infeasible.

• "throw out those cells with the most error, refine the grid" -- didn't you just say that this strategy is not effective for your $f$? If your target function is as ugly as you describe, check whether any algorithm can be better than plain random search; are there any signals? If not, starting $p$ independent searches on $p$ processors seems pretty much like the best you can do to me. – Raphael Aug 15 '14 at 21:54
• @Raphael There are large convex regions of parameter space where no combinations will work. A relatively coarse search might be able to identify and eliminate those. I'm thinking of a two-stage approach that combines an initial 'grid' search with p independent searches on the best results from the grid stage. But I'm not trained in this area so I thought I'd see what experts recommend. I'm sure I'm not the first person with ugly f! – Matt Phillips Aug 15 '14 at 23:01
• The issue I see is, won't "any reasonable N-dimensional grid around the region of likely minima will contain numerous cells that will be nowhere close to optimal" mean that you throw out the grid cells with the minima, too? – Raphael Aug 16 '14 at 9:26
• @Raphael No, there are large regions where there is nothing close to a global minimum. Of course, this is partly because I make the grid initially large so as not to miss anything, also because the region of feasible parameter values won't be a nice compact N-rectangle in any case. – Matt Phillips Aug 16 '14 at 17:39