Go to the source code of this file
Subroutines for the resolution of Linear Complementarity Problems.
Functions
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)
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax options
: structure used to define the solver and its parameters. lcp_compute_error
(LinearComplementarityProblem *problem, double *z, double *w, double tolerance, double *error)¶This function computes the input vector \( w = Mz + q \) and checks the validity of the vector z as a solution of the LCP : \( 0 \le z \perp Mz + q \ge 0 \) The criterion is based on \( \sum [ (z[i]*(Mz+q)[i])_{pos} + (z[i])_{neg} + (Mz+q)[i])_{neg} ] \) with \( x_{pos} = max(0,x) \) and \( xneg = max(0,-x)\).
This sum is divided by \( \|q\| \) and then compared to tol.
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. tolerance
: threshold used to validate the solution: if the error is less than this value, the solution is accepted error
: the actual error of the solution with respect to the problem lcp_compute_error_only
(unsigned int n, double *z, double *w, double *error)¶This function computes the input vector \( w = Mz + q \) and checks the validity of the vector z as a solution of the LCP : \( 0 \le z \perp Mz + q \ge 0 \) The criterion is based on \( \sum [ (z[i]*(Mz+q)[i])_{pos} + (z[i])_{neg} + (Mz+q)[i])_{neg} ] \) with \( x_{pos} = max(0,x) \) and \( xneg = max(0,-x)\).
This sum is divided by \( \|q\| \) and then compared to tol.
n
: size of the LCP z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. error
: the result of the computation lcp_ConvexQP_ProjectedGradient
(LinearComplementarityProblem *problem, double *reaction, double *velocity, int *info, SolverOptions *options)¶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.
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0: convergence 1: iter = itermax 2: negative diagonal term 3: pWp nul options
: structure used to define the solver and its parameters. lcp_driver_DenseMatrix
(LinearComplementarityProblem *problem, double *z, double *w, SolverOptions *options)¶Interface to solvers for Linear Complementarity Problems, dedicated to dense matrix storage.
problem
: the LinearComplementarityProblem structure which handles the problem (M,q) z
: a n-vector of doubles which contains the solution of the problem. w
: a n-vector of doubles which contains the solution of the problem. options
: structure used to define the solver(s) and their parameters lcp_enum
(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶enumerative solver
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : success 1 : failed options
: structure used to define the solver and its parameters. lcp_enum_init
(LinearComplementarityProblem *problem, SolverOptions *options, int withMemAlloc)¶problem
: structure that represents the LCP (M, q…) options
: structure used to define the solver and its parameters. withMemAlloc
: If it is not 0, then the necessary work memory is allocated. lcp_enum_reset
(LinearComplementarityProblem *problem, SolverOptions *options, int withMemAlloc)¶problem
: structure that represents the LCP (M, q…) options
: structure used to define the solver and its parameters. withMemAlloc
: If it is not 0, then the work memory is free. lcp_gams
(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶lcp_gams uses the solver provided by GAMS
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax options
: structure used to define the solver and its parameters. lcp_latin
(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶lcp_latin (LArge Time INcrements) is a basic latin solver for LCP.
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : Cholesky Factorization failed 3 : nul diagonal term options
: structure used to define the solver and its parameters. 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.
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : Cholesky Factorization failed 3 : nul diagonal term options
: structure used to define the solver and its parameters. 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)
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : negative diagonal term options
: structure used to define the solver and its parameters. lcp_newton_FB
(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶lcp_newton_FB use a nonsmooth newton method based on the Fischer-Bursmeister convex function
\( 0 \le z \perp w \ge 0 \Longrightarrow \phi(z,w)=\sqrt{z^2+w^2}-(z+w)=0 \)
\( \Phi(z) = \left[ \begin{array}{c} \phi(z_1,w_1) \\ \phi(z_1,w_1) \\ \vdots \\ \phi(z_n,w_n) \end{array}\right] =0\\ \)
References: Alart & Curnier 1990, Pang 1990
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 - convergence 1 - iter = itermax 2 - failure in the descent direction search (in LAPACK)options
: structure used to define the solver and its parameters. 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 \( 0 \le z \perp w \ge 0 \Longrightarrow \min(w,\rho z)=0 \Longrightarrow w = \max(0,w - \rho z) \)
\( H(z) = H(\left[ \begin{array}{c} z \\ w \end{array}\right])= \left[ \begin{array}{c} w-Mz-q \\ min(w,\rho z) \end{array}\right] =0\\ \)
References: Alart & Curnier 1990, Pang 1990
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : Problem in resolution in DGESV 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
: structure used to define the solver and its parameters.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 Fischer-Bursmeister reformulation References: FacchineiPang (2003)
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 - convergence 1 - iter = itermax 2 - failure in the descent direction search (in LAPACK)options
: structure used to define the solver and its parameters. lcp_nsgs_SBM
(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶generic interface used to call any LCP solver applied on a Sparse-Block structured matrix M, with a Gauss-Seidel process to solve the global problem (formulation/solving of local problems for each row of blocks)
problem
: structure that represents the LCP (M, q…). M must be a SparseBlockStructuredMatrix z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector 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
: structure used to define the solver and its parameters. lcp_nsgs_SBM_buildLocalProblem
(int rowNumber, SparseBlockStructuredMatrix *const blmat, LinearComplementarityProblem *local_problem, double *q, double *z)¶Construct local problem from a “global” one.
rowNumber
: index of the local problem blmat
: matrix containing the problem local_problem
: problem to fill q
: big q z
: big z 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
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: 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
: structure used to define the solver and its parameters. lcp_path
(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : negative diagonal term options
: structure used to define the solver and its parameters. 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
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax options
: structure used to define the solver and its parameters. lcp_pgs
(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶lcp_pgs (Projected Gauss-Seidel) is a basic Projected Gauss-Seidel solver for LCP.
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : negative diagonal term options
: structure used to define the solver and its parameters. 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 least-index or Lemke rule for choosing the pivot.
The default one is Lemke and it cam be changed by setting iparam[2]. The list of choices are in the enum LCP_PIVOT (see lcp_cst.h).
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax options
: structure used to define the solver and its parameters. lcp_pivot_covering_vector
(LinearComplementarityProblem *problem, double *u, double *s, int *info, SolverOptions *options, double *cov_vec)¶lcp_pivot_lumod
(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶lcp_pivot_lumod_covering_vector
(LinearComplementarityProblem *problem, double *u, double *s, int *info, SolverOptions *options, double *cov_vec)¶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
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : negative diagonal term options
: structure used to define the solver and its parameters. lcp_qp
(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶lcp_qp uses a quadratic programm formulation for solving a LCP
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: 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
: structure used to define the solver and its parameters. lcp_rpgs
(LinearComplementarityProblem *problem, double *z, double *w, int *info, SolverOptions *options)¶lcp_rpgs (Regularized Projected Gauss-Seidel ) is a solver for LCP, able to handle matrices with null diagonal terms.
problem
: structure that represents the LCP (M, q…) z
: a n-vector of doubles which contains the initial solution and returns the solution of the problem. w
: a n-vector of doubles which returns the solution of the problem. info
: an integer which returns the termination value: 0 : convergence 1 : iter = itermax 2 : negative diagonal term options
: structure used to define the solver and its parameters.linearComplementarity_ConvexQP_ProjectedGradient_setDefaultSolverOptions
(SolverOptions *options)¶linearComplementarity_cpg_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_enum_setDefaultSolverOptions
(LinearComplementarityProblem *problem, SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
problem
: structure that represents the LCP (M, q…) options
: the pointer to the array of options to set linearComplementarity_latin_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_latin_w_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_lexicolemke_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_newton_min_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_nsgs_SBM_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_nsqp_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_pgs_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_psor_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_qp_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_rpgs_setDefaultSolverOptions
(SolverOptions *options)¶set the default solver parameters and perform memory allocation for LinearComplementarity
options
: the pointer to the array of options to set linearComplementarity_setDefaultSolverOptions
(LinearComplementarityProblem *problem, SolverOptions *options, int)¶set the default solver parameters and perform memory allocation for LinearComplementarity
problem
: the LinearComplementarityProblem structure which handles the problem (M,q) options
: the pointer to the array of options to set