Fast Numerical Gradient required
Author
Hello!
I have a multi-objective function. It''s analytical gradient is difficult to calculate. I am using the central forward method to find its grdient like given below:
F = f(x1,x2,............,xn)
del = 0.00000001
then grdient g_i with respect to x_i is
g_1 = [f(x1+del, x2,....,xn) - f(x1-del, x2,...,xn)]/(2*del)
g_2 = [f(x1, x2+del,....,xn) - f(x1, x2-del,...,xn)]/(2*del)
.
.
.
g_n = [f(x1, x2,....,xn+del) - f(x1, x2,...,xn-del)]/(2*del)
Problem arises when n increase and it takes a long time. Any suggestion to make it fast ??????
Regards
Alam
You are trying to calculate n values. The time this takes has to be O(n). Even if you had the analytical solution.
The only optimisation that occurs to me would be possible if some of the parameters were independant of each other.
---------------------------
I may be getting older, but I refuse to grow up
The only optimisation that occurs to me would be possible if some of the parameters were independant of each other.
---------------------------
I may be getting older, but I refuse to grow up
quote:Original post by Alam
F = f(x1,x2,............,xn)
del = 0.00000001
then grdient g_i with respect to x_i is
g_1 = [f(x1+del, x2,....,xn) - f(x1-del, x2,...,xn)]/(2*del)
g_2 = [f(x1, x2+del,....,xn) - f(x1, x2-del,...,xn)]/(2*del)
.
.
.
g_n = [f(x1, x2,....,xn+del) - f(x1, x2,...,xn-del)]/(2*del)
I haven''t tried anything like this before, so this might not be an acceptable optimization. What I''d suggest is changing the equations to:
g_1 = [f(x1+del, x2,....,xn) - f(x1, x2,...,xn)]/(del)
g_2 = [f(x1, x2+del,....,xn) - f(x1, x2,...,xn)]/(del)
.
.
.
g_n = [f(x1, x2,....,xn+del) - f(x1, x2,...,xn)]/(del)
but that might lose some accuracy or something. Maybe you''d want to double the size of del if floating point errors become significant. What it obviously achieves is only calculating the right hand f()s once, rather than n times. This wouldn''t really help much if the time to compute f() is small.
What is f? Perhaps someone could solve this analytically for you?
Miles
quote:Original post by Alam
Hello!
I have a multi-objective function. It''s analytical gradient is difficult to calculate. I am using the central forward method to find its grdient like given below:
F = f(x1,x2,............,xn)
del = 0.00000001
then grdient g_i with respect to x_i is
g_1 = [f(x1+del, x2,....,xn) - f(x1-del, x2,...,xn)]/(2*del)
This seems academic to me. What is your project?
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
dunno how big your function is, but you can get rid of the division..
"take a look around" - limp bizkit
www.google.com
"take a look around" - limp bizkit
www.google.com
Author
Yes it is a accademic project. I am doing some kind of simulation/manipulation that needs energy minimization. For Steepest descent or conjugate gradient method gradient is needed.
Analytic method is fastest. Since F is complicated, it can create some error.
If i use farward method, [F(x+del)-F(x)]/del, accuracy is lost that i don''t want.
Actually F is a complex function, any change in x1, causes changes in many variable. Each x_i is linked with x_j (j=1,2...,m). So calculating function also take time.
Any idea to skip some terms and so on ?
Regards
Alam
Alam
-- Learning never ends --
you can try to eliminate the division. but i don''t know if this changes anything.
try instead:
g_1 = [f(x1+del, x2,....,xn) - f(x1, x2,...,xn)]/(del)
double invDel = 1.0 / del;
g_1 = [f(x1+del, x2,....,xn) - f(x1, x2,...,xn)]*(invDel);
are there maybe some symmetries in the formula for g_1 to g_n like intermediate data that you have to calculate several times. if yes you could reuse them. how is f(...) defined? what size can n have at the top?
try instead:
g_1 = [f(x1+del, x2,....,xn) - f(x1, x2,...,xn)]/(del)
double invDel = 1.0 / del;
g_1 = [f(x1+del, x2,....,xn) - f(x1, x2,...,xn)]*(invDel);
are there maybe some symmetries in the formula for g_1 to g_n like intermediate data that you have to calculate several times. if yes you could reuse them. how is f(...) defined? what size can n have at the top?
quote:Original post by Alam
Yes it is a accademic project. I am doing some kind of simulation/manipulation that needs energy minimization. For Steepest descent or conjugate gradient method gradient is needed.
Please understand that these forums are focused specifically on game development, and are not a general place for discussions not directly related to the game development industry.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
To Alam: It''s a pity you haven''t told any details of what you''re doing, as that would help a lot. The conjugate gradient method itself requires no gradient solving per iteration, you simply feed it the coefficient matrix A and the right side vector b and the CG algorithm solves Ax=b for the vector x, no numerical gradients required. Of course if the computation of A or b requires a gradient of some kind it''s different.
To GRhodes: I don''t think that kind of "this subject doesn''t belong to game development" will make games more diverse (simulation subjects are usually well suited for games, btw, for example physics simulation).
- Mikko Kauppila
To GRhodes: I don''t think that kind of "this subject doesn''t belong to game development" will make games more diverse (simulation subjects are usually well suited for games, btw, for example physics simulation).
- Mikko Kauppila
quote:Original post by uutee
To GRhodes: I don''t think that kind of "this subject doesn''t belong to game development" will make games more diverse (simulation subjects are usually well suited for games, btw, for example physics simulation).
Of course you''re correct in what you say. My post was meant as a reminder, really, that I don''t want to deviate too far from game development. I''d really prefer to discuss, say, a physics simulation problem that is specifically being developed for a game project compared with a purely scientific university or commercial research project. Bandwidth and servers cost money. Gamedev.net is growing quite rapidly, and there is evidence that more bandwidth and server space will be necessary to keep going soon. We already had one crisis several months ago, and I fear another is coming. If we allow any and all "math & physics" topics, even those unrelated specifically to games, we''ll be at a crisis point much sooner. We''re nearly there already (it occasionally takes me several HOURS to successfully post a single reply to a thread due to server limit issues). My vision of the future? Eventually you''ll have to pay for gamedev. By occasionally controlling topics, that can be delayed. Note that these bandwidth/server comments are based on my opinion and observations/experiences/interpretation of comments from others and do not necessarily reflect the views of those who actually manage the hardware side of the site.
If I had thought this were a completely off topic post, I would have closed the thread. For example, I have a fairly strict policy on homework (many folks try to abuse these forums to get answers to their homework).
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
