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:

  • 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 )