Sign in to follow this  
Ivan Reinaldo

Lagrange multiplier in constrained dynamics

Recommended Posts

I'm stuck at trying to understand how Lagrangian multiplier fits into all these things in collision resolution using sequential impulse. (needed for school presentation, and I'm pretty desperate lol)

I learn mostly from this tutorial at toptal ( which I don't understand starting from equality constraint. ) and Erin Catto slides.

 

As far as I understand, Lagrangian multiplier is used to solve constrained optimization problem, in which the function to be optimized need to lies on a constant made by another function (for example, minimize f(x,y) where g(x,y) = 0), whereas in the tutorial, it says what being minimized is actually the constraint function itself (quoted: " In other words, we want to minimize C.")

 

what am I missing here?

Edited by ivanrei

Share this post


Link to post
Share on other sites

In a velocity-based formulation the Lagrangian multiplier is the magnitude of a constraint impulse, whereas in a acceleration-based formulation is the magnitude of a constraint-force. It is required to put the constraint into a valid state. Having the constraint configuration defined, it shouldn't be difficult to solve for it currently.

 

I don't understand what is the second question though. For example, an equality constraint (e.g. distance, ball-in-socket, or a revolute joint) is satisfied for C = 0.  A inequality constraint (i.e. contact, angle limits) is satisfied when lo <= C <= hi (actually that is the general form of a constraint). Therefore generally is valid to say we want to minimize C so that it remais satisfied all the time. 

 

Yeah, minimize g(x(t)).

 

BTW, that's a good article and he basically summarized some of Catto's and Witkin's papers intuitively.  :)

Share this post


Link to post
Share on other sites

In a velocity-based formulation the Lagrangian multiplier is the magnitude of a constraint impulse, whereas in a acceleration-based formulation is the magnitude of a constraint-force. It is required to put the constraint into a valid state. Having the constraint configuration defined, it shouldn't be difficult to solve for it currently.

 

I don't understand what is the second question though. For example, an equality constraint (e.g. distance, ball-in-socket, or a revolute joint) is satisfied for C = 0.  A inequality constraint (i.e. contact, angle limits) is satisfied when lo <= C <= hi (actually that is the general form of a constraint). Therefore generally is valid to say we want to minimize C so that it remais satisfied all the time. 

 

Yeah, minimize g(x(t)).

 

BTW, that's a good article and he basically summarized some of Catto's and Witkin's papers intuitively.  :)

Hi Irlan, thank you for your response

I still don't understand, how come we minimize the constraint function? 

this is what I understand about langrange multiplier from calculus class (picture in attachment)

in the picture, it's the case if I try to minimize F, on constraint C, and by the way it's a contour plot.

did I make a mistake somewhere? can you please describe or make an analogy based on that picture?

and yeah, I agree it's a really good article, full with pastel color and stuff :D

Edited by ivanrei

Share this post


Link to post
Share on other sites
I haven't clicked on the link to the tutorial, but I can explain how Lagrange multipliers work.

You want to minimize f(x,y) subject to g(x,y) = 0. We'll introduce an additional variable l (usually "lambda", but I don't have that letter available). Let's look at the function

L(x,y,l) = f(x,y) - l*g(x,y)

and imagine you've found a point where the derivative of L with respect to each of the three variables is 0. You then have

dL/dx = df/dx - l*dg/dx = 0
dL/dy = df/dy - l*dg/dx = 0
dL/dl = g(x,y) = 0

The last condition guarantees that the constraint is being satisfied. The other two basically say that the levels of f and g are tangent.

These are necessary conditions for a point (x,y) to be a solution to your problem. Sufficient conditions do exist, but they are a bit trickier to think about, and this may or may not be important in your case.

Share this post


Link to post
Share on other sites

I haven't clicked on the link to the tutorial, but I can explain how Lagrange multipliers work.

You want to minimize f(x,y) subject to g(x,y) = 0. We'll introduce an additional variable l (usually "lambda", but I don't have that letter available). Let's look at the function

L(x,y,l) = f(x,y) - l*g(x,y)

and imagine you've found a point where the derivative of L with respect to each of the three variables is 0. You then have

dL/dx = df/dx - l*dg/dx = 0
dL/dy = df/dy - l*dg/dx = 0
dL/dl = g(x,y) = 0

The last condition guarantees that the constraint is being satisfied. The other two basically say that the levels of f and g are tangent.

These are necessary conditions for a point (x,y) to be a solution to your problem. Sufficient conditions do exist, but they are a bit trickier to think about, and this may or may not be important in your case.

 

@alvaro

thank you for your response. Yes, that is exactly the lagrange multiplier that I know.

What I don't understand is how it applies to this case, in the tutorial, it says that what being minimized is the constraint function itself.

whereas in your example, (and anywhere I see), we minimize F based on constraint function G. 

I've been at this for weeks, and at this point I'm starting to doubt it's referring to the same 'lagrange' lol

where did I go wrong?

Edited by ivanrei

Share this post


Link to post
Share on other sites

