#### Archived

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

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

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

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

##### Share on other sites
dunno how big your function is, but you can get rid of the division..

"take a look around" - limp bizkit

##### 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 on other sites
you can try to eliminate the division. but i don''t know if this changes anything.

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

1. 1
2. 2
Rutin
22
3. 3
4. 4
5. 5
frob
12

• 9
• 17
• 9
• 31
• 16
• ### Forum Statistics

• Total Topics
632617
• Total Posts
3007450

×