I'm looking at a global minimisation problem on the $n$-sphere ($n$ of the order 10--50) but with a complete swine of an objective --- it is (effectively) a black box; it is piecewise smooth but with discontinuities and (this is the kicker) the minimum seems to occur at (one side of) a discontinuity. My best results so-far are with a simulated annealing (scipy.optimize.anneal, hacked so that updates stay on the sphere) which seems to give me reasonable results with 100,000 evaluations on an $n=10$ problem taking about 2 CPU-hours. Is there a better way?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ It seems to call for investigation of the discontinuity's structure. Perhaps the discontinuity itself is rather smooth and (if your surmise about the location of the minimum is correct) leads to searching in a reduced dimension. $\endgroup$– hardmath ♦Aug 23, 2013 at 13:53
-
$\begingroup$ Thanks hardmath, I had been thinking in this direction too, but my objective is difficult to analyse and the discontinuity structure is probably only available numerically -- I had hoped that there might have been some work in this area but I've failed to find any. $\endgroup$– n00bAug 25, 2013 at 11:07
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Global optimization algorithms are almost always inefficient. This is true for all variants (simulated annealing, genetic, particle swarm, you name it). You can use them, but it's often worth finding out some properties of your objective function. For example, if you can find out where the objective function is discontinuous, then you can rephrase the optimization problem as one where you try to find the optimum on each patch of smooth objective function plus constraints to delineate the smooth region, and then take the optimum over the best value from each of the patches. On each patch you use a local optimizer, making for a much faster method.
answered Aug 24, 2013 at 4:21
$\begingroup$
$\endgroup$
I suggest you try a Genetic Algorithm.
Genetic Algorithms are robust against discontinuities in the objective function and converge to the global optimum in propability.
They might be unfeasible if the evaluation of the objective is expensive. But you have a lot of parameters for tuning.
Have a look at this post for implementations in python.
$\begingroup$
$\endgroup$
Consider exploring your design space a bit more methodically. Polynomial chaos expansion is good for this; you can find it built into the very impressive DAKOTA package. Essentially you intelligently sample the design space and reconstruct it using an orthogonal polynomial expansion. It works very well in areas with discontinuities. You may be able to get away with using a 2nd order polynomial mapping, so you'd have 3^N samples (59049 for your N=10 case), sample that, and use the minima you identify as an initial guess for a local search method (e.g. gradient-based Newton-Raphson.)
Alternatively, try using the results of the global simulated annealing approach you're already using; then stop it after say, 10,000 results, and use the best case (or best 10) as the initial guess for scipy's local optimization routines.