Yeah, agree with Álvaro, he's mathematically wrong. He meant minimizing C towards zero for his equality (although that is wrong either; he meant keeping the constraint between the constraint bounds). 

 

 

I read parts of the tutorial and I think that way of thinking of Lagrange multipliers is probably very useful. The part you quoted about minimizing C seems wrong, though.

so it's wrong? how exactly Lagrangian multiplier is supposed to be used in this case?

I've looked anywhere and explanation seems very unclear to me.. :/

allenchou.net/2013/12/game-physics-constraints-sequential-impulse/

Share this post


Link to post
Share on other sites

I think this is all related to Lagrange's equations (1. kind). You are not minimizing the constraint function but the Lagrange function which (IIRC!) the sum of potential and kinetic energy: 

 

https://en.wikipedia.org/wiki/Lagrangian_mechanics

 

I always found it difficult to find good material in English on this. In German there are tons of good resources...

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites

I think this is all related to Lagrange's equations (1. kind). You are not minimizing the constraint function but the Lagrange function which (IIRC!) the sum of potential and kinetic energy: 

 

https://en.wikipedia.org/wiki/Lagrangian_mechanics

 

I always found it difficult to find good material in English on this. In German there are tons of good resources...

@Dirk

thank you for your response :)

 

There's the same case of 'bead on a wire' constraint in that wikipedia page, so I'm guessing you're correct, although I can't really understand it,  maybe after I study it.

 

I never study Lagrangian mechanics, but from what I've read in that wikipedia link you gave, is it just how we would rewrite things?  

If that's the case, is this the equivalent in Newtonian?

 

in that video,basically, we look for collision normal, because that's the impulse direction, and then we compute magnitude of the impulse by relating it with "relative velocity"

 

by the way Dirk, your slides on collision detection at GDC helped me tremendously in implementing SAT, thanks :D 

Share this post


Link to post
Share on other sites

I think you might be a bit to concentrated on the term 'Lagrange Multiplier'. The important part here is that you know the direction of the constraint force is the gradient of the constraint function and you only need to find a scalar multiplier to determine the constraint force. The reason for this is that constraint forces doesn't do work. IIRC you can show this using virtual displacements. Maybe concentrate a bit more on the physical meaning rather than trying to be overly mathematical  abstract.

 

Thanks! I am glad you found it useful!

Share this post


Link to post
Share on other sites

I haven't watched that video completely, but I see that it follows Baraff's literature to solve for constraint *forces* (impulses / time_step). He uses essentially the same method as found in the constraint-based literature for non-penetration constraints using the LCP formulation. However, he uses quadratic programming (a global solver) to solve for the multipliers.

 

As Dirk said, you'll need to define your gradients (normals from the SAT for the collision case), each of which will be inserted into a Jacobian matrix for a general constraint-based system. From there you compute the lagrange multipliers as showed in Catto's slides. I think it is important to understand constraints geometrically when implementing these things. So yeah, we do look for a collision normal and point and only then we can find the force magnitude by relating it to the impulse-momentum law in Euler form and then we find the new relative velocities of each body after the collision/contact. 

 

BTW, different authors use the term impulse and force interchangeble, but assuming the force is constant during the time step then impulse = force * time_step. Therefore the lagrange multipliers both refer to the same thing.

 

(Do not take this too theoretical but here is an example without using Catto's simplification to solve for the multipliers (impulses) for a distance constraint.)

Edited by Irlan Robson

Share this post


Link to post
Share on other sites

I think you might be a bit to concentrated on the term 'Lagrange Multiplier'. The important part here is that you know the direction of the constraint force is the gradient of the constraint function and you only need to find a scalar multiplier to determine the constraint force. The reason for this is that constraint forces doesn't do work. IIRC you can show this using virtual displacements. Maybe concentrate a bit more on the physical meaning rather than trying to be overly mathematical  abstract.

 

Thanks! I am glad you found it useful!

 

I haven't watched that video completely, but I see that it follows Baraff's literature to solve for constraint *forces* (impulses / time_step). He uses essentially the same method as found in the constraint-based literature for non-penetration constraints using the LCP formulation. However, he uses quadratic programming (a global solver) to solve for the multipliers.

 

As Dirk said, you'll need to define your gradients (normals from the SAT for the collision case), each of which will be inserted into a Jacobian matrix for a general constraint-based system. From there you compute the lagrange multipliers as showed in Catto's slides. I think it is important to understand constraints geometrically when implementing these things. So yeah, we do look for a collision normal and point and only then we can find the force magnitude by relating it to the impulse-momentum law in Euler form and then we find the new relative velocities of each body after the collision/contact. 

 

BTW, different authors use the term impulse and force interchangeble, but assuming the force is constant during the time step then impulse = force * time_step. Therefore the lagrange multipliers both refer to the same thing.

 

(Do not take this too theoretical but here is an example without using Catto's simplification to solve for the multipliers (impulses) for a distance constraint.)

 

Hi guys, thank you for answering so far 

 

I've studied a bit of Lagrangian mechanic, I think I begin to see the gist of things now :D

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this