# Looking for numerical methods for finding local maxima and minima of a function

In derivative,

If $f'(x)$ is rising at $f'(x)$ = 0, there's a local minima in $f(x)$.

If $f'(x)$ is falling at $f'(x)$ = 0, there's a local maxima in $f(x)$.

If $f''(x)$ is rising at $f''(x)$ = 0, there's a local minima in $f'(x)$ and $f(x)$ is falling.

If $f''(x)$ is falling at $f''(x)$ = 0, there's a local maxima in $f'(x)$ and $f(x)$ is rising.

We can graph the function out to see whether it's falling or rising, A simple check at the position very close the root may suffice to see whether we got a positive or negative number, and conclude whether a function is falling or rising. Derivative can be used to find roots, maxima, minima, rising slope, and falling slope.

In numerical method, (or more precisely, for a computer program) we can use Bisection method, Newton-Raphson method to approximate roots of a function.

Now, what about other features such as local maxima, minima and whether the function is rising or falling? I am looking for an algorithm for approximating these critical points. What are some of the numerical method names I should be looking for?

-
Perhaps I'm missing something, but why can't you just use some of the algorithms you mentioned before to approximate roots of the first and second derivative and use the propositions you mentioned in the beginning of the question? –  Tilo Wiklund Aug 21 '11 at 9:56
@Tilo: then that implies I need a programming algorithm that can automatically derive any given formula. Also, I just want to know whether any critical point approximating algorithm for a function exists in numerical method or not. –  Karl Aug 21 '11 at 10:05
most are variations on the newton-rapson alg. A more robust variant is levenberg-marquardt (but more complicated). A popular one is actually the simplex method or nelder-mead method (simplex algorithm for non-linear programming! the more well known 'simplex method' is for linear programming - but that's not what you want here). –  Peter Sheldrick Aug 21 '11 at 10:17
There are ways to approximate the derivative though, which shouldn't be too big a problem since you are going for approximations anyway. (One can also go for things like automatic differentiation, but making this feasible presupposes you work in a reasonably flexible language.) –  Tilo Wiklund Aug 21 '11 at 23:17

## 2 Answers

For univariate functions you can use golden section search to find the extrema without knowing the derivatives of the function. But beware of its requirements to the function (namely to be unimodal), but maybe you can first narrow the search space to a unimodal interval.

-
Golden is what you should be happy with if you can't assume smoothness in the function you're optimizing. If the function is smooth somewhat, you can manage to do a parabolic fit along with the golden section search to speed things up a bit; as a matter of fact, Richard Brent wrote a very cute algorithm incorporating these ideas, which he discusses in his Algorithms for Minimization Without Derivatives. –  Guess who it is. Aug 21 '11 at 11:09

The topic you are asking for is very broad. Therefore this should give you a good start into the main algorithms employed, it depends a lot on what kind of functions are optimized and how they behave, a very good behaving case is for example where $f$ is differentiable, then the methods are quite efficient.

-