In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case.
[1][2][3] Given a real matrix M and vector q, the linear complementarity problem LCP(q, M) seeks vectors z and w which satisfy the following constraints: A sufficient condition for existence and uniqueness of a solution to this problem is that M be symmetric positive-definite.
Besides having polynomial time complexity, interior-point methods are also effective in practice.
The fourth condition derives from the complementarity of each group of variables (x, s) with its set of KKT vectors (optimal Lagrange multipliers) being (v, λ).
In that case, If the non-negativity constraint on the x is relaxed, the dimensionality of the LCP problem can be reduced to the number of the inequalities, as long as Q is non-singular (which is guaranteed if it is positive definite).
The multipliers v are no longer present, and the first KKT conditions can be rewritten as: or: pre-multiplying the two sides by A and subtracting b we obtain: The left side, due to the second KKT condition, is s. Substituting and reordering: Calling now we have an LCP, due to the relation of complementarity between the slack variables s and their Lagrange multipliers λ.
Finally, it is also possible to handle additional equality constraints: This introduces a vector of Lagrange multipliers μ, with the same dimension as
are now expressed as: From λ we can now recover the values of both x and the Lagrange multiplier of equalities μ: In fact, most QP solvers work on the LCP formulation, including the interior point method, principal / complementarity pivoting, and active set methods.
[1][2] LCP problems can be solved also by the criss-cross algorithm,[6][7][8][9] conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.