13
$\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!

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Can you evaluate its gradient at a given point? $\endgroup$
    – chaohuang
    Apr 8, 2013 at 0:57
  • $\begingroup$ @chaohuang: There are two cases: you may or may not evaluate its gradient, depending on assumptions. $\endgroup$
    – Tim
    Apr 8, 2013 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, 2013 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, 2013 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, 2013 at 2:24

3 Answers 3

Reset to default
14
$\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.
Improve this answer
$\endgroup$
6
  • 2
    $\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, 2013 at 8:13
  • $\begingroup$ Yes, you can :-) Certainly a great addition. $\endgroup$
    – Wolfgang Bangerth
    Apr 9, 2013 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, 2013 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, 2013 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, 2013 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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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