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).
|
| | 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.
|
| | UnrevisedLemkeSolver (const UnrevisedLemkeSolver &)=delete |
| UnrevisedLemkeSolver & | operator= (const UnrevisedLemkeSolver &)=delete |
| | UnrevisedLemkeSolver (UnrevisedLemkeSolver &&)=delete |
| UnrevisedLemkeSolver & | operator= (UnrevisedLemkeSolver &&)=delete |
| | ~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.
|
| bool | available () const override |
| | Returns true iff support for this solver has been compiled into Drake.
|
| bool | enabled () const override |
| | Returns true iff this solver is properly configured for use at runtime.
|
| SolverId | solver_id () const final |
| | Returns the identifier of this solver.
|
| bool | AreProgramAttributesSatisfied (const MathematicalProgram &) const override |
| | Returns true iff the program's attributes are compatible with this solver's capabilities.
|
| std::string | ExplainUnsatisfiedProgramAttributes (const MathematicalProgram &) const override |
| | Describes the reasons (if any) why the program is incompatible with this solver's capabilities.
|
| | SolverBase (const SolverBase &)=delete |
| SolverBase & | operator= (const SolverBase &)=delete |
| | SolverBase (SolverBase &&)=delete |
| SolverBase & | operator= (SolverBase &&)=delete |
| virtual | ~SolverInterface () |
| | SolverInterface (const SolverInterface &)=delete |
| SolverInterface & | operator= (const SolverInterface &)=delete |
| | SolverInterface (SolverInterface &&)=delete |
| SolverInterface & | operator= (SolverInterface &&)=delete |
Solves an optimization program with optional initial guess and solver options.
Note that these initial guess and solver options are not written to prog. If the prog has set an initial guess, and initial_guess is set, then initial_guess takes priority. If the prog has set an option for a solver, and solver_options contains a different value for the same option on the same solver, then solver_options takes priority. Derived implementations of this interface may elect to throw std::exception for badly formed programs.
Reimplemented from SolverBase.
template<class T>
| 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.
