Prev: How to append to plot, or continuously update plot? plot3d?
Next: How to use matlab generated dll in .NET
From: Jorge Lagos on 8 Apr 2010 09:01
Hi all! I am facing a global optimization problem for which I have tried the new function "globalsearch" (along with fmincon as the local solver) in R2010a, obtaining results that agree with what I expected. However, I am in the need to justify the mathematical rigorousness of the global maxima found by this function. After reading the documentation for this function, it seems that the algorithm behind its workings is based on heuristics, and it is not clear to me if this means that there are no guarantees about the results it produces.

In particular, I would like to know if:

1. There is any guarantee that this function will find an approximation the global maxima to a certain (or given?) degree of accuracy.

2. In case the answer to question #1 is negative, can it be said that it is because globalsearch (along with fmincon) is a stochastic global optimizer? or is it deterministic but based on heuristics? In short, what prevents it to provide the guarantees?.

3. What other alternative approaches to (nonlinear, continuous) global optimization with guaranteed convergence to a certain precision are available?

Thanks in advance for any help regarding this doubts!

Regards,

Jorge.
From: James Allison on 8 Apr 2010 12:28
Unless your objective/constraint functions have special properties, no
guarantee about finding a global optimum can be made (regardless of your
computing platform). Algorithms such as globalsearch can increase the
propability of finding the global optimum vs. a local search algorithm,
but cannot guarantee it. A convex underestimator approach can guarantee
a global optimum, but applies only to functional programs (i.e., NLPs
with factorable objective and constraint functions); it is not as
general as the functions in the Global Optimization Toolbox.

-James

Jorge Lagos wrote:
> Hi all! I am facing a global optimization problem for which I have tried
> the new function "globalsearch" (along with fmincon as the local solver)
> in R2010a, obtaining results that agree with what I expected. However, I
> am in the need to justify the mathematical rigorousness of the global
> maxima found by this function. After reading the documentation for this
> function, it seems that the algorithm behind its workings is based on
> heuristics, and it is not clear to me if this means that there are no
> guarantees about the results it produces.
>
> In particular, I would like to know if:
>
> 1. There is any guarantee that this function will find an approximation
> the global maxima to a certain (or given?) degree of accuracy.
>
> 2. In case the answer to question #1 is negative, can it be said that it
> is because globalsearch (along with fmincon) is a stochastic global
> optimizer? or is it deterministic but based on heuristics? In short,
> what prevents it to provide the guarantees?.
>
> 3. What other alternative approaches to (nonlinear, continuous) global
> optimization with guaranteed convergence to a certain precision are
> available?
>
> Thanks in advance for any help regarding this doubts!
>
> Regards,
>
> Jorge.
From: Jorge Lagos on 19 Apr 2010 12:20
Thanks so much for your reply, James.

In fact, since I posted my message I have run across some instances of my problem for which Globalsearch also fails to converge to the global maximum. I have done some further research on the start-of-the-art in global optimization, and it seems that currently there is no software capable of guaranteeing convergence to a predefined precision. Thanks anyway for the clarification.

Regards,

Jorge.

James Allison <james.allison(a)mathworks.com> wrote in message <hpl081$7n6$1(a)fred.mathworks.com>...
> Unless your objective/constraint functions have special properties, no
> guarantee about finding a global optimum can be made (regardless of your
> computing platform). Algorithms such as globalsearch can increase the
> propability of finding the global optimum vs. a local search algorithm,
> but cannot guarantee it. A convex underestimator approach can guarantee
> a global optimum, but applies only to functional programs (i.e., NLPs
> with factorable objective and constraint functions); it is not as
> general as the functions in the Global Optimization Toolbox.
>
> -James
>
> Jorge Lagos wrote:
> > Hi all! I am facing a global optimization problem for which I have tried
> > the new function "globalsearch" (along with fmincon as the local solver)
> > in R2010a, obtaining results that agree with what I expected. However, I
> > am in the need to justify the mathematical rigorousness of the global
> > maxima found by this function. After reading the documentation for this
> > function, it seems that the algorithm behind its workings is based on
> > heuristics, and it is not clear to me if this means that there are no
> > guarantees about the results it produces.
> >
> > In particular, I would like to know if:
> >
> > 1. There is any guarantee that this function will find an approximation
> > the global maxima to a certain (or given?) degree of accuracy.
> >
> > 2. In case the answer to question #1 is negative, can it be said that it
> > is because globalsearch (along with fmincon) is a stochastic global
> > optimizer? or is it deterministic but based on heuristics? In short,
> > what prevents it to provide the guarantees?.
> >
> > 3. What other alternative approaches to (nonlinear, continuous) global
> > optimization with guaranteed convergence to a certain precision are
> > available?
> >
> > Thanks in advance for any help regarding this doubts!
> >
> > Regards,
> >
> > Jorge.
 | 
Pages: 1
Prev: How to append to plot, or continuously update plot? plot3d?
Next: How to use matlab generated dll in .NET