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

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

## ◆ UnrevisedLemkeSolver() [1/3]

 UnrevisedLemkeSolver ( const UnrevisedLemkeSolver< T > & )
delete

## ◆ UnrevisedLemkeSolver() [2/3]

 UnrevisedLemkeSolver ( UnrevisedLemkeSolver< T > && )
delete

## ◆ UnrevisedLemkeSolver() [3/3]

 UnrevisedLemkeSolver ( )

## ◆ ~UnrevisedLemkeSolver()

 ~UnrevisedLemkeSolver ( )
final

## ◆ 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, T 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] M the LCP matrix. [in] q the LCP vector. [in,out] z the 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_pivots the number of pivots used, on return. [in] zero_tol The 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::exception if 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.

## ◆ 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: