Conic Form of Constraints

[AlexandreAmice]

Is your feature request related to a problem? Please describe. A number of AddConstraint methods in MathematicalProgram do not return types of Binding<Constraint>. Examples include AddSosConstraint which returns the Gram matrix of the SOS polynomial and AddPositiveDiagonallyDominantMatrixConstraint which returns the slack variables used to implement the constraint. This is awkward for a couple of reasons:

1. It makes removing these constraints almost impossible, as these methods silently for example add e.g. several linear constraints and introduce several spurious new variables.
2. These constraints mathematically represent one idea, yet get implemented as a scattered collection which cannot be grouped. This makes doing things like extracting dual variables almost impossible.

Describe the solution you'd like I would like to introduce some notion of AbstractConicConstraint which is nothing more than Ax+b lives in some cone.

A conic constraint should always know how to write an extended formulation of itself in terms of the "standard symmetric" cones dilineated here so that passing to the solver is easy.

Moreover, given a MathematicalProgramResult from the extended formulation, a conic constraint should know how to construct it's corresponding dual variable. Therefore, every AbstractConicConstraint must implement its dual cone.

For example implementing PositiveDiagonallyDominantMatrixConstraint should imply implementing PositiveDiagonallyDominantDualConeMatrixConstraint

Additional context The current structure of Constraint and Binding makes the implementation of this proposal awkward. We take the example of PositiveDiagonallyDominantConstraint. The extended formulation of "X is PositiveDiagonallyDominant" that we use in Drake is:

1. Introduce a symmetric "slack variable" Y.
2. Add the constraints -Yᵢⱼ ≤ Xᵢⱼ ≤ Yᵢⱼ for i < j and Xᵢᵢ == yᵢᵢ
3. Add the constraint Xᵢᵢ ≥ ∑ⱼYᵢⱼ.

Notice that an extended formulation almost always requires introducing new variables. Since Constraint has no concept of variables then it seems like the responsibility for providing an extended formulation should lie in the class Binding<ConicConstraintImpl>. However, this somewhat departs from the current very lightweight, header-only implementation of Binding.

[AlexandreAmice]

cc @hongkai-dai @RussTedrake @jwnimmer-tri for discussion on the design.

[hongkai-dai]

If the proposal is to add new class PositiveDiagonallyDominantMatrixConstraint, derived from the abstract Constraint class, then inside SolverInterface::Solve() function, we need to convert this PositiveDiagonallyDominantMatrixConstraint to a bunch of second order cone constraints with slack variables. These converted second order cone constraints, together with the slack variables are destroyed at the end of SolverInterface::Solve(), and MathematicalProgramResult cannot retrieve any information on these second order cone constraints or slack variables.

I would propose to change the return type of AddPositiveDiagonallyDominantMatrixConstraint. We can create a new struct PositiveDiagonallyDominantMatrixReturnType as

struct PositiveDiagonallyDominantMatrixReturnType {
  VectorXDecisionVariable slack;
  std::vector<Binding<LorentzConeConstraint>> soc;
  Binding<LinearEqualityConstraint> lin_eq;
}

and a function MathematicalProgram::RemoveConstraint(const PositiveDiagonallyDominantMatrixReturnType ) to remove the constraints and slack variables.

[AlexandreAmice]

The PositiveDiagonallyDominantMatrix was only meant to be an illustrative example of a conic constraint that has an extended formulation in terms of the "standard" cones. The SOS, l1, and l_infty cones are other examples.

The proposition is to add a new abstract class ConicConstraint derived from Constraint which all of our conic constraints would derive from. This would make it easier to e.g. convert programs to standard form, algorithmically take duals, and get meaningful dual solutions.

I will hopefully have a draft PR up soon that may make some of these points clearer.