Drake
UnrevisedLemkeSolver< T > Class Template Reference

A class for the Unrevised Implementation of Lemke Algorithm's for solving Linear Complementarity Problems (LCPs). More...

#include <drake/solvers/unrevised_lemke_solver.h>

Inheritance diagram for UnrevisedLemkeSolver< T >:
[legend]
Collaboration diagram for UnrevisedLemkeSolver< T >:
[legend]

Public Member Functions

 UnrevisedLemkeSolver ()=default
 
 ~UnrevisedLemkeSolver () override=default
 
bool SolveLcpLemke (const MatrixX< T > &M, const VectorX< T > &q, VectorX< T > *z, int *num_pivots, const T &zero_tol=T(-1)) const
 Lemke's Algorithm for solving LCPs in the matrix class E, which contains all strictly semimonotone matrices, all P-matrices, and all strictly copositive matrices. More...
 
bool available () const override
 Returns true iff this solver was enabled at compile-time. More...
 
SolutionResult Solve (MathematicalProgram &prog) const override
 Sets values for the decision variables on the given MathematicalProgram prog, or: More...
 
SolverId solver_id () const override
 Returns the identifier of this solver. More...
 
template<>
SolutionResult Solve (MathematicalProgram &) const
 Sets values for the decision variables on the given MathematicalProgram prog, or: More...
 
template<>
SolutionResult Solve (MathematicalProgram &) const
 Sets values for the decision variables on the given MathematicalProgram prog, or: More...
 
Does not allow copy, move, or assignment
 UnrevisedLemkeSolver (const UnrevisedLemkeSolver &)=delete
 
UnrevisedLemkeSolveroperator= (const UnrevisedLemkeSolver &)=delete
 
 UnrevisedLemkeSolver (UnrevisedLemkeSolver &&)=delete
 
UnrevisedLemkeSolveroperator= (UnrevisedLemkeSolver &&)=delete
 
- Public Member Functions inherited from MathematicalProgramSolverInterface
 MathematicalProgramSolverInterface ()=default
 
virtual ~MathematicalProgramSolverInterface ()=default
 
 MathematicalProgramSolverInterface (const MathematicalProgramSolverInterface &)=delete
 
MathematicalProgramSolverInterfaceoperator= (const MathematicalProgramSolverInterface &)=delete
 
 MathematicalProgramSolverInterface (MathematicalProgramSolverInterface &&)=delete
 
MathematicalProgramSolverInterfaceoperator= (MathematicalProgramSolverInterface &&)=delete
 

Static Public Member Functions

template<class U >
static U ComputeZeroTolerance (const MatrixX< U > &M)
 Calculates the zero tolerance that the solver would compute if the user does not specify a tolerance. More...
 
static bool IsSolution (const MatrixX< T > &M, const VectorX< T > &q, const VectorX< T > &z, T zero_tol=-1)
 Checks whether a given candidate solution to the LCP Mz + q = w, z ≥ 0, w ≥ 0, zᵀw = 0 is satisfied to a given tolerance. More...
 

Friends

class UnrevisedLemkePrivateTests
 
class UnrevisedLemkePrivateTests_SelectSubMatrixWithCovering_Test
 
class UnrevisedLemkePrivateTests_SelectSubColumnWithCovering_Test
 
class UnrevisedLemkePrivateTests_SelectSubVector_Test
 
class UnrevisedLemkePrivateTests_SetSubVector_Test
 
class UnrevisedLemkePrivateTests_ValidateIndices_Test
 
class UnrevisedLemkePrivateTests_IsEachUnique_Test
 
class UnrevisedLemkePrivateTests_LemkePivot_Test
 
class UnrevisedLemkePrivateTests_ConstructLemkeSolution_Test
 
class UnrevisedLemkePrivateTests_DetermineIndexSets_Test
 
class UnrevisedLemkePrivateTests_FindBlockingIndex_Test
 
class UnrevisedLemkePrivateTests_FindBlockingIndexCycling_Test
 
class UnrevisedLemkePrivateTests_FindComplementIndex_Test
 

Detailed Description

template<class T>
class drake::solvers::UnrevisedLemkeSolver< T >

A class for the Unrevised Implementation of Lemke Algorithm's for solving Linear Complementarity Problems (LCPs).

See MobyLcpSolver for a description of LCPs. This code makes extensive use of the following document: [Dai 2018] Dai, H. and Drumwright, E. Computing the Principal Pivoting Transform for Solving Linear Complementarity Problems with Lemke's Algorithm. (2018, located in doc/pivot_column.pdf).

Constructor & Destructor Documentation

UnrevisedLemkeSolver ( const UnrevisedLemkeSolver< T > &  )
delete
UnrevisedLemkeSolver ( )
default
~UnrevisedLemkeSolver ( )
overridedefault

Member Function Documentation

