LCP solvers

This page gives an overview of the available solvers for LCP in numerics component and their required parameters.

For each solver, the input argument are:

  • a LinearComplementarityProblem structure
  • the unknowns z and w
  • info, the termination value (0: convergence, >0 problem which depends on the solver)
  • a SolverOptions structure, which handles solver parameters (iparam and dparam)

Remark: when the filterOn parameter (from SolverOptions) is different from 0, lcp_compute_error() is called at the end of the process to check the validity of the solution. This function needs a tolerance value and returns an error. In that case, tolerance is dparam[0] and error output dparam[1]. Thus, in the following solvers, when dparam[0,1] are omitted, that means that they are not required inputs, and that if filter is on, some default values will be used.

lexicographic Lemke

Direct solver for LCP based on pivoting method principle for degenerated problem.

function: lcp_lexicolemke()

parameters:

  • iparam[0] (in) : max. number of iterations
  • iparam[1] (out): number of iterations processed

QP Solver

quadratic programm formulation for solving a LCP with a symmetric matrix M.

The QP we solve is

Minimize: \(z^T (M z + q)\) subject to \(Mz + q \geq 0\)

which is the classical reformulation that can be found in Cottle, Pang and Stone (2009).

If the symmetry condition is not fulfilled, use the NSQP Solver

function: lcp_qp()

parameters:

  • dparam[0] (in): tolerance

NSQP Solver

non symmetric (and not nonsmooth as one could have thought in a plateform dedicated to nonsmooth problems) quadratic programm formulation for solving an LCP with a non symmetric matrix.

function: lcp_nsqp()

parameters:

  • dparam[0] (in): tolerance

CPG Solver

Conjugated Projected Gradient solver for LCP based on quadratic minimization. Reference: “Conjugate gradient type algorithms for frictional multi-contact problems: applications to granular materials”, M. Renouf, P. Alart. doi:10.1016/j.cma.2004.07.009

function: lcp_cpg()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed
  • dparam[0] (in): tolerance
  • dparam[1] (out): resulting error

PGS Solver

Projected Gauss-Seidel solver

function: lcp_pgs()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed
  • dparam[0] (in): tolerance
  • dparam[1] (out): resulting error

RPGS Solver

Regularized Projected Gauss-Seidel, solver for LCP, able to handle with matrices with null diagonal terms

function: lcp_rpgs()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed
  • dparam[0] (in): tolerance
  • dparam[1] (out): resulting error
  • dparam[2] (in): rho

PSOR Solver

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

function: lcp_psor()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed
  • dparam[0] (in): tolerance
  • dparam[1] (out): resulting error
  • dparam[2] (in): relaxation parameter

NewtonMin Solver

a nonsmooth Newton method based on the min formulation of the LCP

function: lcp_newton_min()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed
  • iparam[2] (in): if > 0, keep the work vector (reduce the number of memory allocation if the same type of problem is solved multiple times)
  • iparam[3] (in): if > 0. use a non-monotone linear search
  • iparam[4] (in): if a non-monotone linear search is used, specify the number of merit values to remember
  • dparam[0] (in): tolerance
  • dparam[1] (out): resulting error

NewtonFB Solver

a nonsmooth Newton method based based on the Fischer-Burmeister NCP function. It uses a variant of line search algorithm (VFBLSA in Facchinei-Pang 2003).

function: lcp_newton_FB()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed
  • iparam[2] (in): if > 0, keep the work vector (reduce the number of memory allocation if the same type of problem is solved multiple times)
  • iparam[3] (in): if > 0. use a non-monotone linear search
  • iparam[4] (in): if a non-monotone linear search is used, specify the number of merit values to remember
  • dparam[0] (in): tolerance
  • dparam[1] (out): resulting error

Newton min + FB Solver

a nonsmooth Newton method based based on the minFBLSA algorithm : the descent direction is given by a min reformulation but the linesearch is done with Fischer-Burmeister (and if needed the gradient direction).

function: lcp_newton_minFB()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed
  • iparam[2] (in): if > 0, keep the work vector (reduce the number of memory allocation if the same type of problem is solved multiple times)
  • iparam[3] (in): if > 0. use a non-monotone linear search
  • iparam[4] (in): if a non-monotone linear search is used, specify the number of merit values to remember
  • dparam[0] (in): tolerance
  • dparam[1] (out): resulting error

Path (Ferris) Solver

This solver uses the external PATH solver

function: lcp_path()

parameters:

  • dparam[0] (in): tolerance

Enumerative Solver

A brute-force method to find the solution of the LCP

function: lcp_enum()

parameters:

  • iparam[0] (in): search for multiple solutions if 1
  • iparam[1] (out): key of the solution
  • iparam[1] (out): number of solutions
  • iparam[3] (in): starting key values (seed)
  • iparam[4] (in): use DGELS (1) or DGESV (0).
  • dparam[0] (in): tolerance

Latin Solver

LArge Time INcrements solver

function: lcp_latin()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed
  • dparam[0] (in): tolerance
  • dparam[1] (out): resulting error
  • dparam[2] (in): latin parameter

Latin_w Solver

LArge Time INcrements solver with relaxation

function: lcp_latin_w()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed
  • dparam[0] (in): tolerance
  • dparam[1] (out): resulting error
  • dparam[2] (in): latin parameter
  • dparam[3] (in): relaxation parameter

Block solver (Gauss Seidel)

Gauss-Seidel for Sparse-Block matrices. n Matrix M of the LCP must be a SparseBlockStructuredMatrix. n This solver first build a local problem for each row of blocks and then call any of the other solvers through lcp_driver()`.

function: lcp_nsgs_SBM()

parameters:

  • iparam[0] (in): maximum number of iterations allowed for GS process
  • iparam[1] (out): number of GS iterations processed
  • iparam[2] (out): sum of all local number of iterations (if it has sense for the local solver)
  • dparam[0] (in): tolerance
  • dparam[1] (out): resulting error
  • dparam[2] (in): sum of all local error values