File numerics/src/LCP/LCP_Solvers.h¶
Go to the source code of this file
Subroutines for the resolution of Linear Complementarity Problems.
See detailed documentation in LCP available solvers
Functions

void lcp_qp(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_qp uses a quadratic programm formulation for solving a LCP
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence / minimization sucessfull 1 : Too Many iterations 2 : Accuracy insuficient to satisfy convergence criterion 5 : Length of working array insufficient Other : The constraints are inconstent
options – [inout] structure used to define the solver and its parameters.

void lcp_cpg(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_cpg is a CPG (Conjugated Projected Gradient) solver for LCP based on quadratic minimization.
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0: convergence 1: iter = itermax 2: negative diagonal term 3: pWp nul
options – [inout] structure used to define the solver and its parameters.

void lcp_pgs(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_pgs (Projected GaussSeidel) is a basic Projected GaussSeidel solver for LCP.
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : negative diagonal term
options – [inout] structure used to define the solver and its parameters.

void lcp_rpgs(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_rpgs (Regularized Projected GaussSeidel ) is a solver for LCP, able to handle matrices with null diagonal terms.
 Todo:
Sizing the regularization paramter and apply it only on null diagnal term
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : negative diagonal term
options – [inout] structure used to define the solver and its parameters.

void lcp_psor(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_psor Projected Succesive over relaxation solver for LCP.
See cottle, Pang Stone Chap 5
 Todo:
use the relax parameter
add test
add a vector of relaxation parameter wtith an auto sizing (see SOR algorithm for linear solver.)
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : negative diagonal term
options – [inout] structure used to define the solver and its parameters.

void lcp_nsqp(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_nsqp use a quadratic programm formulation for solving an non symmetric LCP
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence / minimization sucessfull 1 : Too Many iterations 2 : Accuracy insuficient to satisfy convergence criterion 5 : Length of working array insufficient Other : The constraints are inconstent
options – [inout] structure used to define the solver and its parameters.

void lcp_latin(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_latin (LArge Time INcrements) is a basic latin solver for LCP.
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : Cholesky Factorization failed 3 : nul diagonal term
options – [inout] structure used to define the solver and its parameters.

void lcp_latin_w(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_latin_w (LArge Time INcrements) is a basic latin solver with relaxation for LCP.
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : Cholesky Factorization failed 3 : nul diagonal term
options – [inout] structure used to define the solver and its parameters.

void lcp_lexicolemke(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_lexicolemke is a direct solver for LCP based on pivoting method principle for degenerate problem Choice of pivot variable is performed via lexicographic ordering Ref: “The Linear Complementarity Problem” Cottle, Pang, Stone (1992)
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : negative diagonal term
options – [inout] structure used to define the solver and its parameters.

void lcp_newton_min(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_newton_min uses a nonsmooth Newton method based on the min formulation (or max formulation) of the LCP
 Todo:
Optimizing the memory allocation (Try to avoid the copy of JacH into A)
Add rules for the computation of the penalization rho
Add a globalization strategy based on a decrease of a merit function. (Nonmonotone LCP) Reference in Ferris Kanzow 2002
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence / minimization sucessfull 1 : Too Many iterations 2 : Accuracy insuficient to satisfy convergence criterion 5 : Length of working array insufficient Other : The constraints are inconstent
options – [inout] structure used to define the solver and its parameters.

void lcp_newton_FB(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_newton_FB use a nonsmooth newton method based on the FischerBursmeister convex function
 Todo:
Optimizing the memory allocation (Try to avoid the copy of JacH into A)
Add rules for the computation of the penalization rho
Add a globalization strategy based on a decrease of a merit function. (Nonmonotone LCP) Reference in Ferris Kanzow 2002
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0  convergence 1  iter = itermax 2  failure in the descent direction search (in LAPACK)
options – [inout] structure used to define the solver and its parameters.

void lcp_newton_minFB(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_newton_minFB use a nonsmooth newton method based on both a min and FischerBursmeister reformulation References: Facchinei—Pang (2003)
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0  convergence 1  iter = itermax 2  failure in the descent direction search (in LAPACK)
options – [inout] structure used to define the solver and its parameters.

void lcp_path(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
path solver
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : negative diagonal term
options – [inout] structure used to define the solver and its parameters.

void lcp_enum(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
enumerative solver
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : success 1 : failed
options – [inout] structure used to define the solver and its parameters.

void lcp_enum_init(LinearComplementarityProblem *problem, SolverOptions *options, int withMemAlloc)¶
Proceed with initialisation required before any call of the enum solver.
 Parameters
problem – [in] structure that represents the LCP (M, q…)
options – [inout] structure used to define the solver and its parameters.
withMemAlloc – [in] If it is not 0, then the necessary work memory is allocated.

void lcp_enum_reset(LinearComplementarityProblem *problem, SolverOptions *options, int withMemAlloc)¶
Reset state for enum solver parameters.
 Parameters
problem – [in] structure that represents the LCP (M, q…)
options – [inout] structure used to define the solver and its parameters.
withMemAlloc – [in] If it is not 0, then the work memory is free.

void lcp_avi_caoferris(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_avi_caoferris is a direct solver for LCP based on an Affine Variational Inequalities (AVI) reformulation The AVI solver is here the one from Cao and Ferris Ref: “A Pivotal Method for Affine Variational Inequalities” Menglin Cao et Michael Ferris (1996)
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax
options – [inout] structure used to define the solver and its parameters.

void lcp_pivot(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_pivot is a direct solver for LCP based on a pivoting method It can currently use Bard, Murty’s leastindex or Lemke rule for choosing the pivot.
The default one is Lemke and it can be changed by setting iparam[SICONOS_LCP_IPARAM_PIVOTING_METHOD_TYPE]. The list of choices are in the enum LCP_PIVOT (see lcp_cst.h).
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax
options – [inout] structure used to define the solver and its parameters.

void lcp_pivot_covering_vector(LinearComplementarityProblem *problem, double *u, double *s, int *info, SolverOptions *options, double *cov_vec)¶

void lcp_pivot_lumod(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶

void lcp_pivot_lumod_covering_vector(LinearComplementarityProblem *problem, double *u, double *s, int *info, SolverOptions *options, double *cov_vec)¶

void lcp_pathsearch(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_pathsearch is a direct solver for LCP based on the pathsearch algorithm
Warning
this solver is available for testing purposes only! consider using lcp_pivot() if you are looking for simular solvers
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax
options – [inout] structure used to define the solver and its parameters.

void lcp_gams(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
lcp_gams uses the solver provided by GAMS
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – [out] an integer which returns the termination value: 0 : convergence 1 : iter = itermax
options – [inout] structure used to define the solver and its parameters.

void lcp_nsgs_SBM(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶
generic interface used to call any LCP solver applied on a SparseBlock structured matrix M, with a GaussSeidel process to solve the global problem (formulation/solving of local problems for each row of blocks)
 Parameters
problem – [in] structure that represents the LCP (M, q…). M must be a SparseBlockStructuredMatrix
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
info – an integer which returns the termination value: 0 : convergence >0 : failed, depends on local solver
options – [inout] structure used to define the solver and its parameters.

void lcp_nsgs_SBM_buildLocalProblem(int rowNumber, SparseBlockStructuredMatrix *const blmat, LinearComplementarityProblem *local_problem, double *q, double *z)¶
Construct local problem from a “global” one.
 Parameters
rowNumber – index of the local problem
blmat – matrix containing the problem
local_problem – problem to fill
q – big q
z – big z

int lcp_compute_error(LinearComplementarityProblem *problem, double *z, double *w, double tolerance, double *error)¶
Computes error criterion and update \( w = Mz + q \).
 Parameters
problem – [in] structure that represents the LCP (M, q…)
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
tolerance – [in] threshold used to validate the solution: if the error is less than this value, the solution is accepted
error – [out] the actual error of the solution with respect to the problem
 Returns
status: 0 : convergence, 1: error > tolerance

void lcp_compute_error_only(unsigned int n, double *z, double *w, double *error)¶
Computes error criterion.
 Parameters
n – [in] size of the LCP
z – [inout] a nvector of doubles which contains the initial solution and returns the solution of the problem.
w – [inout] a nvector of doubles which returns the solution of the problem.
error – [out] the result of the computation

int lcp_driver_DenseMatrix(LinearComplementarityProblem *problem, double *z, double *w, SolverOptions *options)¶
Interface to solvers for Linear Complementarity Problems, dedicated to dense matrix storage.
 Parameters
problem – [in] the LinearComplementarityProblem structure which handles the problem (M,q)
z – [inout] a nvector of doubles which contains the solution of the problem.
w – [inout] a nvector of doubles which contains the solution of the problem.
options – [inout] structure used to define the solver(s) and their parameters
 Returns
info termination value
0 : successful
>0 : otherwise see each solver for more information about the log info

void lcp_ConvexQP_ProjectedGradient(LinearComplementarityProblem *problem, double *reaction, double *velocity, int *info, SolverOptions *options)¶

void lcp_lexicolemke_set_default(SolverOptions *options)¶

void lcp_nsgs_sbm_set_default(SolverOptions *options)¶

void lcp_latin_set_default(SolverOptions *options)¶

void lcp_latin_w_set_default(SolverOptions *options)¶

void lcp_newton_FB_set_default(SolverOptions *options)¶

void lcp_psor_set_default(SolverOptions *options)¶

void lcp_rpgs_set_default(SolverOptions *options)¶

void lcp_enum_set_default(SolverOptions *options)¶

void lcp_pivot_set_default(SolverOptions *options)¶

void lcp_pathsearch_set_default(SolverOptions *options)¶

void lcp_pivot_lumod_set_default(SolverOptions *options)¶