Drake
drake::solvers Namespace Reference

Namespaces

 detail
 
 internal
 
 test
 

Classes

struct  AddRotationMatrixBoxSphereIntersectionReturn
 Some of the newly added variables in function AddRotationMatrixBoxSphereIntersectionMilpConstraints. More...
 
class  Binding
 A binding on constraint type C is a mapping of the decision variables onto the inputs of C. More...
 
class  BoundingBoxConstraint
 Implements a constraint of the form lb <= x <= ub . More...
 
class  Constraint
 A constraint is a function + lower and upper bounds. More...
 
class  Cost
 Provides an abstract base for all costs. More...
 
class  DrealSolver
 
class  EqualityConstrainedQPSolver
 
class  EvaluatorBase
 Provides an abstract interface to represent an expression, mapping a fixed or dynamic number of inputs to a fixed number of outputs, that may be evaluated on a scalar type of double or AutoDiffXd. More...
 
class  EvaluatorConstraint
 A constraint that may be specified using another (potentially nonlinear) evaluator. More...
 
class  EvaluatorCost
 A cost that may be specified using another (potentially nonlinear) evaluator. More...
 
class  ExpressionConstraint
 Impose a generic (potentially nonlinear) constraint represented as a vector of symbolic Expression. More...
 
class  FunctionEvaluator
 An evaluator that may be specified using a callable object. More...
 
class  GurobiSolver
 
class  IpoptSolver
 
class  LinearComplementarityConstraint
 Implements a constraint of the form: More...
 
class  LinearConstraint
 Implements a constraint of the form lb <= Ax <= ub . More...
 
class  LinearCost
 Implements a cost of the form a'x + b . More...
 
class  LinearEqualityConstraint
 Implements a constraint of the form Ax = b . More...
 
class  LinearMatrixInequalityConstraint
 Impose the matrix inequality constraint on variable x

\[ F_0 + x_1 F_1 + ... + x_n F_n \text{ is p.s.d} \]

where p.s.d stands for positive semidefinite. More...

 
class  LinearSystemSolver
 
struct  LogarithmicSos2NewBinaryVariables
 The size of the new binary variables in the compile time, for Special Ordered Set of type 2 (SOS2) constraint. More...
 
struct  LogarithmicSos2NewBinaryVariables< Eigen::Dynamic >
 
class  LorentzConeConstraint
 Constraining the linear expression \( z=Ax+b \) lies within the Lorentz cone. More...
 
class  MathematicalProgram
 MathematicalProgram stores the decision variables, the constraints and costs of an optimization problem. More...
 
class  MathematicalProgramSolverInterface
 Interface used by implementations of individual solvers. More...
 
class  MixedIntegerBranchAndBound
 Given a mixed-integer optimization problem (MIP) (or more accurately, mixed binary problem), solve this problem through branch-and-bound process. More...
 
class  MixedIntegerBranchAndBoundNode
 A node in the branch-and-bound (bnb) tree. More...
 
class  MixedIntegerRotationConstraintGenerator
 We relax the non-convex SO(3) constraint on rotation matrix R to mixed-integer linear constraints. More...
 
class  MobyLCPSolver
 A class for solving Linear Complementarity Problems (LCPs). More...
 
class  MobyLcpSolverId
 Non-template class for MobyLcpSolver<T> constants. More...
 
class  MosekSolver
 
struct  NewSymmetricVariableNames
 
struct  NewVariableNames
 
struct  NewVariableNames< Eigen::Dynamic >
 
struct  NewVariableNames< Rows, Cols >
 
struct  NewVariableNames< Size >
 The type of the names for the newly added variables. More...
 
class  NloptSolver
 
class  OsqpSolver
 
class  PolynomialConstraint
 lb[i] <= Pi <= ub[i], where each P[i] is a multivariate polynomial in x, y... More...
 
class  PolynomialCost
 Implements a cost of the form P(x, y...) where P is a multivariate polynomial in x, y, ... More...
 
class  PolynomialEvaluator
 Implements an evaluator of the form P(x, y...) where P is a multivariate polynomial in x, y, ... More...
 
class  PositiveSemidefiniteConstraint
 Implements a positive semidefinite constraint on a symmetric matrix S

\[\text{ S is p.s.d }\]

namely, all eigen values of S are non-negative. More...

 
class  QuadraticConstraint
 lb ≤ .5 xᵀQx + bᵀx ≤ ub Without loss of generality, the class stores a symmetric matrix Q. More...
 
class  QuadraticCost
 Implements a cost of the form .5 x'Qx + b'x + c . More...
 
class  RotatedLorentzConeConstraint
 Constraining that the linear expression \( z=Ax+b \) lies within rotated Lorentz cone. More...
 
class  ScsSolver
 
class  SnoptSolver
 
class  SolverId
 Identifies a MathematicalProgramSolverInterface implementation. More...
 
class  SolverResult
 This class is used by implementations of the class MathematicalProgramSolverInterface to report their results to the mathematical program. More...
 
class  SolverTypeConverter
 Converts between SolverType and SolverId. More...
 
class  SystemIdentification
 Utility functions for system identification. More...
 
class  UnrevisedLemkeSolver
 A class for the Unrevised Implementation of Lemke Algorithm's for solving Linear Complementarity Problems (LCPs). More...
 
class  UnrevisedLemkeSolverId
 Non-template class for UnrevisedLemkeSolver<T> constants. More...
 
class  VisualizationCallback
 Defines a simple evaluator with no outputs that takes a callback function pointer. More...
 

Typedefs

using MapVarToIndex = unordered_map< Variable::Id, int >
 
template<int rows, int cols>
using MatrixDecisionVariable = Eigen::Matrix< symbolic::Variable, rows, cols >
 
template<int rows>
using VectorDecisionVariable = MatrixDecisionVariable< rows, 1 >
 
using MatrixXDecisionVariable = MatrixDecisionVariable< Eigen::Dynamic, Eigen::Dynamic >
 
using VectorXDecisionVariable = VectorDecisionVariable< Eigen::Dynamic >
 
using VariableRefList = std::list< Eigen::Ref< const VectorXDecisionVariable >>
 
template<int rows, int cols>
using MatrixIndeterminate = Eigen::Matrix< symbolic::Variable, rows, cols >
 MatrixIndeterminate<int, int> is used as an alias for Eigen::Matrix<symbolic::Variable, int, int>. More...
 
template<int rows>
using VectorIndeterminate = MatrixIndeterminate< rows, 1 >
 VectorIndeterminate<int> is used as an alias for Eigen::Matrix<symbolic::Variable, int, 1>. More...
 
using MatrixXIndeterminate = MatrixIndeterminate< Eigen::Dynamic, Eigen::Dynamic >
 MatrixXIndeterminate is used as an alias for Eigen::Matrix<symbolic::Variable, Eigen::Dynamic, Eigen::Dynamic>. More...
 
using VectorXIndeterminate = VectorIndeterminate< Eigen::Dynamic >
 VectorXIndeterminate is used as an alias for Eigen::Matrix<symbolic::Variable, Eigen::Dynamic, 1>. More...
 
using IndeterminatesRefList = std::list< Eigen::Ref< const VectorXIndeterminate >>
 
typedef uint32_t AttributesSet
 
typedef uint32_t RollPitchYawLimits
 

Enumerations

enum  ProgramAttributes {
  kNoCapabilities = 0, kError = 1 << 0, kGenericCost = 1 << 1, kGenericConstraint = 1 << 2,
  kQuadraticCost = 1 << 3, kQuadraticConstraint = 1 << 4, kLinearCost = 1 << 5, kLinearConstraint = 1 << 6,
  kLinearEqualityConstraint = 1 << 7, kLinearComplementarityConstraint = 1 << 8, kLorentzConeConstraint = 1 << 9, kRotatedLorentzConeConstraint = 1 << 10,
  kPositiveSemidefiniteConstraint = 1 << 11, kBinaryVariable = 1 << 12, kCallback = 1 << 13
}
 
enum  SolutionResult {
  kSolutionFound = 0, kInvalidInput = -1, kInfeasibleConstraints = -2, kUnbounded = -3,
  kUnknownError = -4, kInfeasible_Or_Unbounded, kIterationLimit = -6, kDualInfeasible = -7
}
 
enum  IntervalBinning { kLogarithmic, kLinear }
 For a continuous variable whose range is cut into small intervals, we will use binary variables to represent which interval the continuous variable is in. More...
 
enum  RollPitchYawLimitOptions {
  kNoLimits = 0, kRPYError = 1 << 0, kRoll_NegPI_2_to_PI_2 = 1 << 1, kRoll_0_to_PI = 1 << 2,
  kPitch_NegPI_2_to_PI_2 = 1 << 3, kPitch_0_to_PI = 1 << 4, kYaw_NegPI_2_to_PI_2 = 1 << 5, kYaw_0_to_PI = 1 << 6,
  kRoll_0_to_PI_2 = (1 << 1) | (1 << 2), kPitch_0_to_PI_2 = (1 << 3) | (1 << 4), kYaw_0_to_PI_2 = (1 << 5) | (1 << 6)
}
 
