I want to run local optimizers on a multi-dimensional function f with several local minimums.

To make sure to trap into the real global optimum, I am running first an initial sampling (e.g. randomly) over a wider space, and get e.g. n combinations of (fi, Xi). If I now rank the function values, then it is not given that e.g. the lowest and 2nd lowest fi belong to the same local minimum, so I want to run a kind of cluster analysis upfront to the local minimizations. However, I wonder which algorithms work efficient, would e.g. a k-mean cluster analysis fit, and how to apply it?

Usually the number of local minimums is not known, but we can assume that there are usually only 1 to 3, not more. The functions have typically 2 to 7 dimensions, and the initial random sample has e.g. n=50 to 500 points.

One difficulty, I already observed is that if the initial sampling does not cover a really wide space, then it is likely that e.g. even the true global minimum is not hit often, compared to a local optimum in the center of the sampling space.

One brute-force method would be to pick a good sample (fo,Xo), and to pick also 6 other samples "nearby", and to create a quadratic model. If the Hessian has good properties, then we have a good candidate. Then we might check for another "good" sample regarding f, but with (X-Xo) large enough, but I wonder if there are existing "packaged" methods?

I wonder, if we first filter out all fi>f(too large), and simply run k-mean, do we filter out too many local optimum clusters, so that the over-all optimization would not be better then most local optimization methods?


You could use simulated annealing or generalised simulated annealing on this, it would work very well. Since simulated annealing is stochastic, it can handle local minima.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.