4
$\begingroup$

I have a bounded non-convex function in 10-dimensional space. The function is quasi-smooth, you can imagine a histogram, here is an illustration, it just shows the idea and not related to my particular function:

enter image description here

The function value is obtained by time consuming simulation (it takes about 10 seconds). Obviously if I want compute gradients, I need to approximate them by difference quotients. If you need more details about the function, I might be able to say more.

I have read the article of L.M. Rios and N.V. Sahinidis, Derivative-free optimization: A review of algorithms and comparison of software implementations

So I've tried all of TOMLAB solvers, proposed in article and also MCS method, also mentioned in the article as one of the best. But neither of them could not overperform simple Brent method accompanied by hand picked initial guess (well, I hardly believe I can produce such great guesses).

I've also heard about surrogate modeling, is it worth trying?

So which other global optimization methods should I consider?

$\endgroup$
  • $\begingroup$ Brent's method is essentially a 1-D line search (for root finding). What are you using to generate search directions for your line search if you have a 10-dimensional search space? $\endgroup$ – Geoff Oxberry Oct 10 '14 at 23:45
  • $\begingroup$ @GeoffOxberry, more accurately speaking, I use Powell's and inside it - Brent's method alongside of each coordinate $\endgroup$ – JohnnyBGoode Oct 11 '14 at 9:48
2
$\begingroup$

As the review article points out, there's no one best derivative-free optimizer for all problems, much like there's no one best nonlinear solver for finding roots of algebraic equations, or one best linear solver for solving linear equations, etc. Also, like linear solvers and nonlinear solvers, a certain amount of experimentation is required if you want a highly performant solution.

Along that line of argument, surrogate modeling is something that's worth trying. You might first try the algorithms in NLOPT, written by Steven G. Johnson at MIT, which contains a few derivative-free algorithms that use surrogate models (polynomial interpolants, basically). It sounds like you're using something similar to PRAXIS right now, so you could also try COBYLA, BOBYQA, and NEWUOA, and see how they work.

$\endgroup$
0
$\begingroup$

You can try fitting your data by a 10-dimensional B-spline hypersurface by penalized least-squares fitting as suggested in this article:

N. Whitehorn, J. van Santen, S. Lafebre, Computer Physics Communications (2013) 184: 9. doi:10.1016/j.cpc.2013.04.008

This yields a smooth function that is very cheap to evaluate and provides you an inexpensive gradient. This could bring you close to your global minimum where a local search shouldn't be a problem.

$\endgroup$

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.