|
|
| Author |
Message |
goldfita@signalsguru.net
science forum beginner
Joined: 27 Jun 2006
Posts: 4
|
 Posted: Tue Jun 27, 2006 1:09 pm Post subject:
basic minimization question
|
|
|
I want to minimize a function of 64 parameters. Each variable is an
integer 1 to 255. I only know the parameters and the function's value
for those parameters. Also, there will be more than one minima (i.e.
f(X) = f(y) = ... = min(f), x<>y), but any of them is ok. There will
probably also be many local minima with the same property.
My question is can this be done in a sane amount of time (hours)? If
so, where do I start? I'm only familiar with steepest descent, but I'm
not sure if that's appropriate, and I don't know how to find the
gradient. I see someone recommended "Iterative Solution of Nonlinear
Equations in Several Variables" in another post. This looks like it
might be helpful. I may not have the background to understand though.
Thanks! |
|
| Back to top |
|
 |
Torsten Hennig
science forum Guru Wannabe
Joined: 28 Apr 2005
Posts: 136
|
| Posted: Tue Jun 27, 2006 1:50 pm Post subject:
Re: basic minimization question
|
|
|
| Quote: | I want to minimize a function of 64 parameters. Each >variable is an
integer 1 to 255. I only know the parameters and the >function's value
for those parameters. Also, there will be more than one >minima (i.e.
f(X) = f(y) = ... = min(f), x<>y), but any of them is >ok. There will
probably also be many local minima with the same >property.
My question is can this be done in a sane amount of time >(hours)? If
so, where do I start? I'm only familiar with steepest >descent, but I'm
not sure if that's appropriate, and I don't know how to >find the
gradient. I see someone recommended "Iterative Solution >of Nonlinear
Equations in Several Variables" in another post. This >looks like it
might be helpful. I may not have the background to >understand though.
Thanks!
|
Looks like an integer nonlinear programming problem
which is normally solved by branch-and-bound methods.
For further links look at
http://plato.la.asu.edu/topics/problems/nlores.html
Maybe you can save some time instead of testing all
of the 64^255 possibilities for your solution vector,
but nevertheless the problem will be
tremendously time-consuming to solve.
Could you provide more information about the structure
of the function to be minimized ?
Best wishes
Torsten. |
|
| Back to top |
|
|
goldfita@signalsguru.net
science forum beginner
Joined: 27 Jun 2006
Posts: 4
|
| Posted: Tue Jun 27, 2006 1:56 pm Post subject:
Re: basic minimization question
|
|
|
goldfita@signalsguru.net wrote:
| Quote: | I want to minimize a function of 64 parameters. Each variable is an
integer 1 to 255. I only know the parameters and the function's value
for those parameters. Also, there will be more than one minima (i.e.
f(X) = f(y) = ... = min(f), x<>y), but any of them is ok. There will
probably also be many local minima with the same property.
My question is can this be done in a sane amount of time (hours)? If
so, where do I start? I'm only familiar with steepest descent, but I'm
not sure if that's appropriate, and I don't know how to find the
gradient. I see someone recommended "Iterative Solution of Nonlinear
Equations in Several Variables" in another post. This looks like it
might be helpful. I may not have the background to understand though.
Thanks!
|
I forgot to mention, the parameters can be made real-valued if
necessary. I just need the integer values as the solution. I suppose
what I really want is arg min (f) over x. X can be rounded to get the
final solution. |
|
| Back to top |
|
|
goldfita@signalsguru.net
science forum beginner
Joined: 27 Jun 2006
Posts: 4
|
| Posted: Tue Jun 27, 2006 2:31 pm Post subject:
Re: basic minimization question
|
|
|
Torsten Hennig wrote:
| Quote: | I want to minimize a function of 64 parameters. Each >variable is an
integer 1 to 255. I only know the parameters and the >function's value
for those parameters. Also, there will be more than one >minima (i.e.
f(X) = f(y) = ... = min(f), x<>y), but any of them is >ok. There will
probably also be many local minima with the same >property.
My question is can this be done in a sane amount of time >(hours)? If
so, where do I start? I'm only familiar with steepest >descent, but I'm
not sure if that's appropriate, and I don't know how to >find the
gradient. I see someone recommended "Iterative Solution >of Nonlinear
Equations in Several Variables" in another post. This >looks like it
might be helpful. I may not have the background to >understand though.
Thanks!
Looks like an integer nonlinear programming problem
which is normally solved by branch-and-bound methods.
For further links look at
http://plato.la.asu.edu/topics/problems/nlores.html
Maybe you can save some time instead of testing all
of the 64^255 possibilities for your solution vector,
but nevertheless the problem will be
tremendously time-consuming to solve.
|
Isn't that 255^64?
| Quote: | Could you provide more information about the structure
of the function to be minimized ?
|
I probably shouldn't say too much since this is a work related problem.
Without telling you exactly what I'm doing, all I can say is there
will be many solutions and I think many flat areas which are not
minima. It seems like I should be able to use something like SDA, but
can I escape from local minima? I'm just guessing... I may be able to
seed the algorithm with a close approximation. But with numbers this
large, I don't know how much that helps.
| Quote: | Best wishes
Torsten. |
|
|
| Back to top |
|
|
Martin Brown
science forum addict
Joined: 12 May 2005
Posts: 82
|
| Posted: Tue Jun 27, 2006 3:37 pm Post subject:
Re: basic minimization question
|
|
|
goldfita@signalsguru.net wrote:
| Quote: | Torsten Hennig wrote:
I want to minimize a function of 64 parameters. Each >variable is an
integer 1 to 255. I only know the parameters and the >function's value
for those parameters. Also, there will be more than one >minima (i.e.
f(X) = f(y) = ... = min(f), x<>y), but any of them is >ok. There will
probably also be many local minima with the same >property.
|
But will there be comparatively few global minima, and many spurious
local minima or featureless plateaus?
I presume you want the global minima, or a good working approximation
to it?
| Quote: | My question is can this be done in a sane amount of time >(hours)? If
so, where do I start? I'm only familiar with steepest >descent, but I'm
not sure if that's appropriate, and I don't know how to >find the
gradient.
|
Can you differentiate your function f(X) wrt each of the parameters?
Without knowing more about the properties of f(X) it is impossible to
say what method(s) will work best.
| Quote: | Looks like an integer nonlinear programming problem
which is normally solved by branch-and-bound methods.
For further links look at
http://plato.la.asu.edu/topics/problems/nlores.html
Maybe you can save some time instead of testing all
of the 64^255 possibilities for your solution vector,
but nevertheless the problem will be
tremendously time-consuming to solve.
Isn't that 255^64?
|
Yes.
| Quote: | Could you provide more information about the structure
of the function to be minimized ?
I probably shouldn't say too much since this is a work related problem.
|
OK first thing is to factor out any symmetries inherent in the problem.
Every little helps.
| Quote: | Without telling you exactly what I'm doing, all I can say is there
will be many solutions and I think many flat areas which are not
minima. It seems like I should be able to use something like SDA, but
can I escape from local minima? I'm just guessing... I may be able to
seed the algorithm with a close approximation. But with numbers this
large, I don't know how much that helps.
|
It sounds like the sort of problem that simulated annealling sometimes
excels at. I once used it for a nasty combinatorial problem and a
humble PC running for a week came close to matching the true global
minimum found by a suprcomputer using brute force.
Regards,
Martin Brown |
|
| Back to top |
|
|
goldfita@signalsguru.net
science forum beginner
Joined: 27 Jun 2006
Posts: 4
|
| Posted: Tue Jun 27, 2006 4:17 pm Post subject:
Re: basic minimization question
|
|
|
|||newspam|||@nezumi.demon.co.uk wrote:
| Quote: | goldfita@signalsguru.net wrote:
Torsten Hennig wrote:
I want to minimize a function of 64 parameters. Each >variable is an
integer 1 to 255. I only know the parameters and the >function's value
for those parameters. Also, there will be more than one >minima (i.e.
f(X) = f(y) = ... = min(f), x<>y), but any of them is >ok. There will
probably also be many local minima with the same >property.
But will there be comparatively few global minima, and many spurious
local minima or featureless plateaus?
I presume you want the global minima, or a good working approximation
to it?
|
Yes. I can only guess that there will be many plateaus (which are also
local minima).
| Quote: | My question is can this be done in a sane amount of time >(hours)? If
so, where do I start? I'm only familiar with steepest >descent, but I'm
not sure if that's appropriate, and I don't know how to >find the
gradient.
Can you differentiate your function f(X) wrt each of the parameters?
Without knowing more about the properties of f(X) it is impossible to
say what method(s) will work best.
|
I'm not sure. I only know the parameters and the function output. As
I said, the parameters can be made real-valued. Seems like I could
estimate the derivative with (f(x+dx)-f(x))/dx, but I think most of the
time it will just be 0 unless dx is an integer.
| Quote: | Looks like an integer nonlinear programming problem
which is normally solved by branch-and-bound methods.
For further links look at
http://plato.la.asu.edu/topics/problems/nlores.html
Maybe you can save some time instead of testing all
of the 64^255 possibilities for your solution vector,
but nevertheless the problem will be
tremendously time-consuming to solve.
Isn't that 255^64?
Yes.
Could you provide more information about the structure
of the function to be minimized ?
I probably shouldn't say too much since this is a work related problem.
OK first thing is to factor out any symmetries inherent in the problem.
Every little helps.
Without telling you exactly what I'm doing, all I can say is there
will be many solutions and I think many flat areas which are not
minima. It seems like I should be able to use something like SDA, but
can I escape from local minima? I'm just guessing... I may be able to
seed the algorithm with a close approximation. But with numbers this
large, I don't know how much that helps.
It sounds like the sort of problem that simulated annealling sometimes
excels at. I once used it for a nasty combinatorial problem and a
humble PC running for a week came close to matching the true global
minimum found by a suprcomputer using brute force.
|
I'll take a look at that. Thanks.
| Quote: | Regards,
Martin Brown |
|
|
| Back to top |
|
|
Julian V. Noble
science forum Guru Wannabe
Joined: 03 May 2005
Posts: 148
|
| Posted: Tue Jun 27, 2006 8:09 pm Post subject:
Re: basic minimization question
|
|
|
goldfita@signalsguru.net wrote:
| Quote: | I want to minimize a function of 64 parameters. Each variable is an
integer 1 to 255. I only know the parameters and the function's value
for those parameters. Also, there will be more than one minima (i.e.
f(X) = f(y) = ... = min(f), x<>y), but any of them is ok. There will
probably also be many local minima with the same property.
My question is can this be done in a sane amount of time (hours)? If
so, where do I start? I'm only familiar with steepest descent, but I'm
not sure if that's appropriate, and I don't know how to find the
gradient. I see someone recommended "Iterative Solution of Nonlinear
Equations in Several Variables" in another post. This looks like it
might be helpful. I may not have the background to understand though.
Thanks!
|
If I were faced with this problem I would first treat the
64 parameters as continuous variables, and since you don't
know if the function can be differentiated, use a method
such as downhill simplex (see Numerical Recipes) or perhaps
a stochastic method like simulated annealing.
Once I had a satisfactory minimum I would then explore its
neighborhood to see if a mutually compatible set of integer-valued
parameters can be found that are not the minimum but the best
you can do in integers.
--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 3:41 am | All times are GMT
|
|
Free Advertising | Debt Consolidation | Credit Cards | Problem Mortgage | Loans
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
num-analysis
