Jump to content
  • Advertisement
Sign in to follow this  
Dirk Gregorius

Linear Complemtary Problem (LCP)

This topic is 4771 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

The Linear Complementary Problem (LCP) is defined like this: Given is a square matrix A and column vector b. Find x and w satisfying: w-A*x=b, w>=0, x>=0, w_i*x_i=0 for all i For the case that w equals the zero vector the problem simply becomes: A*x=b, x>=0 I am looking for literature dealing with this special case. Is there a proof that I simply can solve the linear system and then set all c_i < 0 simply to zero, like done in some of the physic engines (ODE and Open Tissue). They simply add the word "Projected" to the classical iterative solver ( Projected Conjugate Gradient, Projected SOR, Projected Gauss-Seidel, etc) and during the iteration the result is simply clamped when it doesn't meet the second condition. What if I have to solve a system where is x not just needed to be greate or equal than zero, but needs to lie between two boundaries: A*x=b, lo<=x<=hi The comma normaly denotes a mathematical "and" that would mean that if the solution does not satisfy the second condition the system does not have a solution at all. Does complementary simply states: If the first condition isn't met the second one must hold? Regards, -Dirk

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
You can't just clamp the negative components. For a counterexample, take a look at A = (1,1;1,1), b = (1,1). x = (-1,2) satisfies the equality, but the clamped version does not.

With iterative methods, clamping works as long as the clamping itself doesn't screw with convergence, which depends on the type of system. If the matrix is SPD, as is often the case, and a component is negative, then clamping it to zero actually improves the estimate, and all is well.

As for A*x=b, lo<

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Heh. As I was saying, the case of two constraints translates into the canonical w-Ax=b form. Most optimization books list conversion steps, so does Google.

Share this post


Link to post
Share on other sites
So there are requirements to the system matrix A for the clamping. So as long as the matrix A is positive definit (PD) or positive semi-definit (PSD) I am ok. Any resources on this topic?

Regards,

-Dirk

PS: I would use google, but I am not sure what I should search for. Any recommendations are appreciated.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!