enum  SolverType {
  kDReal, kEqualityConstrainedQP, kGurobi, kIpopt,
  kLinearSystem, kMobyLCP, kMosek, kNlopt,
  kOsqp, kSnopt, kScs, kUnrevisedLemke
}
 

Functions

MapVarToIndex ConstructVarToIndexMap (const Eigen::Ref< const VectorXDecisionVariable > &x)
 
Expression ReplaceBilinearTerms (const Expression &e, const Eigen::Ref< const VectorXDecisionVariable > &x, const Eigen::Ref< const VectorXDecisionVariable > &y, const Eigen::Ref< const MatrixX< symbolic::Expression >> &W)
 
symbolic::Expression ReplaceBilinearTerms (const symbolic::Expression &e, const Eigen::Ref< const VectorXDecisionVariable > &x, const Eigen::Ref< const VectorXDecisionVariable > &y, const Eigen::Ref< const MatrixX< symbolic::Expression >> &W)
 Replaces all the bilinear product terms in the expression e, with the corresponding terms in W, where W represents the matrix x * yᵀ, such that after replacement, e does not have bilinear terms involving x and y. More...
 
bool MathProgHasBinaryVariables (const MathematicalProgram &prog)
 Determines if the mathematical program has binary variables. More...
 
bool IsVariableInList (const std::list< symbolic::Variable > &variable_list, const symbolic::Variable &variable)
 
shared_ptr< QuadraticCostMakeQuadraticErrorCost (const Eigen::Ref< const MatrixXd > &Q, const Eigen::Ref< const VectorXd > &x_desired)
 
shared_ptr< QuadraticCostMakeL2NormCost (const Eigen::Ref< const Eigen::MatrixXd > &A, const Eigen::Ref< const Eigen::VectorXd > &b)
 Creates a cost term of the form | Ax - b |^2. More...
 
std::shared_ptr< QuadraticCostMakeQuadraticErrorCost (const Eigen::Ref< const Eigen::MatrixXd > &Q, const Eigen::Ref< const Eigen::VectorXd > &x_desired)
 Creates a cost term of the form (x-x_desired)'Q(x-x_desired). More...
 
template<typename FF >
std::shared_ptr< CostMakeFunctionCost (FF &&f)
 Converts an input of type F to a nonlinear cost. More...
 
VectorXDecisionVariable ConcatenateVariableRefList (const VariableRefList &var_list)
 Concatenates each element in var_list into a single Eigen vector of decision variables, returns this concatenated vector. More...
 
SolutionResult SolveUnconstrainedQP (const Eigen::Ref< const Eigen::MatrixXd > &G, const Eigen::Ref< const Eigen::VectorXd > &c, double feasibility_tol, Eigen::VectorXd *x)
 Solves the un-constrained QP problem min 0.5 * xᵀ * G * x + cᵀ * x. More...
 
VectorXIndeterminate ConcatenateIndeterminatesRefList (const IndeterminatesRefList &var_list)
 Concatenates each element in var_list into a single Eigen vector of indeterminates, returns this concatenated vector. More...
 
Binding< LinearConstraintCreateLogicalAndConstraint (const symbolic::Expression &b1, const symbolic::Expression &b2, const symbolic::Expression &b1_and_b2)
 Adds linear constraints, such that when b1, b2, b1_and_b2 satisfy the constraints, and b1, b2 take binary values, it is guaranteed that b1_and_b2 = b1 ∧ b2 (b1 and b2). More...
 
Binding< LinearConstraintCreateLogicalOrConstraint (const symbolic::Expression &b1, const symbolic::Expression &b2, const symbolic::Expression &b1_or_b2)
 Adds linear constraints, such that when b1, b2, b1_or_b2 satisfy the constraints, and b1, b2 take binary values, it is guaranteed that b1_or_b2 = b1 ∨ b2 (b1 or b2). More...
 
Binding< LinearConstraintCreateLogicalXorConstraint (const symbolic::Expression &b1, const symbolic::Expression &b2, const symbolic::Expression &b1_xor_b2)
 Add linear constraints, such that when b1, b2, b1_xor_b2 satisfy the constraints, and b1, b2 take binary values, it is guaranteed that b1_xor_b2 = b1 ⊕ b2 (b1 exclusive xor b2). More...
 
Binding< LinearConstraintCreateBinaryCodeMatchConstraint (const VectorX< symbolic::Expression > &code, const Eigen::Ref< const Eigen::VectorXi > &expected, const symbolic::Expression &match)
 Create linear constraints such that, when these constraints are satisfied, match = 1 if and only if code == expected, otherwise match = 0. More...
 
std::string to_string (SolutionResult solution_result)
 
std::ostream & operator<< (std::ostream &os, SolutionResult solution_result)
 
std::string to_string (IntervalBinning binning)
 
std::ostream & operator<< (std::ostream &os, const IntervalBinning &binning)
 
void AddLogarithmicSos2Constraint (MathematicalProgram *prog, const Eigen::Ref< const VectorX< symbolic::Expression >> &lambda, const Eigen::Ref< const VectorX< symbolic::Expression >> &y)
 Adds the special ordered set 2 (SOS2) constraint,. More...
 
void AddSos2Constraint (MathematicalProgram *prog, const Eigen::Ref< const VectorX< symbolic::Expression >> &lambda, const Eigen::Ref< const VectorX< symbolic::Expression >> &y)
 Adds the special ordered set 2 (SOS2) constraint. More...
 
void AddLogarithmicSos1Constraint (MathematicalProgram *prog, const Eigen::Ref< const VectorX< symbolic::Expression >> &lambda, const Eigen::Ref< const VectorXDecisionVariable > &y, const Eigen::Ref< const Eigen::MatrixXi > &codes)
 Adds the special ordered set of type 1 (SOS1) constraint. More...
 
void AddBilinearProductMcCormickEnvelopeMultipleChoice (MathematicalProgram *prog, const symbolic::Variable &x, const symbolic::Variable &y, const symbolic::Expression &w, const Eigen::Ref< const Eigen::VectorXd > &phi_x, const Eigen::Ref< const Eigen::VectorXd > &phi_y, const Eigen::Ref< const VectorX< symbolic::Expression >> &Bx, const Eigen::Ref< const VectorX< symbolic::Expression >> &By)
 Add constraints to the optimization program, such that the bilinear product x * y is approximated by w, using Mixed Integer constraint with "Multiple Choice" model. More...
 
constexpr int CeilLog2 (int n)
 Return ⌈log₂(n)⌉, namely the minimal integer no smaller than log₂(n), with base 2. More...
 
template<typename Derived >
std::enable_if< drake::is_eigen_vector_of< Derived, symbolic::Expression >::value, typename LogarithmicSos2NewBinaryVariables< Derived::RowsAtCompileTime >::type >::type AddLogarithmicSos2Constraint (MathematicalProgram *prog, const Eigen::MatrixBase< Derived > &lambda, const std::string &binary_variable_name="y")
 Adds the special ordered set 2 (SOS2) constraint,. More...
 
template<typename DerivedPhiX , typename DerivedPhiY , typename DerivedBx , typename DerivedBy >
std::enable_if< is_eigen_vector_of< DerivedPhiX, double >::value &&is_eigen_vector_of< DerivedPhiY, double >::value &&is_eigen_vector_of< DerivedBx, symbolic::Expression >::value &&is_eigen_vector_of< DerivedBy, symbolic::Expression >::value, MatrixDecisionVariable< DerivedPhiX::RowsAtCompileTime, DerivedPhiY::RowsAtCompileTime > >::type AddBilinearProductMcCormickEnvelopeSos2 (MathematicalProgram *prog, const symbolic::Variable &x, const symbolic::Variable &y, const symbolic::Expression &w, const DerivedPhiX &phi_x, const DerivedPhiY &phi_y, const DerivedBx &Bx, const DerivedBy &By, IntervalBinning binning)
 Add constraints to the optimization program, such that the bilinear product x * y is approximated by w, using Special Ordered Set of Type 2 (sos2) constraint. More...
 
std::string to_string (MixedIntegerRotationConstraintGenerator::Approach type)
 
std::ostream & operator<< (std::ostream &os, const MixedIntegerRotationConstraintGenerator::Approach &type)
 
AddRotationMatrixBoxSphereIntersectionReturn AddRotationMatrixBoxSphereIntersectionMilpConstraints (const Eigen::Ref< const MatrixDecisionVariable< 3, 3 >> &R, int num_intervals_per_half_axis, MathematicalProgram *prog)
 Adds binary variables that constrain the value of the column and row vectors of R, in order to add the following (in some cases non-convex) constraints as an MILP. More...
 
std::pair< Eigen::MatrixXd, Eigen::MatrixXd > DecomposeNonConvexQuadraticForm (const Eigen::Ref< const Eigen::MatrixXd > &Q)
 For a non-convex homogeneous quadratic form xᵀQx, where Q is not necessarily a positive semidefinite matrix, we decompose it as a difference between two convex homogeneous quadratic forms xᵀQx = xᵀQ₁x - xᵀQ₂x, Q₁, Q₂ are positive semidefinite. More...
 
std::tuple< Binding< LinearConstraint >, std::vector< Binding< RotatedLorentzConeConstraint > >, VectorXDecisionVariableAddRelaxNonConvexQuadraticConstraintInTrustRegion (MathematicalProgram *prog, const Eigen::Ref< const VectorXDecisionVariable > &x, const Eigen::Ref< const Eigen::MatrixXd > &Q1, const Eigen::Ref< const Eigen::MatrixXd > &Q2, const Eigen::Ref< const VectorXDecisionVariable > &y, const Eigen::Ref< const Eigen::VectorXd > &p, double lower_bound, double upper_bound, const Eigen::Ref< const Eigen::VectorXd > &linearization_point, double trust_region_gap)
 For a non-convex quadratic constraint lb ≤ xᵀQ₁x - xᵀQ₂x + pᵀy ≤ ub where Q₁, Q₂ are both positive semidefinite matrices. More...
 
MatrixDecisionVariable< 3, 3 > NewRotationMatrixVars (MathematicalProgram *prog, const std::string &name="R")
 Allocates a 3x3 matrix of decision variables with the trivial bounding box constraint ensuring all elements are [-1,1], and the linear constraint imposing -1 <= trace(R) <= 3. More...
 
void AddBoundingBoxConstraintsImpliedByRollPitchYawLimits (MathematicalProgram *prog, const Eigen::Ref< const MatrixDecisionVariable< 3, 3 >> &R, RollPitchYawLimits limits=kNoLimits)
 Applies very conservative limits on the entries of R for the cases when rotations can be limited (for instance, if you want to search over rotations, but there is an obvious symmetry in the problem so that e.g. More...
 
void AddBoundingBoxConstraintsImpliedByRollPitchYawLimitsToBinary (MathematicalProgram *prog, const Eigen::Ref< const MatrixDecisionVariable< 3, 3 >> &B, RollPitchYawLimits limits)
 
void AddRotationMatrixSpectrahedralSdpConstraint (MathematicalProgram *prog, const Eigen::Ref< const MatrixDecisionVariable< 3, 3 >> &R)
 Adds constraint (10) from https://arxiv.org/pdf/1403.4914.pdf , which exactly represents the convex hull of all rotation matrices in 3D. More...
 
void AddRotationMatrixOrthonormalSocpConstraint (MathematicalProgram *prog, const Eigen::Ref< const MatrixDecisionVariable< 3, 3 >> &R)
 Adds a set of convex constraints which approximate the set of orthogonal matrices, O(3). More...
 
bool operator== (const SolverId &a, const SolverId &b)
 
bool operator!= (const SolverId &a, const SolverId &b)
 
std::ostream & operator<< (std::ostream &os, const SolverId &self)
 
 TEST_P (TestMinimumDistance, Test)
 
 TEST_P (TestMinimumDistanceWOrthonormalSocp, Test)
 
 INSTANTIATE_TEST_CASE_P (RotationTest, TestMinimumDistance,::testing::Combine(::testing::ValuesIn< std::vector< MixedIntegerRotationConstraintGenerator::Approach >>({MixedIntegerRotationConstraintGenerator::Approach::kBoxSphereIntersection, MixedIntegerRotationConstraintGenerator::Approach::kBilinearMcCormick}),::testing::ValuesIn< std::vector< int >>({1, 2, 3})))
 
 INSTANTIATE_TEST_CASE_P (RotationTest, TestMinimumDistanceWOrthonormalSocp,::testing::Combine(::testing::ValuesIn< std::vector< MixedIntegerRotationConstraintGenerator::Approach >>({MixedIntegerRotationConstraintGenerator::Approach::kBoxSphereIntersection}),::testing::ValuesIn< std::vector< int >>({1, 2, 3})))
 
void DrawSphere (const Eigen::RowVector3d &color=Eigen::RowVector3d(0, 0.5,0.5))
 Draw a unit sphere. More...
 
void DrawBox (const Eigen::Vector3d &bmin, const Eigen::Vector3d &bmax, const Eigen::RowVector3d &color=Eigen::RowVector3d(0.5, 0.2,0.3))
 Draw the box bmin <= x <= bmax, where the inequality is elementwise. More...
 
void DrawBoxSphereIntersection (const Eigen::Vector3d &bmin, const Eigen::Vector3d &bmax, const Eigen::RowVector3d &color=Eigen::RowVector3d(1, 0, 0))
 Draw the boundary of the intersection region, between the box bmin <= x <= bmax, and the unit sphere. More...
 
template<typename Derived >
void RunLCP (const Eigen::MatrixBase< Derived > &M, const Eigen::VectorXd &q, const Eigen::VectorXd &expected_z_in)
 
 GTEST_TEST (TestUnrevisedLemke, DimensionalMismatch)
 
 GTEST_TEST (TestUnrevisedLemke, TestCycling)
 
 GTEST_TEST (TestUnrevisedLemke, TestSimple)
 
 GTEST_TEST (TestUnrevisedLemke, TestPSD)
 
 GTEST_TEST (TestUnrevisedLemke, TestProblem1)
 
 GTEST_TEST (TestUnrevisedLemke, TestProblem2)
 
 GTEST_TEST (TestUnrevisedLemke, TestProblem3)
 
 GTEST_TEST (TestUnrevisedLemke, TestProblem4)
 
 GTEST_TEST (TestUnrevisedLemke, TestProblem6)
 
 GTEST_TEST (TestUnrevisedLemke, TestEmpty)
 
 GTEST_TEST (TestUnrevisedLemke, TestFailure)
 
 GTEST_TEST (TestUnrevisedLemke, TestSolutionQuality)
 
 GTEST_TEST (TestUnrevisedLemke, ZeroTolerance)
 
 GTEST_TEST (TestUnrevisedLemke, WarmStarting)
 
 GTEST_TEST (TestUnrevisedLemke, Trivial)
 
 TEST_F (UnrevisedLemkePrivateTests, SelectSubMatrixWithCovering)
 
 TEST_F (UnrevisedLemkePrivateTests, SelectSubColumnWithCovering)
 
 TEST_F (UnrevisedLemkePrivateTests, SelectSubVector)
 
 TEST_F (UnrevisedLemkePrivateTests, SetSubVector)
 
 TEST_F (UnrevisedLemkePrivateTests, ValidateIndices)
 
 TEST_F (UnrevisedLemkePrivateTests, IsEachUnique)
 
 TEST_F (UnrevisedLemkePrivateTests, LemkePivot)
 
 TEST_F (UnrevisedLemkePrivateTests, ConstructLemkeSolution)
 
 TEST_F (UnrevisedLemkePrivateTests, DetermineIndexSets)
 
 TEST_F (UnrevisedLemkePrivateTests, FindComplementIndex)
 
 TEST_F (UnrevisedLemkePrivateTests, FindBlockingIndex)
 
 TEST_F (UnrevisedLemkePrivateTests, FindBlockingIndexCycling)
 

Variables

const double epsilon = 5e-14
 

Typedef Documentation

typedef uint32_t AttributesSet
using IndeterminatesRefList = std::list<Eigen::Ref<const VectorXIndeterminate>>
using MapVarToIndex = unordered_map<Variable::Id, int>
using MatrixDecisionVariable = Eigen::Matrix<symbolic::Variable, rows, cols>
using MatrixIndeterminate = Eigen::Matrix<symbolic::Variable, rows, cols>

MatrixIndeterminate<int, int> is used as an alias for Eigen::Matrix<symbolic::Variable, int, int>.

After resolving aliases, a compiler does not distinguish between these two. All indeterminates are a variable of type symbolic::Variable::Type::CONTINUOUS (by default).

Template Parameters
rowsThe number of rows in the new matrix containing indeterminates.
colsThe number of columns in the new matrix containing indeterminates.
using MatrixXDecisionVariable = MatrixDecisionVariable<Eigen::Dynamic, Eigen::Dynamic>
using MatrixXIndeterminate = MatrixIndeterminate<Eigen::Dynamic, Eigen::Dynamic>

MatrixXIndeterminate is used as an alias for Eigen::Matrix<symbolic::Variable, Eigen::Dynamic, Eigen::Dynamic>.

See also
MatrixIndeterminate<int, int>
typedef uint32_t RollPitchYawLimits
using VariableRefList = std::list<Eigen::Ref<const VectorXDecisionVariable>>

VectorIndeterminate<int> is used as an alias for Eigen::Matrix<symbolic::Variable, int, 1>.

Template Parameters
rowsThe number of rows in the new matrix containing indeterminates.
See also
MatrixIndeterminate<int, int>
using VectorXIndeterminate = VectorIndeterminate<Eigen::Dynamic>

VectorXIndeterminate is used as an alias for Eigen::Matrix<symbolic::Variable, Eigen::Dynamic, 1>.

See also
MatrixIndeterminate<int, int>

Enumeration Type Documentation

enum IntervalBinning
strong

For a continuous variable whose range is cut into small intervals, we will use binary variables to represent which interval the continuous variable is in.

We support two representations, either using logarithmic number of binary variables, or linear number of binary variables. For more details,

See also
AddLogarithmicSos2Constraint and AddSos2Constraint
Enumerator
kLogarithmic 
kLinear 
Enumerator
kNoCapabilities 
kError 

Do not use, to avoid & vs. && typos.

kGenericCost 
kGenericConstraint 
kQuadraticCost 
kQuadraticConstraint 
kLinearCost 
kLinearConstraint 
kLinearEqualityConstraint 
kLinearComplementarityConstraint 
kLorentzConeConstraint 
kRotatedLorentzConeConstraint 
kPositiveSemidefiniteConstraint 
kBinaryVariable 
kCallback 
Enumerator
kNoLimits 
kRPYError 

Do not use, to avoid & vs. && typos.

kRoll_NegPI_2_to_PI_2 
kRoll_0_to_PI 
kPitch_NegPI_2_to_PI_2 
kPitch_0_to_PI 
kYaw_NegPI_2_to_PI_2 
kYaw_0_to_PI 
kRoll_0_to_PI_2 
kPitch_0_to_PI_2 
kYaw_0_to_PI_2 
Enumerator
kSolutionFound 

Found the optimal solution.

kInvalidInput 

Invalid input.

kInfeasibleConstraints 

The primal is infeasible.

kUnbounded 

The primal is unbounded.

kUnknownError 

Unknown error.

kInfeasible_Or_Unbounded 

The primal is either infeasible or unbounded.

kIterationLimit 

Reaches the iteration limits.

kDualInfeasible 

Dual problem is infeasible.

In this case we cannot infer the status of the primal problem.

enum SolverType
strong
Enumerator
kDReal 
kEqualityConstrainedQP 
kGurobi 
kIpopt 
kLinearSystem 
kMobyLCP 
kMosek 
kNlopt 
kOsqp 
kSnopt 
kScs 
kUnrevisedLemke 

Function Documentation

void AddBilinearProductMcCormickEnvelopeMultipleChoice ( MathematicalProgram prog,
const symbolic::Variable x,
const symbolic::Variable y,
const symbolic::Expression w,
const Eigen::Ref< const Eigen::VectorXd > &  phi_x,
const Eigen::Ref< const Eigen::VectorXd > &  phi_y,
const Eigen::Ref< const VectorX< symbolic::Expression >> &  Bx,
const Eigen::Ref< const VectorX< symbolic::Expression >> &  By 
)

Add constraints to the optimization program, such that the bilinear product x * y is approximated by w, using Mixed Integer constraint with "Multiple Choice" model.

To do so, we assume that the range of x is [x_min, x_max], and the range of y is [y_min, y_max]. We first consider two arrays φˣ, φʸ, satisfying

x_min = φˣ₀ < φˣ₁ < ... < φˣₘ = x_max
y_min = φʸ₀ < φʸ₁ < ... < φʸₙ = y_max

, and divide the range of x into intervals [φˣ₀, φˣ₁], [φˣ₁, φˣ₂], ... , [φˣₘ₋₁, φˣₘ] and the range of y into intervals [φʸ₀, φʸ₁], [φʸ₁, φʸ₂], ... , [φʸₙ₋₁, φʸₙ]. The xy plane is thus cut into rectangles, with each rectangle as [φˣᵢ, φˣᵢ₊₁] x [φʸⱼ, φʸⱼ₊₁]. The convex hull of the surface z = x * y for x, y in each rectangle is a tetrahedron. We then approximate the bilinear product x * y with w, such that (x, y, w) is in one of the tetrahedrons.

Parameters
progThe optimization problem to which the constraints will be added.
xA variable in the bilinear product.
yA variable in the bilinear product.
wThe expression that approximates the bilinear product x * y.
phi_xφˣ in the documentation above. Will be used to cut the range of x into small intervals.
phi_yφʸ in the documentation above. Will be used to cut the range of y into small intervals.
BxThe binary-valued expression indicating which interval x is in. Bx(i) = 1 => φˣᵢ ≤ x ≤ φˣᵢ₊₁.
ByThe binary-valued expression indicating which interval y is in. By(i) = 1 => φʸⱼ ≤ y ≤ φʸⱼ₊₁.

One formulation of the constraint is

x = ∑ᵢⱼ x̂ᵢⱼ
y = ∑ᵢⱼ ŷᵢⱼ
Bˣʸᵢⱼ = Bˣᵢ ∧ Bʸⱼ
∑ᵢⱼ Bˣʸᵢⱼ = 1
φˣᵢ Bˣʸᵢⱼ ≤ x̂ᵢⱼ ≤ φˣᵢ₊₁ Bˣʸᵢⱼ
φʸⱼ Bˣʸᵢⱼ ≤ ŷᵢⱼ ≤ φʸⱼ₊₁ Bˣʸᵢⱼ
w ≥ ∑ᵢⱼ (x̂ᵢⱼ φʸⱼ + φˣᵢ ŷᵢⱼ - φˣᵢ φʸⱼ Bˣʸᵢⱼ)
w ≥ ∑ᵢⱼ (x̂ᵢⱼ φʸⱼ₊₁ + φˣᵢ₊₁ ŷᵢⱼ - φˣᵢ₊₁ φʸⱼ₊₁ Bˣʸᵢⱼ)
w ≤ ∑ᵢⱼ (x̂ᵢⱼ φʸⱼ + φˣᵢ₊₁ ŷᵢⱼ - φˣᵢ₊₁ φʸⱼ Bˣʸᵢⱼ)
w ≤ ∑ᵢⱼ (x̂ᵢⱼ φʸⱼ₊₁ + φˣᵢ ŷᵢⱼ - φˣᵢ φʸⱼ₊₁ Bˣʸᵢⱼ)

The "logical and" constraint Bˣʸᵢⱼ = Bˣᵢ ∧ Bʸⱼ can be imposed as

Bˣʸᵢⱼ ≥ Bˣᵢ + Bʸⱼ - 1
Bˣʸᵢⱼ ≤ Bˣᵢ
Bˣʸᵢⱼ ≤ Bʸⱼ
0 ≤ Bˣʸᵢⱼ ≤ 1

This formulation will introduce slack variables x̂, ŷ and Bˣʸ, in total 3 * m * n variables.

In order to reduce the number of slack variables, we can further simplify these constraints, by defining two vectors x̅ ∈ ℝⁿ, y̅ ∈ ℝᵐ as

x̅ⱼ = ∑ᵢ x̂ᵢⱼ
y̅ᵢ = ∑ⱼ ŷᵢⱼ

and the constraints above can be re-formulated using and as

x = ∑ⱼ x̅ⱼ
y = ∑ᵢ y̅ᵢ
Bˣʸᵢⱼ = Bˣᵢ ∧ Bʸⱼ
∑ᵢⱼ Bˣʸᵢⱼ = 1
∑ᵢ φˣᵢ Bˣʸᵢⱼ ≤ x̅ⱼ ≤ ∑ᵢ φˣᵢ₊₁ Bˣʸᵢⱼ
∑ⱼ φʸⱼ Bˣʸᵢⱼ ≤ y̅ᵢ ≤ ∑ⱼ φʸⱼ₊₁ Bˣʸᵢⱼ
w ≥ ∑ⱼ( x̅ⱼ φʸⱼ ) + ∑ᵢ( φˣᵢ y̅ᵢ ) - ∑ᵢⱼ( φˣᵢ φʸⱼ Bˣʸᵢⱼ )
w ≥ ∑ⱼ( x̅ⱼ φʸⱼ₊₁ ) + ∑ᵢ( φˣᵢ₊₁ y̅ᵢ ) - ∑ᵢⱼ( φˣᵢ₊₁ φʸⱼ₊₁ Bˣʸᵢⱼ )
w ≤ ∑ⱼ( x̅ⱼ φʸⱼ ) + ∑ᵢ( φˣᵢ₊₁ y̅ⱼ ) - ∑ᵢⱼ( φˣᵢ₊₁ φʸⱼ Bˣʸᵢⱼ )
w ≤ ∑ⱼ( x̅ⱼ φʸⱼ₊₁ ) + ∑ᵢ( φˣᵢ y̅ᵢ ) - ∑ᵢⱼ( φˣᵢ φʸⱼ₊₁ Bˣʸᵢⱼ ).

In this formulation, we introduce new continuous variables , , Bˣʸ. The total number of new variables is m + n + m * n.

In section 3.3 of Mixed-Integer Models for Nonseparable Piecewise Linear Optimization: Unifying Framework and Extensions by Juan P Vielma, Shabbir Ahmed and George Nemhauser, this formulation is called "Multiple Choice Model".

Note
We DO NOT add the constraint Bx(i) ∈ {0, 1}, By(j) ∈ {0, 1} in this function. It is the user's responsibility to ensure that these binary constraints are enforced. The users can also add cutting planes ∑ᵢBx(i) = 1, ∑ⱼBy(j) = 1. Without these two cutting planes, (x, y, w) is still in the McCormick envelope of z = x * y, but these two cutting planes "might" improve the computation speed in the mixed-integer solver.

Here is the call graph for this function:

Here is the caller graph for this function:

std::enable_if< is_eigen_vector_of<DerivedPhiX, double>::value && is_eigen_vector_of<DerivedPhiY, double>::value && is_eigen_vector_of<DerivedBx, symbolic::Expression>::value && is_eigen_vector_of<DerivedBy, symbolic::Expression>::value, MatrixDecisionVariable<DerivedPhiX::RowsAtCompileTime, DerivedPhiY::RowsAtCompileTime> >::type drake::solvers::AddBilinearProductMcCormickEnvelopeSos2 ( MathematicalProgram prog,
const symbolic::Variable x,
const symbolic::Variable y,
const symbolic::Expression w,
const DerivedPhiX &  phi_x,
const DerivedPhiY &  phi_y,
const DerivedBx &  Bx,
const DerivedBy &  By,
IntervalBinning  binning 
)

Add constraints to the optimization program, such that the bilinear product x * y is approximated by w, using Special Ordered Set of Type 2 (sos2) constraint.

To do so, we assume that the range of x is [x_min, x_max], and the range of y is [y_min, y_max]. We first consider two arrays φˣ, φʸ, satisfying

x_min = φˣ₀ < φˣ₁ < ... < φˣₘ = x_max
y_min = φʸ₀ < φʸ₁ < ... < φʸₙ = y_max

, and divide the range of x into intervals [φˣ₀, φˣ₁], [φˣ₁, φˣ₂], ... , [φˣₘ₋₁, φˣₘ] and the range of y into intervals [φʸ₀, φʸ₁], [φʸ₁, φʸ₂], ... , [φʸₙ₋₁, φʸₙ]. The xy plane is thus cut into rectangles, with each rectangle as [φˣᵢ, φˣᵢ₊₁] x [φʸⱼ, φʸⱼ₊₁]. The convex hull of the surface z = x * y for x, y in each rectangle is a tetrahedron. We then approximate the bilinear product x * y with w, such that (x, y, w) is in one of the tetrahedrons.

We use two different encoding schemes on the binary variables, to determine which interval is active. We can choose either linear or logarithmic binning. When using linear binning, for a variable with N intervals, we use N binary variables, and B(i) = 1 indicates the variable is in the i'th interval. When using logarithmic binning, we use ⌈log₂(N)⌉ binary variables. If these binary variables represent integer M in the reflected Gray code, then the continuous variable is in the M'th interval.

Parameters
progThe program to which the bilinear product constraint is added
xThe decision variable.
yThe decision variable.
wThe expression to approximate x * y
phi_xThe end points of the intervals for x.
phi_yThe end points of the intervals for y.
BxThe binary variables for the interval in which x stays encoded as described above.
ByThe binary variables for the interval in which y stays encoded as described above.
binningDetermine whether to use linear binning or logarithmic binning.
Returns
lambda The auxiliary continuous variables.

The constraints we impose are

x = (φˣ)ᵀ * ∑ⱼ λᵢⱼ
y = (φʸ)ᵀ * ∑ᵢ λᵢⱼ
w = ∑ᵢⱼ φˣᵢ * φʸⱼ * λᵢⱼ
Both ∑ⱼ λᵢⱼ = λ.rowwise().sum() and ∑ᵢ λᵢⱼ = λ.colwise().sum() satisfy SOS2

If x ∈ [φx(M), φx(M+1)] and y ∈ [φy(N), φy(N+1)], then only λ(M, N), λ(M + 1, N), λ(M, N + 1) and λ(M+1, N+1) can be strictly positive, all other λ(i, j) are zero.

Note
We DO NOT add the constraint Bx(i) ∈ {0, 1}, By(j) ∈ {0, 1} in this function. It is the user's responsibility to ensure that these constraints are enforced.

Here is the call graph for this function:

void AddBoundingBoxConstraintsImpliedByRollPitchYawLimits ( MathematicalProgram prog,
const Eigen::Ref< const MatrixDecisionVariable< 3, 3 >> &  R,
RollPitchYawLimits  limits = kNoLimits 
)

Applies very conservative limits on the entries of R for the cases when rotations can be limited (for instance, if you want to search over rotations, but there is an obvious symmetry in the problem so that e.g.

0 < pitch < PI need not be considered). A matrix so constrained may still contain rotations outside of this envelope. Note: For simple rotational symmetry over PI, prefer kPitch_NegPI_2_to_PI_2 (over 0_to_PI) because it adds one more constraint (when combined with constraints on roll and yaw). Note: The Roll-Pitch-Yaw coordinates follow the convention in - representing extrinsic rotations about Space-fixed x-y-z axes, respectively.

Here is the call graph for this function:

void drake::solvers::AddBoundingBoxConstraintsImpliedByRollPitchYawLimitsToBinary ( MathematicalProgram prog,
const Eigen::Ref< const MatrixDecisionVariable< 3, 3 >> &  B,
RollPitchYawLimits  limits 
)

Here is the call graph for this function:

void AddLogarithmicSos1Constraint ( MathematicalProgram prog,
const Eigen::Ref< const VectorX< symbolic::Expression >> &  lambda,
const Eigen::Ref< const VectorXDecisionVariable > &  y,
const Eigen::Ref< const Eigen::MatrixXi > &  codes 
)

Adds the special ordered set of type 1 (SOS1) constraint.

Namely

  λ(0) + ... + λ(n-1) = 1
  λ(i) ≥ 0 ∀i
  ∃ j ∈ {0, 1, ..., n-1}, s.t λ(j) = 1

one and only one of λ(i) is strictly positive (equals to 1 in this case). We will need to add ⌈log₂(n)⌉ binary variables, where n is the number of rows in λ. For more information, please refer to Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints by J. Vielma and G. Nemhauser, 2011.

Parameters
progThe program to which the SOS1 constraint is added.
lambdalambda is in SOS1.
yThe binary variables indicating which λ is positive. For a given assignment on the binary variable y, if (y(0), ..., y(⌈log₂(n)⌉) represents integer M in codes, then only λ(M) is positive. Namely, if (y(0), ..., y(⌈log₂(n)⌉) equals to codes.row(M), then λ(M) = 1
codesA n x ⌈log₂(n)⌉ matrix. code.row(i) represents integer i. No two rows of codes can be the same.
Exceptions
std::runtime_errorif codes has a non-binary entry (0, 1).

Here is the call graph for this function:

Here is the caller graph for this function:

void AddLogarithmicSos2Constraint ( MathematicalProgram prog,
const Eigen::Ref< const VectorX< symbolic::Expression >> &  lambda,
const Eigen::Ref< const VectorX< symbolic::Expression >> &  y 
)

Adds the special ordered set 2 (SOS2) constraint,.

See also
AddLogarithmicSos2Constraint.

Here is the call graph for this function:

Here is the caller graph for this function:

std::enable_if< drake::is_eigen_vector_of<Derived, symbolic::Expression>::value, typename LogarithmicSos2NewBinaryVariables< Derived::RowsAtCompileTime>::type>::type drake::solvers::AddLogarithmicSos2Constraint ( MathematicalProgram prog,
const Eigen::MatrixBase< Derived > &  lambda,
const std::string &  binary_variable_name = "y" 
)

Adds the special ordered set 2 (SOS2) constraint,.

  λ(0) + ... + λ(n) = 1
  ∀i. λ(i) ≥ 0
  ∃ j ∈ {0, 1, ..., n-1}, s.t λ(i) = 0 if i ≠ j and i ≠ j + 1 

Namely at most two entries in λ can be strictly positive, and these two entries have to be adjacent. All other λ should be zero. Moreover, the non-zero λ satisfies λ(j) + λ(j + 1) = 1. We will need to add ⌈log₂(n - 1)⌉ binary variables, where n is the number of rows in λ. For more information, please refer to Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints by J. Vielma and G. Nemhauser, 2011.

Parameters
progAdd the SOS2 constraint to this mathematical program.
lambdaAt most two entries in λ can be strictly positive, and these two entries have to be adjacent. All other entries are zero.
Returns
y The newly added binary variables. The assignment of the binary variable y implies which two λ can be strictly positive. With a binary assignment on y, and suppose the integer M corresponds to (y(0), y(1), ..., y(⌈log₂(n - 1)⌉)) in Gray code, then only λ(M) and λ(M + 1) can be non-zero. For example, if the assignment of y = (1, 1), in Gray code, (1, 1) represents integer 2, so only λ(2) and λ(3) can be strictly positive.

Here is the call graph for this function:

std::tuple< Binding< LinearConstraint >, std::vector< Binding< RotatedLorentzConeConstraint > >, VectorXDecisionVariable > AddRelaxNonConvexQuadraticConstraintInTrustRegion ( MathematicalProgram prog,
const Eigen::Ref< const VectorXDecisionVariable > &  x,
const Eigen::Ref< const Eigen::MatrixXd > &  Q1,
const Eigen::Ref< const Eigen::MatrixXd > &  Q2,
const Eigen::Ref< const VectorXDecisionVariable > &  y,
const Eigen::Ref< const Eigen::VectorXd > &  p,
double  lower_bound,
double  upper_bound,
const Eigen::Ref< const Eigen::VectorXd > &  linearization_point,
double  trust_region_gap 
)

For a non-convex quadratic constraint lb ≤ xᵀQ₁x - xᵀQ₂x + pᵀy ≤ ub where Q₁, Q₂ are both positive semidefinite matrices.

y is a vector that can overlap with x. We relax this non-convex constraint by several convex constraints. The steps are

  1. Introduce two new variables z₁, z₂, to replace xᵀQ₁x and xᵀQ₂x respectively. The constraint becomes
         lb ≤ z₁ - z₂ + pᵀy ≤ ub              (1)
       
  2. Ideally, we would like to enforce z₁ = xᵀQ₁x and z₂ = xᵀQ₂x through convex constraints. To this end, we first bound z₁ and z₂ from below, as
         z₁ ≥ xᵀQ₁x                            (2)
         z₂ ≥ xᵀQ₂x                            (3)
       
    These two constraints are second order cone constraints.
  3. To bound z₁ and z₂ from above, we linearize the quadratic forms xᵀQ₁x and xᵀQ₂x at a point x₀. Due to the convexity of the quadratic form, we know that given a positive scalar d > 0, there exists a neighbourhood N(x₀) around x₀, s.t ∀ x ∈ N(x₀)
       xᵀQ₁x ≤ 2 x₀ᵀQ₁(x - x₀) + x₀ᵀQ₁x₀ + d   (4)
       xᵀQ₂x ≤ 2 x₀ᵀQ₂(x - x₀) + x₀ᵀQ₂x₀ + d   (5)
       
    Notice N(x₀) is the intersection of two ellipsoids, as formulated in (4) and (5). Therefore, we also enforce the linear constraints
         z₁ ≤ 2 x₀ᵀQ₁(x - x₀) + x₀ᵀQ₁x₀ + d    (6)
         z₂ ≤ 2 x₀ᵀQ₂(x - x₀) + x₀ᵀQ₂x₀ + d    (7)
       
    So we relax the original non-convex constraint, with the convex constraints (1)-(3), (6) and (7).

The trust region is the neighbourhood N(x₀) around x₀, such that the inequalities (4), (5) are satisfied ∀ x ∈ N(x₀).

The positive scalar d controls both how much the constraint relaxation is (the original constraint can be violated by at most d), and how big the trust region is.

If there is a solution satisfying the relaxed constraint, this solution can violate the original non-convex constraint by at most d; on the other hand, if there is not a solution satisfying the relaxed constraint, it proves that the original non-convex constraint does not have a solution in the trust region.

This approach is outlined in section III of On Time Optimization of Centroidal Momentum Dynamics by Brahayam Ponton, Alexander Herzog, Stefan Schaal and Ludovic Righetti, ICRA, 2018

The special cases are when Q₁ = 0 or Q₂ = 0.

  1. When Q₁ = 0, the original constraint becomes lb ≤ -xᵀQ₂x + pᵀy ≤ ub If ub = +∞, then the original constraint is the convex rotated Lorentz cone constraint xᵀQ₂x ≤ pᵀy - lb. The user should not call this function to relax this convex constraint.
    Exceptions
    std::runtime_errorif Q₁ = 0 and ub = +∞. If ub < +∞, then we introduce a new variable z, with the constraints lb ≤ -z + pᵀy ≤ ub z ≥ xᵀQ₂x z ≤ 2 x₀ᵀQ₂(x - x₀) + x₀ᵀQ₂x₀ + d
  2. When Q₂ = 0, the constraint becomes lb ≤ xᵀQ₁x + pᵀy ≤ ub If lb = -∞, then the original constraint is the convex rotated Lorentz cone constraint xᵀQ₁x ≤ ub - pᵀy. The user should not call this function to relax this convex constraint.
    Exceptions
    std::runtime_errorif Q₂ = 0 and lb = -∞. If lb > -∞, then we introduce a new variable z, with the constraints lb ≤ z + pᵀy ≤ ub z ≥ xᵀQ₁x z ≤ 2 x₀ᵀQ₁(x - x₀) + x₀ᵀQ₁x₀ + d
  3. If both Q₁ and Q₂ are zero, then the original constraint is a convex linear constraint lb ≤ pᵀx ≤ ub. The user should not call this function to relax this convex constraint. Throw a runtime error.
    Parameters
    progThe MathematicalProgram to which the relaxed constraints are added.
    xThe decision variables which appear in the original non-convex constraint.
    Q1A positive semidefinite matrix.
    Q2A positive semidefinite matrix.
    yA vector, the variables in the linear term of the quadratic form.
    pA vector, the linear coefficients of the quadratic form.
    linearization_pointThe vector x₀ in the documentation above.
    lower_boundThe left-hand side of the original non-convex constraint.
    upper_boundThe right-hand side of the original non-convex constraint.
    trust_region_gapThe user-specified positive scalar, d in the documentation above. This gap determines both the maximal constraint violation and the size of the trust region.
    Return values
    <linear_constraint,rotated_lorentz_cones,z>linear_constraint includes (1)(6)(7) rotated_lorentz_cones are (2) (3) When either Q1 or Q2 is zero, rotated_lorentz_cones contains only one rotated Lorentz cone, either (2) or (3). z is the newly added variable.
    Precondition
    1. Q1, Q2 are positive semidefinite.
    1. d is positive.
    2. Q1, Q2, x, x₀ are all of the consistent size.
    3. p and y are of the consistent size.
    4. lower_bound ≤ upper_bound.
    Exceptions
    std::runtime_errorwhen the precondition is not satisfied.

Here is the call graph for this function:

AddRotationMatrixBoxSphereIntersectionReturn AddRotationMatrixBoxSphereIntersectionMilpConstraints ( const Eigen::Ref< const MatrixDecisionVariable< 3, 3 >> &  R,
int  num_intervals_per_half_axis,
MathematicalProgram prog 
)

Adds binary variables that constrain the value of the column and row vectors of R, in order to add the following (in some cases non-convex) constraints as an MILP.

Specifically, for column vectors Ri, we constrain:

  • forall i, |Ri| = 1 ± envelope,
  • forall i,j. i ≠ j, Ri.dot(Rj) = 0 ± envelope,
  • R2 = R0.cross(R1) ± envelope, and again for R0=R1.cross(R2), and R1=R2.cross(R0).

Then all of the same constraints are also added to R^T. The size of the envelope decreases quickly as num_binary_variables_per_half_axis is is increased.

Note: Creates 9*2*num_binary_variables_per_half_axis binary variables named "BRpos*(*,*)" and "BRneg*(*,*)", and the same number of continuous variables named "CRpos*(*,*)" and "CRneg*(*,*)".

Note: The particular representation/algorithm here was developed in an attempt:

  • to enable efficient reuse of the variables between the constraints between multiple rows/columns (e.g. the constraints on Rᵀ use the same variables as the constraints on R), and
  • to facilitate branch-and-bound solution techniques – binary regions are layered so that constraining one region establishes constraints on large portions of SO(3), and confers hopefully "useful" constraints the on other binary variables.
    Parameters
    RThe rotation matrix
    num_intervals_per_half_axisnumber of intervals for a half axis.
    progThe mathematical program to which the constraints are added.
    Note
    This method uses the same approach as MixedIntegerRotationConstraintGenerator with kBoxSphereIntersection, namely the feasible sets to both relaxation are the same. But they use different sets of binary variables, and thus the computation speed can be different inside optimization solvers.

Here is the call graph for this function:

void AddRotationMatrixOrthonormalSocpConstraint ( MathematicalProgram prog,
const Eigen::Ref< const MatrixDecisionVariable< 3, 3 >> &  R 
)

Adds a set of convex constraints which approximate the set of orthogonal matrices, O(3).

Adds the bilinear constraints that the each column Ri has length <= 1 and that Ri'Rj approx 0 via -2 + |Ri|^2 + |Rj|^2 <= 2Ri'Rj <= 2 - |Ri|^2 - |Rj|^2 (for all i!=j), using a second-order-cone relaxation. Additionally, the same constraints are applied to all of the rows.

Here is the call graph for this function:

Here is the caller graph for this function:

void AddRotationMatrixSpectrahedralSdpConstraint ( MathematicalProgram prog,
const Eigen::Ref< const MatrixDecisionVariable< 3, 3 >> &  R 
)

Adds constraint (10) from https://arxiv.org/pdf/1403.4914.pdf , which exactly represents the convex hull of all rotation matrices in 3D.

Here is the call graph for this function:

void AddSos2Constraint ( MathematicalProgram prog,
const Eigen::Ref< const VectorX< symbolic::Expression >> &  lambda,
const Eigen::Ref< const VectorX< symbolic::Expression >> &  y 
)

Adds the special ordered set 2 (SOS2) constraint.

y(i) takes binary values (either 0 or 1).

  y(i) = 1 => λ(i) + λ(i + 1) = 1.
See also
AddLogarithmicSos2Constraint for a complete explanation on SOS2 constraint.
Parameters
progThe optimization program to which the SOS2 constraint is added.
lambdaAt most two entries in λ can be strictly positive, and these two entries have to be adjacent. All other entries are zero. Moreover, these two entries should sum up to 1.
yy(i) takes binary value, and determines which two entries in λ can be strictly positive. Throw a runtime error if y.rows() != lambda.rows() - 1.

Here is the call graph for this function:

Here is the caller graph for this function:

constexpr int drake::solvers::CeilLog2 ( int  n)

Return ⌈log₂(n)⌉, namely the minimal integer no smaller than log₂(n), with base 2.

Parameters
nA positive integer.
Returns
The minimal integer no smaller than log₂(n).

Here is the caller graph for this function:

VectorXIndeterminate ConcatenateIndeterminatesRefList ( const IndeterminatesRefList var_list)

Concatenates each element in var_list into a single Eigen vector of indeterminates, returns this concatenated vector.

Here is the call graph for this function:

Here is the caller graph for this function:

VectorXDecisionVariable ConcatenateVariableRefList ( const VariableRefList var_list)

Concatenates each element in var_list into a single Eigen vector of decision variables, returns this concatenated vector.

Here is the caller graph for this function:

MapVarToIndex drake::solvers::ConstructVarToIndexMap ( const Eigen::Ref< const VectorXDecisionVariable > &  x)

Here is the caller graph for this function:

Binding< LinearConstraint > CreateBinaryCodeMatchConstraint ( const VectorX< symbolic::Expression > &  code,
const Eigen::Ref< const Eigen::VectorXi > &  expected,
const symbolic::Expression match 
)

Create linear constraints such that, when these constraints are satisfied, match = 1 if and only if code == expected, otherwise match = 0.

Parameters
codecode(i) should only take binary values.
expectedThe expected matched value for code.
matchan expression that takes binary value, representing if code == expected
Returns
the linear constraints.

This function is useful integer optimization, for example, if we have a constraint match = ((b1 == 0) && (b2 == 1) && (b3 == 1)), we can call the function CreateBinaryCodeMatchConstraint({b1, b2, b3}, {0, 1, 1}, match) to create the constraint.

Here is the call graph for this function:

Binding< LinearConstraint > CreateLogicalAndConstraint ( const symbolic::Expression b1,
const symbolic::Expression b2,
const symbolic::Expression b1_and_b2 
)

Adds linear constraints, such that when b1, b2, b1_and_b2 satisfy the constraints, and b1, b2 take binary values, it is guaranteed that b1_and_b2 = b1 ∧ b2 (b1 and b2).

The constraints are

  b1_and_b2 >= b1 + b2 - 1
  b1_and_b2 <= b1
  b1_and_b2 <= b2
  0 <= b1_and_b2 <= 1
Parameters
b1An expression that should only take a binary value.
b2An expression that should only take a binary value.
b1_and_b2Should be the logical and between b1 and b2.
Returns
The newly added constraints, such that when b1, b2, b1_and_b2 satisfy the constraints, it is guaranteed that b1_and_b2 = b1 ∧ b2.
Precondition
b1, b2, b1_and_b2 are all linear expressions.

Here is the call graph for this function:

Here is the caller graph for this function:

Binding< LinearConstraint > CreateLogicalOrConstraint ( const symbolic::Expression b1,
const symbolic::Expression b2,
const symbolic::Expression b1_or_b2 
)

Adds linear constraints, such that when b1, b2, b1_or_b2 satisfy the constraints, and b1, b2 take binary values, it is guaranteed that b1_or_b2 = b1 ∨ b2 (b1 or b2).

The constraints are

  b1_or_b2 <= b1 + b2
  b1_or_b2 >= b1
  b1_or_b2 >= b2
  0 <= b1_or_b2 <= 1
Parameters
b1An expression that should only take a binary value.
b2An expression that should only take a binary value.
b1_or_b2Should be the logical or between b1 and b2.
Returns
The newly added constraints, such that when b1, b2, b1_or_b2 satisfy the constraints, it is guaranteed that b1_or_b2 = b1 ∨ b2.
Precondition
b1, b2, b1_or_b2 are all linear expressions.

Here is the call graph for this function:

Binding< LinearConstraint > CreateLogicalXorConstraint ( const symbolic::Expression b1,
const symbolic::Expression b2,
const symbolic::Expression b1_xor_b2 
)

Add linear constraints, such that when b1, b2, b1_xor_b2 satisfy the constraints, and b1, b2 take binary values, it is guaranteed that b1_xor_b2 = b1 ⊕ b2 (b1 exclusive xor b2).

The constraints are

  b1_xor_b2 <= b1 + b2
  b1_xor_b2 >= b1 - b2
  b1_xor_b2 >= b2 - b1
  b1_xor_b2 <= 2 - b1 - b2
  0 <= b1_xor_b2 <= 1
Parameters
b1An expression that should only take a binary value.
b2An expression that should only take a binary value.
b1_xor_b2Should be the logical exclusive or between b1 and b2.
Returns
The newly added constraints, such that when b1, b2, b1_xor_b2 satisfy the constraints, it is guaranteed that b1_xor_b2 = b1 ⊕ b2.
Precondition
b1, b2, b1_xor_b2 are all linear expressions.

Here is the call graph for this function:

std::pair< Eigen::MatrixXd, Eigen::MatrixXd > DecomposeNonConvexQuadraticForm ( const Eigen::Ref< const Eigen::MatrixXd > &  Q)

For a non-convex homogeneous quadratic form xᵀQx, where Q is not necessarily a positive semidefinite matrix, we decompose it as a difference between two convex homogeneous quadratic forms xᵀQx = xᵀQ₁x - xᵀQ₂x, Q₁, Q₂ are positive semidefinite.

To find the optimal Q₁ and Q₂, we solve the following semidefinite programming problem min s s.t s >= trace(Q₁) s >= trace(Q₂) Q₁ - Q₂ = (Q + Qᵀ) / 2 Q₁, Q₂ are positive semidefinite The decomposition Q = Q₁ - Q₂ can be used later, to solve the non-convex optimization problem involving a quadratic form xᵀQx. For more information, please refer to the papers on difference of convex decomposition, for example Undominated d.c Decompositions of Quadratic Functions and Applications to Branch-and-Bound Approaches By I.M.Bomze and M. Locatelli Computational Optimization and Applications, 2004 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques By A. A. Ahmadi and G. Hall Mathematical Programming, 2015

Parameters
QA square matrix. Throws a runtime_error if Q is not square.
Returns
The optimal decomposition (Q₁, Q₂) TODO(hongkai.dai): templatize this function, to avoid dynamic memory allocation.

Here is the call graph for this function:

void DrawBox ( const Eigen::Vector3d &  bmin,
const Eigen::Vector3d &  bmax,
const Eigen::RowVector3d &  color = Eigen::RowVector3d(0.5, 0.2,0.3) 
)

Draw the box bmin <= x <= bmax, where the inequality is elementwise.

Parameters
bminThe innermost corner of the box
bmaxThe outermost corner of the box
colorThe rgb color of the surface to be plotted.
Default: is [0.5, 0.2, 0.3]
Precondition
bmin >= 0 and bmax >= 0. The inequality is elementwise.

Here is the call graph for this function:

void DrawBoxSphereIntersection ( const Eigen::Vector3d &  bmin,
const Eigen::Vector3d &  bmax,
const Eigen::RowVector3d &  color = Eigen::RowVector3d(1, 0, 0) 
)

Draw the boundary of the intersection region, between the box bmin <= x <= bmax, and the unit sphere.

Currently we only accept the box in the first orthant.

Parameters
bminThe innermost corner of the box.
bmaxThe outermost corner of the box.
colorThe rgb color of the boundary to be plotted.
Default: is red.

Here is the call graph for this function:

void DrawSphere ( const Eigen::RowVector3d &  color = Eigen::RowVector3d(0, 0.5,0.5))

Draw a unit sphere.

Parameters
colorThe rgb color of the surface to be plotted.
Default: is [0, 0.5, 0.5]

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
DimensionalMismatch   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestCycling   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestSimple   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestPSD   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestProblem1   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestProblem2   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestProblem3   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestProblem4   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestProblem6   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestEmpty   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestFailure   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
TestSolutionQuality   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
ZeroTolerance   
)
drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
WarmStarting   
)

Here is the call graph for this function:

drake::solvers::GTEST_TEST ( TestUnrevisedLemke  ,
Trivial   
)

Here is the call graph for this function:

drake::solvers::INSTANTIATE_TEST_CASE_P ( RotationTest  ,
TestMinimumDistance  ,
::testing::Combine(::testing::ValuesIn< std::vector< MixedIntegerRotationConstraintGenerator::Approach >>({MixedIntegerRotationConstraintGenerator::Approach::kBoxSphereIntersection, MixedIntegerRotationConstraintGenerator::Approach::kBilinearMcCormick}),::testing::ValuesIn< std::vector< int >>({1, 2, 3}))   
)

Here is the caller graph for this function:

drake::solvers::INSTANTIATE_TEST_CASE_P ( RotationTest  ,
TestMinimumDistanceWOrthonormalSocp  ,
::testing::Combine(::testing::ValuesIn< std::vector< MixedIntegerRotationConstraintGenerator::Approach >>({MixedIntegerRotationConstraintGenerator::Approach::kBoxSphereIntersection}),::testing::ValuesIn< std::vector< int >>({1, 2, 3}))   
)
bool drake::solvers::IsVariableInList ( const std::list< symbolic::Variable > &  variable_list,
const symbolic::Variable variable 
)
std::shared_ptr<Cost> drake::solvers::MakeFunctionCost ( FF &&  f)

Converts an input of type F to a nonlinear cost.

Template Parameters
FFThe forwarded function type (e.g., const F&,F&&, ...). The classF` should have functions numInputs(), numOutputs(), and eval(x, y).
See also
detail::FunctionTraits.

Here is the caller graph for this function:

std::shared_ptr< QuadraticCost > MakeL2NormCost ( const Eigen::Ref< const Eigen::MatrixXd > &  A,
const Eigen::Ref< const Eigen::VectorXd > &  b 
)

Creates a cost term of the form | Ax - b |^2.

Here is the call graph for this function:

Here is the caller graph for this function:

shared_ptr<QuadraticCost> drake::solvers::MakeQuadraticErrorCost ( const Eigen::Ref< const MatrixXd > &  Q,
const Eigen::Ref< const VectorXd > &  x_desired 
)

Here is the caller graph for this function:

std::shared_ptr<QuadraticCost> drake::solvers::MakeQuadraticErrorCost ( const Eigen::Ref< const Eigen::MatrixXd > &  Q,
const Eigen::Ref< const Eigen::VectorXd > &  x_desired 
)

Creates a cost term of the form (x-x_desired)'Q(x-x_desired).

bool drake::solvers::MathProgHasBinaryVariables ( const MathematicalProgram prog)

Determines if the mathematical program has binary variables.

Here is the call graph for this function:

MatrixDecisionVariable< 3, 3 > NewRotationMatrixVars ( MathematicalProgram prog,
const std::string &  name = "R" 
)

Allocates a 3x3 matrix of decision variables with the trivial bounding box constraint ensuring all elements are [-1,1], and the linear constraint imposing -1 <= trace(R) <= 3.

Here is the call graph for this function:

Here is the caller graph for this function:

bool operator!= ( const SolverId a,
const SolverId b 
)
std::ostream & operator<< ( std::ostream &  os,
const IntervalBinning binning 
)

Here is the call graph for this function:

std::ostream & operator<< ( std::ostream &  os,
SolutionResult  solution_result 
)

Here is the call graph for this function:

Here is the caller graph for this function:

std::ostream & operator<< ( std::ostream &  os,
const SolverId self 
)
std::ostream & operator<< ( std::ostream &  os,
const MixedIntegerRotationConstraintGenerator::Approach type 
)

Here is the call graph for this function:

bool operator== ( const SolverId a,
const SolverId b 
)
symbolic::Expression drake::solvers::ReplaceBilinearTerms ( const symbolic::Expression e,
const Eigen::Ref< const VectorXDecisionVariable > &  x,
const Eigen::Ref< const VectorXDecisionVariable > &  y,
const Eigen::Ref< const MatrixX< symbolic::Expression >> &  W 
)

Replaces all the bilinear product terms in the expression e, with the corresponding terms in W, where W represents the matrix x * yᵀ, such that after replacement, e does not have bilinear terms involving x and y.

For example, if e = x(0)*y(0) + 2 * x(0)*y(1) + x(1) * y(1) + 3 * x(1), e has bilinear terms x(0)*y(0), x(0) * y(1) and x(2) * y(1), if we call ReplaceBilinearTerms(e, x, y, W) where W(i, j) represent the term x(i) * y(j), then this function returns W(0, 0) + 2 * W(0, 1) + W(1, 1) + 3 * x(1).

Parameters
eAn expression potentially contains bilinear products between x and y.
xThe bilinear product between x and y will be replaced by the corresponding term in W. Throws a runtime error if x contains duplicate entries.
yThe bilinear product between x and y will be replaced by the corresponding term in W.Throws a runtime error ify` contains duplicate entries.
WBilinear product term x(i) * y(j) will be replaced by W(i, j). If W(i,j) is not a single variable, but an expression, then this expression cannot contain a variable in either x or y. The program will throw a runtime error, if W(i, j) is not a single variable, and also contains a variable in x or y.
Returns
The symbolic expression after replacing x(i) * y(j) with W(i, j).
Expression drake::solvers::ReplaceBilinearTerms ( const Expression &  e,
const Eigen::Ref< const VectorXDecisionVariable > &  x,
const Eigen::Ref< const VectorXDecisionVariable > &  y,
const Eigen::Ref< const MatrixX< symbolic::Expression >> &  W 
)

Here is the call graph for this function:

void drake::solvers::RunLCP ( const Eigen::MatrixBase< Derived > &  M,
const Eigen::VectorXd &  q,
const Eigen::VectorXd &  expected_z_in 
)

Here is the call graph for this function:

Here is the caller graph for this function:

SolutionResult drake::solvers::SolveUnconstrainedQP ( const Eigen::Ref< const Eigen::MatrixXd > &  G,
const Eigen::Ref< const Eigen::VectorXd > &  c,
double  feasibility_tol,
Eigen::VectorXd *  x 
)

Solves the un-constrained QP problem min 0.5 * xᵀ * G * x + cᵀ * x.

Here is the caller graph for this function:

drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
SelectSubMatrixWithCovering   
)

Here is the call graph for this function:

drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
SelectSubColumnWithCovering   
)

Here is the call graph for this function:

drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
SelectSubVector   
)
drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
SetSubVector   
)
drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
ValidateIndices   
)
drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
IsEachUnique   
)
drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
LemkePivot   
)

Here is the call graph for this function:

drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
ConstructLemkeSolution   
)

Here is the call graph for this function:

drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
DetermineIndexSets   
)
drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
FindComplementIndex   
)
drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
FindBlockingIndex   
)
drake::solvers::TEST_F ( UnrevisedLemkePrivateTests  ,
FindBlockingIndexCycling   
)
drake::solvers::TEST_P ( TestMinimumDistance  ,
Test   
)
drake::solvers::TEST_P ( TestMinimumDistanceWOrthonormalSocp  ,
Test   
)

Here is the call graph for this function:

std::string to_string ( SolutionResult  solution_result)

Here is the caller graph for this function:

std::string to_string ( IntervalBinning  binning)
std::string to_string ( MixedIntegerRotationConstraintGenerator::Approach  type)

Here is the caller graph for this function:

Variable Documentation

const double epsilon = 5e-14