Drake
UnrevisedLemkeSolver< T > Class Template Referencefinal

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

#include <drake/solvers/unrevised_lemke_solver.h>

Public Member Functions

 UnrevisedLemkeSolver ()
 
 ~UnrevisedLemkeSolver () final
 
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...
 
MathematicalProgramResult Solve (const MathematicalProgram &prog, const std::optional< Eigen::VectorXd > &initial_guess=std::nullopt, const std::optional< SolverOptions > &solver_options=std::nullopt) const
 Like SolverInterface::Solve(), but the result is a return value instead of an output argument. More...
 
void Solve (const MathematicalProgram &, const std::optional< Eigen::VectorXd > &, const std::optional< SolverOptions > &, MathematicalProgramResult *) const override
 
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 SolverBase
 ~SolverBase () override
 
MathematicalProgramResult Solve (const MathematicalProgram &prog, const std::optional< Eigen::VectorXd > &initial_guess=std::nullopt, const std::optional< SolverOptions > &solver_options=std::nullopt) const
 Like SolverInterface::Solve(), but the result is a return value instead of an output argument. More...
 
void Solve (const MathematicalProgram &, const std::optional< Eigen::VectorXd > &, const std::optional< SolverOptions > &, MathematicalProgramResult *) const override
 Solves an optimization program with optional initial guess and solver options. More...
 
bool available () const override
 Returns true iff support for this solver has been compiled into Drake. More...
 
bool enabled () const override
 Returns true iff this solver is properly configured for use at runtime. More...
 
SolverId solver_id () const override
 Returns the identifier of this solver. More...
 
bool AreProgramAttributesSatisfied (const MathematicalProgram &) const override
 Returns true iff the program's attributes are compatible with this solver's capabilities. More...
 
std::string ExplainUnsatisfiedProgramAttributes (const MathematicalProgram &) const override
 Describes the reasons (if any) why the program is incompatible with this solver's capabilities. More...
 
 SolverBase (const SolverBase &)=delete
 
SolverBaseoperator= (const SolverBase &)=delete
 
 SolverBase (SolverBase &&)=delete
 
SolverBaseoperator= (SolverBase &&)=delete
 
- Public Member Functions inherited from SolverInterface
virtual ~SolverInterface ()
 
 SolverInterface (const SolverInterface &)=delete
 
SolverInterfaceoperator= (const SolverInterface &)=delete
 
 SolverInterface (SolverInterface &&)=delete
 
SolverInterfaceoperator= (SolverInterface &&)=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...
 
Static versions of the instance methods with similar names.
static SolverId id ()
 
static bool is_available ()
 
static bool is_enabled ()
 
static bool ProgramAttributesSatisfied (const MathematicalProgram &)
 

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
 

Additional Inherited Members

- Protected Member Functions inherited from SolverBase
 SolverBase (std::function< SolverId()> id, std::function< bool()> available, std::function< bool()> enabled, std::function< bool(const MathematicalProgram &)> are_satisfied, std::function< std::string(const MathematicalProgram &)> explain_unsatisfied=nullptr)
 Constructs a SolverBase with the given default implementations of the solver_id(), available(), enabled(), AreProgramAttributesSatisfied(), and ExplainUnsatisfiedProgramAttributes() methods. More...
 
- Protected Member Functions inherited from SolverInterface
 SolverInterface ()
 

Constructor & Destructor Documentation

◆ UnrevisedLemkeSolver() [1/3]

UnrevisedLemkeSolver ( const UnrevisedLemkeSolver< T > &  )
delete

◆ UnrevisedLemkeSolver() [2/3]

◆ UnrevisedLemkeSolver() [3/3]

◆ ~UnrevisedLemkeSolver()

Member Function Documentation

◆ ComputeZeroTolerance()

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

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

◆ id()

static SolverId id ( )
static

◆ is_available()

static bool is_available ( )
static

◆ is_enabled()

static bool is_enabled ( )
static

◆ IsSolution()

static 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.

◆ operator=() [1/2]

UnrevisedLemkeSolver& operator= ( UnrevisedLemkeSolver< T > &&  )
delete

◆ operator=() [2/2]

UnrevisedLemkeSolver& operator= ( const UnrevisedLemkeSolver< T > &  )
delete

◆ ProgramAttributesSatisfied()

static bool ProgramAttributesSatisfied ( const MathematicalProgram )
static

◆ Solve() [1/2]

void Solve
override

◆ Solve() [2/2]

Like SolverInterface::Solve(), but the result is a return value instead of an output argument.

◆ SolveLcpLemke()

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::exceptionif 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.

Friends And Related Function Documentation

◆ UnrevisedLemkePrivateTests

friend class UnrevisedLemkePrivateTests
friend

◆ UnrevisedLemkePrivateTests_ConstructLemkeSolution_Test

friend class UnrevisedLemkePrivateTests_ConstructLemkeSolution_Test
friend

◆ UnrevisedLemkePrivateTests_DetermineIndexSets_Test

friend class UnrevisedLemkePrivateTests_DetermineIndexSets_Test
friend

◆ UnrevisedLemkePrivateTests_FindBlockingIndex_Test

friend class UnrevisedLemkePrivateTests_FindBlockingIndex_Test
friend

◆ UnrevisedLemkePrivateTests_FindBlockingIndexCycling_Test

friend class UnrevisedLemkePrivateTests_FindBlockingIndexCycling_Test
friend

◆ UnrevisedLemkePrivateTests_FindComplementIndex_Test

friend class UnrevisedLemkePrivateTests_FindComplementIndex_Test
friend

◆ UnrevisedLemkePrivateTests_IsEachUnique_Test

friend class UnrevisedLemkePrivateTests_IsEachUnique_Test
friend

◆ UnrevisedLemkePrivateTests_LemkePivot_Test

friend class UnrevisedLemkePrivateTests_LemkePivot_Test
friend

◆ UnrevisedLemkePrivateTests_SelectSubColumnWithCovering_Test

friend class UnrevisedLemkePrivateTests_SelectSubColumnWithCovering_Test
friend

◆ UnrevisedLemkePrivateTests_SelectSubMatrixWithCovering_Test

friend class UnrevisedLemkePrivateTests_SelectSubMatrixWithCovering_Test
friend

◆ UnrevisedLemkePrivateTests_SelectSubVector_Test

friend class UnrevisedLemkePrivateTests_SelectSubVector_Test
friend

◆ UnrevisedLemkePrivateTests_SetSubVector_Test

friend class UnrevisedLemkePrivateTests_SetSubVector_Test
friend

◆ UnrevisedLemkePrivateTests_ValidateIndices_Test

friend class UnrevisedLemkePrivateTests_ValidateIndices_Test
friend

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