5
$\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$
3
  • 1
    $\begingroup$ You can try smoothening the function in various ways, for example convolution with a kernel (i.e. averaging a weighted neighborhood). $\endgroup$ Oct 20, 2017 at 8:05
  • $\begingroup$ You could try simulated annealing or local search heuristics. $\endgroup$
    – adrianN
    Oct 20, 2017 at 8:48
  • 1
    $\begingroup$ cs.stackexchange.com/q/39546/755 $\endgroup$
    – D.W.
    Oct 20, 2017 at 14:52

1 Answer 1

2
$\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$
1
  • $\begingroup$ Thanks, differential evolution seems to be a great solution for my problem. $\endgroup$ Oct 21, 2017 at 20:26

Your Answer

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

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