bool available ( ) const
inlineoverridevirtual

Returns true iff this solver was enabled at compile-time.

Implements MathematicalProgramSolverInterface.

static U ComputeZeroTolerance ( const MatrixX< U > &  M)
inlinestatic

Calculates the zero tolerance that the solver would compute if the user does not specify a tolerance.

Here is the caller graph for this function:

bool IsSolution ( const MatrixX< T > &  M,
const VectorX< T > &  q,
const VectorX< T > &  z,
zero_tol = -1 
)
static

Checks whether a given candidate solution to the LCP Mz + q = w, z ≥ 0, w ≥ 0, zᵀw = 0 is satisfied to a given tolerance.

If the tolerance is non-positive, this method computes a reasonable tolerance using M.

Here is the call graph for this function:

Here is the caller graph for this function:

UnrevisedLemkeSolver& operator= ( UnrevisedLemkeSolver< T > &&  )
delete
UnrevisedLemkeSolver& operator= ( const UnrevisedLemkeSolver< T > &  )
delete
SolutionResult Solve ( MathematicalProgram prog) const
virtual

Sets values for the decision variables on the given MathematicalProgram prog, or:

  • If no solver is available, throws std::runtime_error
  • If the solver returns an error, returns a nonzero SolutionResult.

Implements MathematicalProgramSolverInterface.

SolutionResult Solve ( MathematicalProgram prog) const
virtual

Sets values for the decision variables on the given MathematicalProgram prog, or:

  • If no solver is available, throws std::runtime_error
  • If the solver returns an error, returns a nonzero SolutionResult.

Implements MathematicalProgramSolverInterface.

SolutionResult Solve ( MathematicalProgram prog) const
overridevirtual

Sets values for the decision variables on the given MathematicalProgram prog, or:

  • If no solver is available, throws std::runtime_error
  • If the solver returns an error, returns a nonzero SolutionResult.

Implements MathematicalProgramSolverInterface.

Here is the call graph for this function:

bool SolveLcpLemke ( const MatrixX< T > &  M,
const VectorX< T > &  q,
VectorX< T > *  z,
int num_pivots,
const T &  zero_tol = T(-1) 
) const

Lemke's Algorithm for solving LCPs in the matrix class E, which contains all strictly semimonotone matrices, all P-matrices, and all strictly copositive matrices.

The solver can be applied with occasional success to problems outside of its guaranteed matrix classes. Lemke's Algorithm is described in [Cottle 1992], Section 4.4.

The solver will denote failure on return if it exceeds a problem-size dependent number of iterations.

Parameters
[in]Mthe LCP matrix.
[in]qthe LCP vector.
[in,out]zthe solution to the LCP on return (if the solver succeeds). If the length of z is equal to the length of q, the solver will attempt to use the basis from the last solution. This strategy can prove exceptionally fast if solutions differ little between successive calls. If the solver fails (returns false), z will be set to the zero vector on return.
[out]num_pivotsthe number of pivots used, on return.
[in]zero_tolThe tolerance for testing against zero. If the tolerance is negative (default) the solver will determine a generally reasonable tolerance.
Returns
true if the solver computes a solution to floating point tolerances (i.e., if IsSolution() returns true on the problem) and false otherwise.
Exceptions
std::logic_errorif M is not square or the dimensions of M do not match the length of q.
  • [Cottle 1992] R. Cottle, J.-S. Pang, and R. Stone. The Linear Complementarity Problem. Academic Press, 1992.

Here is the call graph for this function:

Here is the caller graph for this function:

SolverId solver_id ( ) const
overridevirtual

Returns the identifier of this solver.

Implements MathematicalProgramSolverInterface.

Here is the call graph for this function:

Friends And Related Function Documentation

friend class UnrevisedLemkePrivateTests
friend
friend class UnrevisedLemkePrivateTests_ConstructLemkeSolution_Test
friend
friend class UnrevisedLemkePrivateTests_DetermineIndexSets_Test
friend
friend class UnrevisedLemkePrivateTests_FindBlockingIndex_Test
friend
friend class UnrevisedLemkePrivateTests_FindBlockingIndexCycling_Test
friend
friend class UnrevisedLemkePrivateTests_FindComplementIndex_Test
friend
friend class UnrevisedLemkePrivateTests_IsEachUnique_Test
friend
friend class UnrevisedLemkePrivateTests_LemkePivot_Test
friend
friend class UnrevisedLemkePrivateTests_SelectSubColumnWithCovering_Test
friend
friend class UnrevisedLemkePrivateTests_SelectSubMatrixWithCovering_Test
friend
friend class UnrevisedLemkePrivateTests_SelectSubVector_Test
friend
friend class UnrevisedLemkePrivateTests_SetSubVector_Test
friend
friend class UnrevisedLemkePrivateTests_ValidateIndices_Test
friend

The documentation for this class was generated from the following files: