4
$\begingroup$

I have a certain function that calculates numerically, for every $x \in [0,10]$, a value $y\geq 0$. I want to find an approximate minimum point of that function. A possible solution is to calculate $y$ for e.g. 10000 values of $x$ in the range $[0,3]$ and return the $x$ for which $y$ is smallest. I am looking for fastest solutions.

I know that the general shape of the function is like the following plot: plot of function

I.e, it is like a function with a single minimum point, but with some added random noise of bounded size. Without the noise, I could easily find the minimum point using gradient methods, but with noise gradients seem useless. What other search algorithm can I use here?

NOTE: Naturally the approximation quality can depend on the noise size, for example, in the above plot, any answer between $\approx 0.3$ and $\approx 0.7$ would be considered good enough.

$\endgroup$
  • 1
    $\begingroup$ You can try smoothening the function in various ways, for example convolution with a kernel (i.e. averaging a weighted neighborhood). $\endgroup$ – Yuval Filmus Oct 20 '17 at 8:05
  • $\begingroup$ You could try simulated annealing or local search heuristics. $\endgroup$ – adrianN Oct 20 '17 at 8:48
  • 1
    $\begingroup$ cs.stackexchange.com/q/39546/755 $\endgroup$ – D.W. Oct 20 '17 at 14:52
1
$\begingroup$

Some things you could explore are metaheuristics. The following methods don't make assumptions about the function to be optimized, and some are relatively simple to understand and implement.

Some of these mantain a population of possible solutions, recombining them to create new possible solutions and keeping the best ones.

  • Differential evolution
  • Particle Swarm
  • Evolutionary algorithms

There are a lot more, with a lot of published variations.

It is my understanding that they are very capable, you can expect the error to be much smaller to the error margin you mentioned and the acceptable error can be used as a parameter for the halting condition of the algorithm. If the target function is computationally cheap to evaluate these methods should be very competitive.

In particular differential evolution could be a place to start exploring. You can use an already written implementation on scipy's optimize.

There are other approaches, some of which make assumptions about the function to be optimized. You can see some examples on Wikipedia (Computational optimization techniques section).

$\endgroup$
  • $\begingroup$ Thanks, differential evolution seems to be a great solution for my problem. $\endgroup$ – Erel Segal-Halevi Oct 21 '17 at 20:26

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.