Linear Complementarity problems (LCP)¶

The problem:

The Linear Complementarity problem (LCP) is defined by

Find $$(z,w)$$ such that:

$\begin{split}\begin{equation*} \begin{cases} M \ z + q = w \\ 0 \le w \perp z \ge 0 \end{cases}, \end{equation*}\end{split}$

where :math: w, z, q are vectors of size $$n$$ and :math: M  is a $$n\times n$$ matrix.

The notation $$x \perp y$$ means that $$x^Ty =0$$ . Inequalities involving vectors are understood to hold component-wise.

From more details on theory and analysis of LCP, we refer to

R.W. Cottle, J.S. Pang, and R.E. Stone. The Linear Complementarity Problem. Academic Press, Inc., Boston, MA, 1992.

The problem is stored and given to the solver in numerics thanks to the C structure LinearComplementarityProblem .

Available solvers:

Use the generic functions lcp_driver_DenseMatrix() to call one the the specific solvers listed below:

Direct solvers:

Iterative solvers:

Equation-based solvers:

QP-reformulation:

(see also the functions/solvers list in LCP_Solvers.h and numbering in lcp_cst.h )