Drake
drake::solvers Namespace Reference

detail

internal

test

Classes

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

lb ≤ .5 xᵀQx + bᵀx ≤ ub Without loss of generality, the class stores a symmetric matrix Q. More...

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>
 using MapVarToIndex = unordered_map
 using MatrixDecisionVariable = Eigen::Matrix
 using MatrixIndeterminate = Eigen::Matrix

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
 rows The number of rows in the new matrix containing indeterminates. cols The number of columns in the new matrix containing indeterminates.
 using MatrixXDecisionVariable = MatrixDecisionVariable
 using MatrixXIndeterminate = MatrixIndeterminate

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

MatrixIndeterminate<int, int>
 typedef uint32_t RollPitchYawLimits
 using VariableRefList = std::list>
 using VectorDecisionVariable = MatrixDecisionVariable
 using VectorIndeterminate = MatrixIndeterminate

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

Template Parameters
 rows The number of rows in the new matrix containing indeterminates.
MatrixIndeterminate<int, int>
 using VectorXDecisionVariable = VectorDecisionVariable
 using VectorXIndeterminate = VectorIndeterminate

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

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,

Enumerator
kLogarithmic
kLinear
 enum ProgramAttributes
Enumerator
kNoCapabilities
kError

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

kGenericCost
kGenericConstraint
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
 enum SolutionResult
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
 prog The optimization problem to which the constraints will be added. x A variable in the bilinear product. y A variable in the bilinear product. w The 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. Bx The binary-valued expression indicating which interval x is in. Bx(i) = 1 => φˣᵢ ≤ x ≤ φˣᵢ₊₁. By The binary-valued expression indicating which interval y is in. By(i) = 1 => φʸⱼ ≤ y ≤ φʸⱼ₊₁.

One formulation of the constraint is

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ˣʸᵢⱼ)

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̂, ŷ 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̅ᵢ = ∑ⱼ ŷᵢⱼ

and the constraints above can be re-formulated using x̅ and y̅ 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 x̅, y̅, 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::value && is_eigen_vector_of::value && is_eigen_vector_of::value && is_eigen_vector_of::value, MatrixDecisionVariable >::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
 prog The program to which the bilinear product constraint is added x The decision variable. y The decision variable. w The expression to approximate x * y phi_x The end points of the intervals for x. phi_y The end points of the intervals for y. Bx The binary variables for the interval in which x stays encoded as described above. By The binary variables for the interval in which y stays encoded as described above. binning Determine 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
 prog The program to which the SOS1 constraint is added. lambda lambda is in SOS1. y The 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 codes A n x ⌈log₂(n)⌉ matrix. code.row(i) represents integer i. No two rows of codes can be the same.
Exceptions
 std::runtime_error if 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,.

Here is the call graph for this function:

Here is the caller graph for this function:

 std::enable_if< drake::is_eigen_vector_of::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
 prog Add the SOS2 constraint to this mathematical program. lambda At 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_error if 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_error if 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
 prog The MathematicalProgram to which the relaxed constraints are added. x The decision variables which appear in the original non-convex constraint. Q1 A positive semidefinite matrix. Q2 A positive semidefinite matrix. y A vector, the variables in the linear term of the quadratic form. p A vector, the linear coefficients of the quadratic form. linearization_point The vector x₀ in the documentation above. lower_bound The left-hand side of the original non-convex constraint. upper_bound The right-hand side of the original non-convex constraint. trust_region_gap The 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 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_error when 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
 R The rotation matrix num_intervals_per_half_axis number of intervals for a half axis. prog The 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.

AddLogarithmicSos2Constraint for a complete explanation on SOS2 constraint.
Parameters
 prog The optimization program to which the SOS2 constraint is added. lambda At 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. y y(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
 n A 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
 code code(i) should only take binary values. expected The expected matched value for code. match an 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
 b1 An expression that should only take a binary value. b2 An expression that should only take a binary value. b1_and_b2 Should 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
 b1 An expression that should only take a binary value. b2 An expression that should only take a binary value. b1_or_b2 Should 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
 b1 An expression that should only take a binary value. b2 An expression that should only take a binary value. b1_xor_b2 Should 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
 Q A 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
 bmin The innermost corner of the box bmax The outermost corner of the box color The 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
 bmin The innermost corner of the box. bmax The outermost corner of the box. color The 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
 color The 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 drake::solvers::MakeFunctionCost ( FF && f )

Converts an input of type F to a nonlinear cost.

Template Parameters
 FF The forwarded function type (e.g., const F&,F&&, ...). The classF should have functions numInputs(), numOutputs(), and eval(x, y).
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 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 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
 e An expression potentially contains bilinear products between x and y. x The bilinear product between x and y will be replaced by the corresponding term in W. Throws a runtime error if x contains duplicate entries. y The bilinear product between x and y will be replaced by the corresponding term in W.Throws a runtime error ify contains duplicate entries. W Bilinear 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