Linear complementarity problem

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.Template:Sfnp Template:Sfnp Template:Sfnp

FormulationEdit

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:

<math>w, z \geqslant 0,</math> (that is, each component of these two vectors is non-negative)
<math>z^Tw = 0</math> or equivalently <math>\sum\nolimits_i w_i z_i = 0.</math> This is the complementarity condition, since it implies that, for all <math>i</math>, at most one of <math>w_i</math> and <math>z_i</math> can be positive.
<math>w = Mz + q</math>

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 Template:Math has a solution for every q, then M is a Q-matrix. If M is such that Template:Math have a unique solution for every q, then M is a P-matrix. Both of these characterizations are sufficient and necessary.Template:Sfnp

The vector w is a slack variable,Template:Sfnp and so is generally discarded after z is found. As such, the problem can also be formulated as:

<math>Mz+q \geqslant 0</math>
<math>z \geqslant 0</math>
<math>z^{\mathrm{T}}(Mz+q) = 0</math> (the complementarity condition)

Convex quadratic-minimization: Minimum conditionsEdit

Finding a solution to the linear complementarity problem is associated with minimizing the quadratic function

subject to the constraints

<math>{Mz}+q \geqslant 0</math>

<math>z \geqslant 0</math>

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 <math>f(x)=c^Tx+\tfrac{1}{2} x^T Qx</math> subject to <math>Ax \geqslant b</math> as well as <math>x \geqslant 0</math> with Q symmetric

is the same as solving the LCP with

<math>q = \begin{bmatrix} c \\ -b \end{bmatrix}, \qquad M = \begin{bmatrix} Q & -A^T \\ A & 0 \end{bmatrix}</math>

This is because the Karush–Kuhn–Tucker conditions of the QP problem can be written as:

<math>\begin{cases}

v = Q x - A^T {\lambda} + c \\ s = A x - b \\ x, {\lambda}, v, s \geqslant 0 \\ x^{T} v+ {\lambda}^T s = 0 \end{cases}</math>

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. The fourth condition derives from the complementarity of each group of variables Template:Math with its set of KKT vectors (optimal Lagrange multipliers) being Template:Math. In that case,

<math>z = \begin{bmatrix} x \\ \lambda \end{bmatrix}, \qquad w = \begin{bmatrix} v \\ s \end{bmatrix}</math>

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:

<math>Q x = A^{T} {\lambda} - c</math>

or:

<math> x = Q^{-1}(A^{T} {\lambda} - c)</math>

pre-multiplying the two sides by A and subtracting b we obtain:

<math> A x - b = A Q^{-1}(A^{T} {\lambda} - c) -b \,</math>

The left side, due to the second KKT condition, is s. Substituting and reordering:

<math> s = (A Q^{-1} A^{T}) {\lambda} + (- A Q^{-1} c - b )\,</math>

Calling now

<math>\begin{align}

M &:= (A Q^{-1} A^{T}) \\ q &:= (- A Q^{-1} c - b) \end{align}</math>

we have an LCP, due to the relation of complementarity between the slack variables s and their Lagrange multipliers λ. Once we solve it, we may obtain the value of x from λ through the first KKT condition.

Finally, it is also possible to handle additional equality constraints:

This introduces a vector of Lagrange multipliers μ, with the same dimension as <math>b_{eq}</math>.

It is easy to verify that the M and Q for the LCP system <math> s = M {\lambda} + Q</math> are now expressed as:

<math>\begin{align}

M &:= \begin{bmatrix} A & 0 \end{bmatrix} \begin{bmatrix} Q & A_{eq}^{T} \\ -A_{eq} & 0 \end{bmatrix}^{-1} \begin{bmatrix} A^T \\ 0 \end{bmatrix} \\ q &:= - \begin{bmatrix} A & 0 \end{bmatrix} \begin{bmatrix} Q & A_{eq}^{T} \\ -A_{eq} & 0 \end{bmatrix}^{-1} \begin{bmatrix} c \\ b_{eq} \end{bmatrix} - b \end{align}</math>

From λ we can now recover the values of both x and the Lagrange multiplier of equalities μ:

<math>\begin{bmatrix} x \\ \mu \end{bmatrix} = \begin{bmatrix} Q & A_{eq}^{T} \\ -A_{eq} & 0 \end{bmatrix}^{-1} \begin{bmatrix} A^T \lambda - c \\ -b_{eq} \end{bmatrix}</math>

In fact, most QP solvers work on the LCP formulation, including the interior point method, principal / complementarity pivoting, and active set methods.Template:Sfnp Template:Sfnp LCP problems can be solved also by the criss-cross algorithm,Template:Sfnp Template:Sfnp Template:Sfnp Template:Sfnp conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.Template:Sfnp Template:Sfnp A sufficient matrix is a generalization both of a positive-definite matrix and of a P-matrix, whose principal minors are each positive.Template:Sfnp Template:Sfnp Template:Sfnp Such LCPs can be solved when they are formulated abstractly using oriented-matroid theory.Template:Sfnp Template:Sfnp Template:Sfnp

NotesEdit

Template:Reflist

ReferencesEdit

External linksEdit

LCPSolve — A simple procedure in GAUSS to solve a linear complementarity problem
Siconos/Numerics open-source GPL implementation in C of Lemke's algorithm and other methods to solve LCPs and MLCPs

Template:Mathematical programming

Linear complementarity problem

Contents

FormulationEdit

Convex quadratic-minimization: Minimum conditionsEdit

See alsoEdit

NotesEdit

ReferencesEdit

Further readingEdit

External linksEdit