MATLAB Central Newsreader - function with multiple local minima?

function with multiple local minima?

David Doria — Mon, 24 Mar 2008 00:52:01 -0400

I have a function that looks like this:
http://rpi.edu/~doriad/view1.jpg

The function is non analytic, so I have to use something
like the steepest descent method with numerical gradients to
find the minimum. However, if my starting point is on the
left of the tall peak, the min I find is on the left side
(clearly) and if I choose the starting point to be on the
right side I find the low point on the right. Clearly in
this case I could just do both and take the smaller one, but
if I'm not sure about the location of the tall peak to start
with, I can't simply choose a starting point on either side.
Is there a way to find the actual lowest point consistently?

Thanks,

David

Re: function with multiple local minima?

John D'Errico — Mon, 24 Mar 2008 03:17:02 -0400

"David Doria" <daviddoria@gmail.com> wrote in message
<fs6tvh$4bq$1@fred.mathworks.com>...
> I have a function that looks like this:
> http://rpi.edu/~doriad/view1.jpg
>
>
> The function is non analytic, so I have to use something
> like the steepest descent method with numerical gradients to

Well, you don't HAVE to use steepest descent,
a provably poor method of optimization in
general.

> find the minimum. However, if my starting point is on the
> left of the tall peak, the min I find is on the left side
> (clearly) and if I choose the starting point to be on the
> right side I find the low point on the right. Clearly in
> this case I could just do both and take the smaller one, but
> if I'm not sure about the location of the tall peak to start
> with, I can't simply choose a starting point on either side.
> Is there a way to find the actual lowest point consistently?

No, this is not an easy thing to assure. Global
optimizers exist, but it is a nasty problem.

I talk about the concept of domains of attraction
in my optimization tips and tricks document. Each
local minimizer has a locus of points which are
attracted to a given solution. The locus for any
given attractor may not be a very nice set in
general.

One thing that you can do is to use a multi-start
approach. Generate multiple starting points, then
start the optimizer from each location. Take the
best solution overall. This is the approach that I
employ in my rmsearch utility, if you want
something that is already set up to do this.

http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?
objectId=13733&objectType=FILE

HTH,
John

Re: function with multiple local minima?

David Doria — Mon, 24 Mar 2008 11:19:02 -0400

Thanks John -

I've heard of a method called "simulated annealing". Would
this help in this case? or would it just get out of the
small local mins once I am on the correct side - but not
help get over the "big bump" in the middle?

Any other thoughts?

David

Re: function with multiple local minima?

John D'Errico — Mon, 24 Mar 2008 11:43:01 -0400

"David Doria" <daviddoria@gmail.com> wrote in message
<fs82n6$44f$1@fred.mathworks.com>...
> Thanks John -
>
> I've heard of a method called "simulated annealing". Would
> this help in this case? or would it just get out of the
> small local mins once I am on the correct side - but not
> help get over the "big bump" in the middle?
>
> Any other thoughts?
>
> David

There are several tools in the vein of stochastic
optimization - simulated annealing, genetic
algorithms, particle swarm optimizers, and
randomly multiply started optimizers form
the most popular variations.

The idea is to get over the humps using a
probabilistic methodology of some sort. There
is no assurance that you will converge to the
global optimum. No stochastic optimizer can
assure you of this. They can only increase the
probability that you do succeed.

In the case of stochastic optimizers, think of
them in terms of their physical metaphors.
A genetic algorithm with a larger gene pool
and a long time to converge will be more likely
to give you a good result than the alternative.
Likewise, if you wish to increase the odds of
convergence, a simulated annealing tool with
a slow, long annealing schedule is better than
short and fast. You might even find that a
schedule with "temperature" oscillations, on
a downward trend are useful in the annealing
context. A large particle swarm, covering more
ground, will be more likely to fall into the
basin for the global minimizer than will a
small swarm. And finally, more random starts
will increase the odds of success in a random
multi-start method.

There are also "global" tools out there, though
not in the optimization toolbox. I'd suggest
that they too have their own issues to deal
with.

John