1
$\begingroup$

I'm writing an optimization algorithm thats supposed to find the maximum and minimum value of any given function. Whats the fastest numerical approuch to do so?

$\endgroup$
  • 1
    $\begingroup$ Functions in one real variable? Continuous? Is it known that there is only one local maximum in an interval? $\endgroup$ – Hagen von Eitzen Apr 24 '13 at 12:18
  • $\begingroup$ yes continous functions with one real variable and one local maximum $\endgroup$ – Yui Apr 24 '13 at 12:22
  • $\begingroup$ I think you must specify the question. There are many fast algorithms for special classes of functions, but there is no algorithm that can handle "any given function". $\endgroup$ – Mårten W Apr 24 '13 at 12:36
  • $\begingroup$ Are there other restrictions? Saw-tooth functions with domain $ $\endgroup$ – Jay Apr 24 '13 at 12:39
  • $\begingroup$ I have a function f(x). It is continous and differentiable. I don't know how it looks but I can determine y for every x. $\endgroup$ – Yui Apr 24 '13 at 12:51
1
$\begingroup$

I don't know how this method is called, so IÄll describe it in full:

If $f\colon[a,b]\to\mathbb R$ has only one local maximum in $[a,b]$ one can use a search basesd on the golden ratio $\phi=\frac{\sqrt 5-1}{2}$. Given $x_0<x_1<x_2<x_3$ with $x_2-x_0=x_3-x_1=\phi(x_3-x_1)$ and the unique local maximum in $[x_0,x_3]$, do as follows: If $f(x_1)\ge f(x_2)$ replace $(x_0,x_1,x_2,x_3)$ with $(x_0, x_0+x_2-x_1, x_1, x_2)$, otherwise with $(x_1, x_2, x_1+x_3-x_2,x_3)$ and repeat.

Care must be taken if due to rounding errors the correct order of the $x_i$ might be destroyed.

$\endgroup$
  • $\begingroup$ I found a technique last year from the 1970s called Brents Method which uses parabolic interpolation with safeguarding by the golden search. Perhaps that is what you are thinking of? $\endgroup$ – Daryl Apr 24 '13 at 20:57
0
$\begingroup$

It is very helpful to have an estimate for the number and distribution of local maxima, because most methods can only find a local maximum. Without such knowledge, I would initially partition the interval into a large number of subintervals, and maximize over each one. Within each subinterval, you could use @Hagen von Eitzen's algorithm, or the bisection method, or Newton's method to find a zero of $f'(x)$. After maximizing over each interval, take the maximum of the maxima and (hopefully) there you go. You can't be sure you've got the maximum, because if one of your intervals had two local maxima, you might have found the smaller one.

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