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

UnrevisedLemkeSolver &	operator= (const UnrevisedLemkeSolver &)=delete

	UnrevisedLemkeSolver (UnrevisedLemkeSolver &&)=delete

UnrevisedLemkeSolver &	operator= (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 final
	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

SolverBase &	operator= (const SolverBase &)=delete

	SolverBase (SolverBase &&)=delete

SolverBase &	operator= (SolverBase &&)=delete

Public Member Functions inherited from SolverInterface
virtual	~SolverInterface ()

	SolverInterface (const SolverInterface &)=delete

SolverInterface &	operator= (const SolverInterface &)=delete

	SolverInterface (SolverInterface &&)=delete

SolverInterface &	operator= (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 (const 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 ( UnrevisedLemkeSolver< T > && )

delete

◆ UnrevisedLemkeSolver() [3/3]

UnrevisedLemkeSolver ( )

◆ ~UnrevisedLemkeSolver()

~UnrevisedLemkeSolver ( )

final

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,
		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]

MathematicalProgramResult Solve

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.

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:

drake/solvers/unrevised_lemke_solver.h

Detailed Description

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

Public Member Functions

Static Public Member Functions

Friends

Additional Inherited Members

Constructor & Destructor Documentation

◆ UnrevisedLemkeSolver() [1/3]

◆ UnrevisedLemkeSolver() [2/3]

◆ UnrevisedLemkeSolver() [3/3]

◆ ~UnrevisedLemkeSolver()

Member Function Documentation

◆ ComputeZeroTolerance()

◆ id()

◆ is_available()

◆ is_enabled()

◆ IsSolution()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ ProgramAttributesSatisfied()

◆ Solve() [1/2]

◆ Solve() [2/2]

◆ SolveLcpLemke()

Friends And Related Function Documentation

◆ UnrevisedLemkePrivateTests

◆ UnrevisedLemkePrivateTests_ConstructLemkeSolution_Test

◆ UnrevisedLemkePrivateTests_DetermineIndexSets_Test

◆ UnrevisedLemkePrivateTests_FindBlockingIndex_Test

◆ UnrevisedLemkePrivateTests_FindBlockingIndexCycling_Test

◆ UnrevisedLemkePrivateTests_FindComplementIndex_Test

◆ UnrevisedLemkePrivateTests_IsEachUnique_Test

◆ UnrevisedLemkePrivateTests_LemkePivot_Test

◆ UnrevisedLemkePrivateTests_SelectSubColumnWithCovering_Test

◆ UnrevisedLemkePrivateTests_SelectSubMatrixWithCovering_Test

◆ UnrevisedLemkePrivateTests_SelectSubVector_Test

◆ UnrevisedLemkePrivateTests_SetSubVector_Test

◆ UnrevisedLemkePrivateTests_ValidateIndices_Test

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