# Linear Complemtary Problem (LCP)

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

## 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 on other sites
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 on other sites
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 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.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 11
• 9
• 24
• 49