|
|
| Author |
Message |
David A. Heiser
science forum beginner
Joined: 18 Sep 2005
Posts: 5
|
 Posted: Fri Jun 30, 2006 2:40 am Post subject:
Re: grid search for global optimum, is there a way to decide stepsize?
|
|
|
"Ray Koopman" <koopman@sfu.ca> wrote in message
news:1151560341.486888.27870@y41g2000cwy.googlegroups.com...
| Quote: | David A. Heiser wrote:
"gino" <loseminds@hotmail.com> wrote in message
news:e7ncrr$h1v$1@news.Stanford.EDU...
Hi all,
As you might have seen my previous posted questions, I am trying hard
to
search for the global minimum of my 4D function z=f(x, y, u, v).
I have read literature extensively, and found out that there is no
algorithm/solver that is guaranteed to locate the global optimum.
So I decide to go back to the primitive grid search. I've already done
a
0.02 step size 4D grid search. It was about 1 night's running time.
Now I want to ask: given this function is continuous except at a few
singularities(mainly due to log(0) and dividing by sigma=0),
analytically
I may be able to obtain gradient functions and may be able to obtain
the
Liptisz constant...
May I be able to decide the optimal stepsize that can guarantee to find
the global optimum?
I am thinking of if the optimal stepsize is not too small, and by
adjusting my bounds/search range using domain specific knowledge, I may
be
able to find the global minimum using grid-search, after a few days
waiting time... (Slowness is better than missing the global optimum)...
Thanks a lot!
---------------------------------
Here is the description of the model, which fits data to an MLE log
likelihood function:
The model is of typical loglikelihood function:
f(mu, sigma, a, b)=-0.5*sum_of_squares( (x - mu)/sigma) + log(p1) -
log(p0).
The log(p1) and log(p0) terms are the logs of some probabilities.
Theoretically all the above functions are continuous and well-behaved.
However, when fitting this model to data, due to model error or data
noise,
the numerical results might not be always well-behaved.
Sigma being near 0 is a huge problem, although I've demanded the low
bound
of sigma to be 1e-5.
p1 and p0 can be evaluated to be 0 or negative too. Although
theoretically
a
probability cannot be outside [0, 1], but when fitting it to data, it
can
give negative values and values that are greater than 1, depending on
the
data.
Thus this 4D log likelihood function is hard to maximize using data. I
am
trying many solvers.
As you can see, theoretically, everything is continuous, except
sigma=0,
but
I've set lower bound of sigma to be 1e-5.
I even could not answer your question about "how many local minimums",
because with z=f(x, y, u, v) 4D function, I was unable to
systematically
visualize the sample points at all.
Any thoughts?
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
Where are all the experts on this. [...]
sci.math.num-analysis ?
+++++++++++++++++++++++++++++++++++++ |
Sounds good, worth a try. As you say, the problem is "noise" and "bad
behavior" in the maximum region. I always seem to get these "bad" problems.
David Heiser |
|
| Back to top |
|
 |
