Archived

This topic is now archived and is closed to further replies.

Fast Numerical Gradient required

This topic is 5592 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
While I tend to agree with Graham on this issue (it''s preferable to see posts that are directly related to game development) I also feel that the question raised in this thread does crop up during development of simulators and therefore relates to game development (since simulators are one form of virtual environment that might be used for entertainment purposes).

Alam, from your posts I take it that you are trying to find a local optima of some quantify F = f(x1,...,xn), since you mention energy minimisation.

Are you specifically required to implement a gradient ascent/descent method for this optimisation or are you free to choose your own method?

From the optimisation perspective, if you only have analytic function evaluations available (i.e., you require numerical estimates of gradient to implement a gradient method) then you are in the realm of ''blind search'' problems. You might then want to consider the use of a genetic algorithm, since this is what they are ideally suited to (and originally designed for).

If, of course, you expect that f() is uni-modal then hill climbing will be far quicker than the canonical GA... although I can offer some slight alterations to the basic GA model that will make it roughly the same order of magnitude in speed as hill climbing on uni-modal functions.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
quote:
My vision of the future? Eventually you''ll have to pay for gamedev

Really? Do you think people would still use it? I think the community would wither and die...

To save bandwidth... There could be that FAQ thing. To answer the eternal question "How do I find the angle between two vectors?".

And, for Alam''s problem, if the function is known at compile-time, try inlining it. Maybe can the compiler find some optimizations by itself.

Cédric

Share this post


Link to post
Share on other sites
quote:
Original post by cedricl
from grhodes_at_work: "My vision of the future? Eventually you''ll have to pay for gamedev"

Really? Do you think people would still use it? I think the community would wither and die...

To save bandwidth... There could be that FAQ thing. To answer the eternal question "How do I find the angle between two vectors?".



Hmmm. An interesting point. If this were 2000 or 2001, I think a site such as this would probably die if people had to pay for it. In 2002, we''re borderline, in my opinion. People are, I like to think, getting more and more used to the idea that they will have to pay incrementally for premium content above and beyond their ISP. Someone has to pay for bandwidth and servers, and I don''t think online advertising would necessarily be able to support EVERY community web site out there. Gamedev is high profile enough that it might be able to weasle some advertisers into paying. Perhaps, perhaps not. I''d be willing to pay, say $30 a year for something like gamedev. Enough people paying that same $30 should do nicely, as the revenue would grow as the number of users grows.

As for the FAQ, although in theory its a great idea, I see it as basically useless. Maybe, if the system were smart and could analyze immature, poorly stated and incorrectly typed questions to determine they should be pointed directly to the FAQ, it would work. But if people are expected to be mature and patient enough to always look in the FAQ first, it isn''t going to work well enough. Its also a certainty that the FAQ won''t explain in the exact way that 90% of the people want anyway.

Again, my opinions, . And, really, quite well off topic. Perhaps even a waste of bandwidth. Therefore, I''m done talking now!


Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
OT, but the topic seems to be dead (I hope we haven''t killed it), and you don''t have an e-mail address. Where are we supposed to complain?

I''b be willing to pay too, as are a lot of people here, but if I''d been asked to pay before I began to be an active member, I would never have accepted.

A nice solution to the problem you are describing would be to automatically show the forum FAQ when somebody starts a new thread for their first time ever in the Maths-Phys forum (or any other), directing them to basic ressources, the forum archives, and, obviously, Google.

Cédric

Share this post


Link to post
Share on other sites
quote:
Original post by cedricl
OT, but the topic seems to be dead (I hope we haven''t killed it), and you don''t have an e-mail address. Where are we supposed to complain?



One last reply, . I removed my email when I started receiving too many direct emails from people begging for help with their math/physics problems outside of these forums. Now, if they were offering pay at my standard hourly consulting rate...

I suppose the place to complain is the "GDNet Suggestions, Comments and Ideas" forum...

quote:
Original post by cedricl
A nice solution to the problem you are describing would be to automatically show the forum FAQ when somebody starts a new thread for their first time ever in the Maths-Phys forum (or any other), directing them to basic ressources, the forum archives, and, obviously, Google.



I think there will be something along those lines when the new forum software is ready. The FAQ issue has been the subject of discussion among the moderators.

I appreciate all the helpful comments!

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites