Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Linear complementarity problem
Summary
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. It was proposed by Cottle and Dantzig in 1968.
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:
(that is, each component of these two vectors is non-negative)
or equivalently This is the complementarity condition, since it implies that, for all , at most one of and can be positive.
A sufficient condition for existence and uniqueness of a solution to this problem is that M be symmetric positive-definite. If M is such that LCP(q, M) has a solution for every q, then M is a Q-matrix. If M is such that LCP(q, M) have a unique solution for every q, then M is a P-matrix. Both of these characterizations are sufficient and necessary.
The vector w is a slack variable, and so is generally discarded after z is found. As such, the problem can also be formulated as:
(the complementarity condition)
Finding a solution to the linear complementarity problem is associated with minimizing the quadratic function
subject to the constraints
These constraints ensure that f is always non-negative. The minimum of f is 0 at z if and only if z solves the linear complementarity problem.
If M is positive definite, any algorithm for solving (strictly) convex QPs can solve the LCP. Specially designed basis-exchange pivoting algorithms, such as Lemke's algorithm and a variant of the simplex algorithm of Dantzig have been used for decades. Besides having polynomial time complexity, interior-point methods are also effective in practice.
Also, a quadratic-programming problem stated as minimize subject to as well as with Q symmetric
is the same as solving the LCP with
This is because the Karush–Kuhn–Tucker conditions of the QP problem can be written as:
with v the Lagrange multipliers on the non-negativity constraints, λ the multipliers on the inequality constraints, and s the slack variables for the inequality constraints.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (9)
Related people (1)