Search   Memberlist   Usergroups
 Page 2 of 2 [22 Posts] View previous topic :: View next topic Goto page:  Previous  1, 2
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
 Quote: David A. Heiser wrote: "gino" 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
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...

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...
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?
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?

 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.

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?
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" 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?
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" 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?
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?

optionstraderjeff at jeffkatz@scientific-consultants.com wrote on 7/3/06
5:14 AM:

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.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 2 of 2 [22 Posts] Goto page:  Previous  1, 2 View previous topic :: View next topic
 The time now is Thu Jun 30, 2011 9:19 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Energy (not pollution) and global warming. PETER1929@TISCALI.CO.UK New Theories 3 Wed Jul 19, 2006 6:38 pm WHEW! The Real Cause of Global Warming Ed Conrad Chem 0 Wed Jul 19, 2006 1:24 pm How to break this USA heat wave of 104 degree F; solution... a_plutonium@hotmail.com Chem 7 Mon Jul 17, 2006 7:31 pm paper search system gnomo74@hotmail.com Chemical 0 Wed Jul 12, 2006 1:16 pm Thistle seed to solve Global Warming a_plutonium@hotmail.com Chem 9 Wed Jul 12, 2006 7:30 am

Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters