# Linear Complementarity problems (LCP)¶

The problem:

The Linear Complementarity problem (LCP) is defined by

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

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:

`lcp_lexicolemke()`

, direct solver for LCP based on pivoting method principle for degenerate problem: the choice of pivot variable is performed via lexicographic ordering.`lcp_pivot()`

, generic solver for pivot-based methods: Bard, Murty and Lemke rules are implemented.`lcp_enum()`

, enumerative solver (brute-force method which tries every possible solution).`lcp_path()`

, interface to the PATH solver

Iterative solvers:

`lcp_cpg()`

, CPG (Conjugated Projected Gradient) solver for LCP based on quadratic minimization.`lcp_pgs()`

, PGS is a basic Projected Gauss-Seidel solver for LCP.`lcp_rpgs()`

, Regularized Projected Gauss-Seidel, is a solver for LCP, able to handle matrices with null diagonal terms.`lcp_psor()`

, Projected Succesive over relaxation solver for LCP. See Cottle, Pang Stone Chap 5.`lcp_latin()`

, (LArge Time INcrements) is a basic latin solver for LCP.`lcp_latin_w()`

, (LArge Time INcrements) is a basic latin solver with relaxation for LCP.`lcp_nsgs_SBM()`

, Gauss-Seidel solver based on a Sparse-Block storage for the matrix M of the LCP.

Equation-based solvers:

`lcp_newton_min()`

, nonsmooth Newton method based on the min formulation of the LCP.`lcp_newton_FB()`

, uses a nonsmooth newton method based on the Fischer-Bursmeister NCP function.`lcp_newton_minFB()`

, nonsmooth Newton method combining the min and FB functions.

QP-reformulation:

`lcp_qp()`

, quadratic programm formulation`lcp_nsqp()`

, quadratic programm formulation for solving an non symmetric LCP

(see also the functions/solvers list in `LCP_Solvers.h`

and numbering in `lcp_cst.h`

)