11
$\begingroup$

Given an unknown function $f:\mathbb R^d \to \mathbb R$, we can evaluate its value at any point in its domain, but we don't have its expression. In other words, $f$ is like a black box to us.

What is the name for the problem of finding the minimizer of $f$? What are some methods out there?

What is the name for the problem of finding the solution to the equation $f(x)=0$? What are some methods out there?

In the above two problems, is it a good idea to interpolate or fit to some evaluations of f: $(x_i, f(x_i)), i=1, \dots, n$ using a function $g_\theta$ with known form and parameter $\theta$ to be determined, and then minimize $g_\theta$ or find its root?

Thanks and regards!

$\endgroup$
  • 1
    $\begingroup$ Can you evaluate its gradient at a given point? $\endgroup$ – chaohuang Apr 8 '13 at 0:57
  • $\begingroup$ @chaohuang: There are two cases: you may or may not evaluate its gradient, depending on assumptions. $\endgroup$ – Tim Apr 8 '13 at 0:58
  • $\begingroup$ If gradient is available, the tasks you're asking can be accomplished by gradient-based algorithms. For example, the minimum, or at least a local minimum, can be computed by steepest descent method, and the roots can be found by Newton's method. $\endgroup$ – chaohuang Apr 8 '13 at 1:05
  • $\begingroup$ And if the gradient is unknown, there are metaheuristic methods, which are also called derivative-free or black-box methods and usually in the form of stochastic optimization. $\endgroup$ – chaohuang Apr 8 '13 at 1:40
  • 2
    $\begingroup$ Do you know whether the function is smooth (even if you can't evaluate the gradient)? Do you know whether the function is convex? If it isn't convex, do you know whether or not it's at least Lipschitz continuous? If the function is completely general, then this is a hopeless problem. $\endgroup$ – Brian Borchers Apr 8 '13 at 2:24
13
$\begingroup$

The methods you are looking for -- i.e., that only use function evaluations but not derivatives -- are called derivative free optimization methods. There is a large body of literature on them, and you can find a chapter on such methods in most books on optimization. Typical approaches include

  • Approximating the gradient by finite differences if one can reasonably expect the function to be smooth and, possibly, convex;
  • Monte Carlo methods such as Simulated Annealing;
  • Genetic Algorithms.
$\endgroup$
  • 1
    $\begingroup$ Can I just add "Surrogate Modelling" to that list? They are very applicable for black-box optimization, in particular if the function is costly to evaluate. $\endgroup$ – OscarB Apr 8 '13 at 8:13
  • $\begingroup$ Yes, you can :-) Certainly a great addition. $\endgroup$ – Wolfgang Bangerth Apr 9 '13 at 2:41
  • $\begingroup$ One could also use the Nelder-Mead method if good estimates of the optima are known. $\endgroup$ – J. M. May 19 '13 at 14:56
  • $\begingroup$ Yes, you could use Nelder-Mead, but it's a terrible algorithm compared to most every other one. $\endgroup$ – Wolfgang Bangerth May 20 '13 at 3:19
  • 1
    $\begingroup$ @WolfgangBangerth: Your comment on Nelder-Mead is valid only in dimension d>2. In two dimensions, it is on many problems an excellent and very hard to beat method. $\endgroup$ – Arnold Neumaier Sep 23 '13 at 15:49
2
$\begingroup$

I think you should start with: GECCO Workshop on Real-Parameter Black-Box Optimization Benchmarking (BBOB 2016) http://numbbo.github.io/workshops/index.html

You will find many different algorithms that have been used in previous competitions, and that have been compared on a common basis. If you start elsewhere, you will soon drown in the hundreds of papers that claim their methods and algorithms perform better than others with little actual evidence for those claims.

Until recently, it was, to be frank, a disgraceful state of affairs and all power to INRIA, GECCO and many others for the effort they have made in establishing a framework for rational comparisons.

$\endgroup$
-1
$\begingroup$

I'd just add that one of the keys here is being able to scale optimization method on multicore CPUs. If you can perform several function evaluations simultaneously, it gives you a speedup equal to a number of cores involved. Compare this to just using slightly more accurate response model, which makes you 10% more efficient or so.

I'd recommend to look at this code, it can be useful for people having access to many cores. A mathematics behind it is described in this paper.

$\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.