gino
science forum beginner
Joined: 01 Feb 2006
Posts: 29
|
| Posted: Fri Jun 30, 2006 3:42 am Post subject:
Re: grid search for global optimum, is there a way to decide stepsize?
|
|
|
"David A. Heiser" <daheiser@gvn.net> wrote in message
news:W4Hog.21$%a5.18451@news.sisna.com...
| Quote: |
"gino" <loseminds@hotmail.com> wrote in message
news:e7ncrr$h1v$1@news.Stanford.EDU...
Hi all,
As you might have seen my previous posted questions, I am trying hard to
search for the global minimum of my 4D function z=f(x, y, u, v).
I have read literature extensively, and found out that there is no
algorithm/solver that is guaranteed to locate the global optimum.
So I decide to go back to the primitive grid search. I've already done a
0.02 step size 4D grid search. It was about 1 night's running time.
Now I want to ask: given this function is continuous except at a few
singularities(mainly due to log(0) and dividing by sigma=0), analytically
I may be able to obtain gradient functions and may be able to obtain the
Liptisz constant...
May I be able to decide the optimal stepsize that can guarantee to find
the global optimum?
I am thinking of if the optimal stepsize is not too small, and by
adjusting my bounds/search range using domain specific knowledge, I may
be able to find the global minimum using grid-search, after a few days
waiting time... (Slowness is better than missing the global optimum)...
Thanks a lot!
---------------------------------
Here is the description of the model, which fits data to an MLE log
likelihood function:
The model is of typical loglikelihood function:
f(mu, sigma, a, b)=-0.5*sum_of_squares( (x - mu)/sigma) + log(p1) -
log(p0).
The log(p1) and log(p0) terms are the logs of some probabilities.
Theoretically all the above functions are continuous and well-behaved.
However, when fitting this model to data, due to model error or data
noise,
the numerical results might not be always well-behaved.
Sigma being near 0 is a huge problem, although I've demanded the low
bound
of sigma to be 1e-5.
p1 and p0 can be evaluated to be 0 or negative too. Although
theoretically a
probability cannot be outside [0, 1], but when fitting it to data, it can
give negative values and values that are greater than 1, depending on the
data.
Thus this 4D log likelihood function is hard to maximize using data. I am
trying many solvers.
As you can see, theoretically, everything is continuous, except sigma=0,
but
I've set lower bound of sigma to be 1e-5.
I even could not answer your question about "how many local minimums",
because with z=f(x, y, u, v) 4D function, I was unable to systematically
visualize the sample points at all.
Any thoughts?
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
Where are all the experts on this. This issue has been intensely worked on
for at least the last 10 years. There is free software out these that does
what gino is asking for. Why aren't the experts citing all this? I'm not
an expert so I don't have to give advice.
The first choice and the most time consuming (appears to take forever) is
to do a random search among all variables to find the optimum region.
Surely you must have some idea of what the range of parameter space is?
Once you have some knowledge of the region, then there are many good
methods for finding the optimum. You might have to repeat the random in
ever more narrow regions to find a "messy" optimum (if it exists).
David Heiser
|
Hi David,
After these days reading, I believe only Bound and Branch will guarantee a
global optimum, albeit slow. But for a 4-free parameter problem, it is
considered as a small-scale problem. So the computing should be within one
day... |
|
| Back to top |
|
|
optionstraderjeff
science forum beginner
Joined: 30 Jun 2006
Posts: 2
|
| Posted: Fri Jun 30, 2006 12:24 pm Post subject:
Re: grid search for global optimum, is there a way to decide stepsize?
|
|
|
Hi,
Why not try genetic optimization. Genetic algorithms are amazingly
effective when it comes to locating global optima; and, they can be
orders of magnitude faster than other stochastic or brute-force methods
when many parameters (>> 4) must be estimated. Depending on the
precision required, you may want to combine a GA with a localized NR
procedure (something you can do if your function is continuous and
well-behaved).
Jeff
gino wrote:
| Quote: | Hi all,
As you might have seen my previous posted questions, I am trying hard to
search for the global minimum of my 4D function z=f(x, y, u, v).
I have read literature extensively, and found out that there is no
algorithm/solver that is guaranteed to locate the global optimum.
So I decide to go back to the primitive grid search. I've already done a
0.02 step size 4D grid search. It was about 1 night's running time.
Now I want to ask: given this function is continuous except at a few
singularities(mainly due to log(0) and dividing by sigma=0), analytically I
may be able to obtain gradient functions and may be able to obtain the
Liptisz constant...
May I be able to decide the optimal stepsize that can guarantee to find the
global optimum?
I am thinking of if the optimal stepsize is not too small, and by adjusting
my bounds/search range using domain specific knowledge, I may be able to
find the global minimum using grid-search, after a few days waiting time...
(Slowness is better than missing the global optimum)...
Thanks a lot!
---------------------------------
Here is the description of the model, which fits data to an MLE log
likelihood function:
The model is of typical loglikelihood function:
f(mu, sigma, a, b)=-0.5*sum_of_squares( (x - mu)/sigma) + log(p1) - log(p0).
The log(p1) and log(p0) terms are the logs of some probabilities.
Theoretically all the above functions are continuous and well-behaved.
However, when fitting this model to data, due to model error or data noise,
the numerical results might not be always well-behaved.
Sigma being near 0 is a huge problem, although I've demanded the low bound
of sigma to be 1e-5.
p1 and p0 can be evaluated to be 0 or negative too. Although theoretically a
probability cannot be outside [0, 1], but when fitting it to data, it can
give negative values and values that are greater than 1, depending on the
data.
Thus this 4D log likelihood function is hard to maximize using data. I am
trying many solvers.
As you can see, theoretically, everything is continuous, except sigma=0, but
I've set lower bound of sigma to be 1e-5.
I even could not answer your question about "how many local minimums",
because with z=f(x, y, u, v) 4D function, I was unable to systematically
visualize the sample points at all.
Any thoughts? |
|
|
| Back to top |
|
|
gino
science forum beginner
Joined: 01 Feb 2006
Posts: 29
|
| Posted: Sat Jul 01, 2006 5:01 am Post subject:
Re: grid search for global optimum, is there a way to decide stepsize?
|
|
|
"optionstraderjeff" <jeffkatz@scientific-consultants.com> wrote in message
news:1151670299.221764.45200@m73g2000cwd.googlegroups.com...
| Quote: | Hi,
Why not try genetic optimization. Genetic algorithms are amazingly
effective when it comes to locating global optima; and, they can be
orders of magnitude faster than other stochastic or brute-force methods
when many parameters (>> 4) must be estimated. Depending on the
precision required, you may want to combine a GA with a localized NR
procedure (something you can do if your function is continuous and
well-behaved).
Jeff
|
Thanks a lot Jeff.
But I have heard a lot about bad fames about these fancy stochastic
searching algorithms. They don't guarantee optimality, they are just
stochastic procedures, they are all about chance, that's the problem.
They are only used when people are desperate.
But for my 4-parameter small problem, I still hope some good global
searching algorithm can give me guaranteed global optimum within reasonable
time. I can wait for quite a few hours...or 1 day, etc. But the result
should be truely global optimum.
okay, which Genetic algorithm is the current state-of-art? |
|
| Back to top |
|
|
C6L1V@shaw.ca
science forum Guru
Joined: 23 May 2005
Posts: 628
|
| Posted: Sat Jul 01, 2006 3:30 pm Post subject:
Re: grid search for global optimum, is there a way to decide stepsize?
|
|
|
gino wrote:
| Quote: | "optionstraderjeff" <jeffkatz@scientific-consultants.com> wrote in message
news:1151670299.221764.45200@m73g2000cwd.googlegroups.com...
Hi,
Why not try genetic optimization. Genetic algorithms are amazingly
effective when it comes to locating global optima; and, they can be
orders of magnitude faster than other stochastic or brute-force methods
when many parameters (>> 4) must be estimated. Depending on the
precision required, you may want to combine a GA with a localized NR
procedure (something you can do if your function is continuous and
well-behaved).
Jeff
Thanks a lot Jeff.
But I have heard a lot about bad fames about these fancy stochastic
searching algorithms. They don't guarantee optimality, they are just
stochastic procedures, they are all about chance, that's the problem.
They are only used when people are desperate.
But for my 4-parameter small problem, I still hope some good global
searching algorithm can give me guaranteed global optimum within reasonable
time. I can wait for quite a few hours...or 1 day, etc. But the result
should be truely global optimum.
|
No algorithm can ever guarantee your getting the exact optimum, even in
well-behaved problems having only a single minimum. All
algorithms---implemented on real computers, using real
finite-wordlength calculations---can only get within some epsilon of
the optimum. They all come with either user-defined, or default
stopping rules that order them to halt when they reach a certain level
of precision. Global search algorithms work that way too: they will
typically stop whenever they reach a solution that is proveably within
some tolerance of the optimum.
R.G. Vickson
| Quote: |
okay, which Genetic algorithm is the current state-of-art? |
|
|
| Back to top |
|
|
optionstraderjeff
science forum beginner
Joined: 30 Jun 2006
Posts: 2
|
| Posted: Mon Jul 03, 2006 10:14 am Post subject:
Re: grid search for global optimum, is there a way to decide stepsize?
|
|
|
Hi,
GAs get bad flames because they have often been used to fit a very
large number of parameters (more than could be fit in a reasonable time
using more traditional methods)with severe "curve fitting" being the
inevitable result. The real problem, of course, is fitting an
excessive number of parameters, not the fact that a GA was used to do
the fitting.
And yes, a GA is not guaranteed to find the global optimum; but, GAs
appear to do very well when it comes to solving extremely difficult
problems--"NP-Hard problems, as they say--like finding an optimal set
of tracings for the lines on a printed circuit board, constructing
complex molecules and "designer" drugs, and even creating and adapting
(optimizing) all the various forms of life on earth!
Stochastic processes may be "chancy", but chance, properly harnessed,
can solve all kinds of problems.
Finally, you do not need a "state of the art" GA. Any good, basic
implementation will handle your problem. I can email you a GA class in
C++ if you send me an email to
jeffkatz@scientific-consultants.com
mentioning this post.
By the way, if you want a good laugh, read "The Dice Man" by Luke
Reinhart--it is a really funny book. Couldn't help but mention it
given the context.
Jeff
gino wrote:
| Quote: | "optionstraderjeff" <jeffkatz@scientific-consultants.com> wrote in message
news:1151670299.221764.45200@m73g2000cwd.googlegroups.com...
Hi,
Why not try genetic optimization. Genetic algorithms are amazingly
effective when it comes to locating global optima; and, they can be
orders of magnitude faster than other stochastic or brute-force methods
when many parameters (>> 4) must be estimated. Depending on the
precision required, you may want to combine a GA with a localized NR
procedure (something you can do if your function is continuous and
well-behaved).
Jeff
Thanks a lot Jeff.
But I have heard a lot about bad fames about these fancy stochastic
searching algorithms. They don't guarantee optimality, they are just
stochastic procedures, they are all about chance, that's the problem.
They are only used when people are desperate.
But for my 4-parameter small problem, I still hope some good global
searching algorithm can give me guaranteed global optimum within reasonable
time. I can wait for quite a few hours...or 1 day, etc. But the result
should be truely global optimum.
okay, which Genetic algorithm is the current state-of-art? |
|
|
| Back to top |
|
|
Matthew Lybanon
science forum beginner
Joined: 09 Aug 2005
Posts: 8
|
| Posted: Mon Jul 03, 2006 3:12 pm Post subject:
Re: grid search for global optimum, is there a way to decide stepsize?
|
|
|
in article 1151921688.604342.262620@m79g2000cwm.googlegroups.com,
optionstraderjeff at jeffkatz@scientific-consultants.com wrote on 7/3/06
5:14 AM:
| Quote: | Hi,
GAs get bad flames because they have often been used to fit a very
large number of parameters (more than could be fit in a reasonable time
using more traditional methods)with severe "curve fitting" being the
inevitable result. The real problem, of course, is fitting an
excessive number of parameters, not the fact that a GA was used to do
the fitting.
And yes, a GA is not guaranteed to find the global optimum; but, GAs
appear to do very well when it comes to solving extremely difficult
problems--"NP-Hard problems, as they say--like finding an optimal set
of tracings for the lines on a printed circuit board, constructing
complex molecules and "designer" drugs, and even creating and adapting
(optimizing) all the various forms of life on earth!
Stochastic processes may be "chancy", but chance, properly harnessed,
can solve all kinds of problems.
Finally, you do not need a "state of the art" GA. Any good, basic
implementation will handle your problem. I can email you a GA class in
C++ if you send me an email to
jeffkatz@scientific-consultants.com
mentioning this post.
By the way, if you want a good laugh, read "The Dice Man" by Luke
Reinhart--it is a really funny book. Couldn't help but mention it
given the context.
Jeff
gino wrote:
"optionstraderjeff" <jeffkatz@scientific-consultants.com> wrote in message
news:1151670299.221764.45200@m73g2000cwd.googlegroups.com...
Hi,
Why not try genetic optimization. Genetic algorithms are amazingly
effective when it comes to locating global optima; and, they can be
orders of magnitude faster than other stochastic or brute-force methods
when many parameters (>> 4) must be estimated. Depending on the
precision required, you may want to combine a GA with a localized NR
procedure (something you can do if your function is continuous and
well-behaved).
Jeff
Thanks a lot Jeff.
But I have heard a lot about bad fames about these fancy stochastic
searching algorithms. They don't guarantee optimality, they are just
stochastic procedures, they are all about chance, that's the problem.
They are only used when people are desperate.
But for my 4-parameter small problem, I still hope some good global
searching algorithm can give me guaranteed global optimum within reasonable
time. I can wait for quite a few hours...or 1 day, etc. But the result
should be truely global optimum.
okay, which Genetic algorithm is the current state-of-art?
|
Genetic algorithms are sometimes used because they are faster than other
methods, or more efficient in some other way. They are not guaranteed to
find a global optimum, but neither are more traditional methods such as
steepest descent.
A few examples of using GAs in real problems (a few years old, but not that
old):
B. P. Buckles, F. E. Petry, D. Prabhu, and M. Lybanon, Mesoscale Feature
Labeling from Satellite Images, in Genetic Algorithms for Pattern
Recognition, S. K. Pal and P. P. Wang, ed., CRC Press, 1996, ISBN
0-8493-9467-8, pp. 167-177.
M. Lybanon and K. C. Messa, Chapter 8: Genetic Algorithm Model Fitting, in
Practical Handbook of Genetic Algorithms, Complex Coding Systems, Volume
III, L. D. Chambers, ed., CRC Press LLC, 1999, ISBN 0-8493-2539-0. |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Thu Jun 30, 2011 9:19 am | All times are GMT
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums |
send newsletters
|
| |
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
