MakeSemidefiniteRelaxation: additional tightening constraints for convex quadratics

[TobiaMarcucci]

As by the discussion with @RussTedrake @AlexandreAmice @bernhardpg @iamsavva this morning, we can improve MakeSemidefiniteRelaxation as follows.

For any (convex) quadratic constraint of the form x^T A x <= b^T x + c such that A is PSD we can add the following additional constraints to the SDP relaxation:

1. Enforce x^T A x <= b^T x + c also for the entries of the PSD matrix that is constructed in the SDP relaxation.
2. This constraint can be rewritten as (1, b^T x + c, L x) in RSOC where L^TL=A is the Cholesky factorization and RSOC is the rotated second order cone. Then if d^T x + e >= 0 is a linear constraint in the original nonconvex problem (or any valid linear constraint), we can also add the constraint (d^x + e, b^T x x^T d + e b^T x + c d^T x + c e, L x x^T d + e L x) in RSOC which is an SOC constraint in the entries of the PSD matrix.
3. Potentially, we could also think of taking products of these SOC constraints by themselves. @AlexandreAmice has studied the literature on this. These products might be nicely representable as additional SDP constraints.

@RussTedrake @AlexandreAmice @bernhardpg @iamsavva Please let me know if you think this summarizes our discussion well.

[iamsavva]

nit: though Lorentz Cone is subset of Rotated Lorentz Cone, but by the same token as 2, one could also add "Linear x Lorentz Cone" constraints, they too are linear in the entries of the SDP variables.

Should this be added? Given that LorentzConeConstraint and RotatedLorentzConeConstraints are two different classes, I imagine that they are treated differently under the hood in drake, though I don't know.

[TobiaMarcucci]

I would not say that Lorentz Cone is a subset of Rotated Lorentz Cone. They are the same thing except for a rotation matrix. I think by doing what you say you get the same constraints twice.

[iamsavva]

I meant that the set of sets representable as a Lorentz Cone is subset of the set of sets representable as a Rotated Lorentz Cone. Of course, any set representable as Rotated Lorentz Cone can be represented with Lorentz Cone in rotated coordinates.

Say I have AddLorentzConeConstraint(e2, e1) and AddLinearConstraint(l1 >= 0), where l1 and e1 are linear expressions, e2 is quadratic. It seems to me that at the SDP relaxation, we should AddLorentzConeConstraint(e2*l1^2, e1*l1), unless it's already added via the RotatedLorentzCone procedures you outlined (I don't know, would it be?).

[sherm1]

Assigned to Russ for disposition

[bernhardpg]

@TobiaMarcucci looks right to me.

Is there any reason to prefer the RSOC formulation over the SOC formulation for adding convex quadratic constraints (and the same question for the product Convex Quadratic x Linear)?

[TobiaMarcucci]

@iamsavva i don't think that's correct. SOCs and rotated SOCs are the same families of sets, but one has an invertible rotation matrix in front. They have the same representation power.

@bernhardpg No particular reason to use rotated SOCs except for the fact that they make the math easier. Expressing a quadratic inequality as a normal SOC is a little more involved.

[iamsavva]

@TobiaMarcucci I'm sorry, my mistake, you are entirely correct! Didn't realize I had a some big errors in my head on the differences between SOC and RSOC. Thanks for your patience, man.

[iamsavva]

A question still. Drake has QuadraticConstraint, LorentzConeConstraint, RotatedLorentzConeConstraint classes. I'm worried that among these three, only RSOC will be multiplied by linear constraints. For completeness sake, would we need a translation layer that translates each of these three into RSOC? Do you know if drake already does something like this under the hood?

[AlexandreAmice]

As discussed offline: 1.) Is likely redundant. The linearization of the quadratic constraint should be sufficient to imply the original quadratic constraints. I'll write a proof for reference. 2 and 3) These are in the pipeline, I will need to find time to finish the implementation.

[bernhardpg]

1.) Is indeed redundant, I have the proof in my notes. I'd be happy to do a writeup of the proof somewhere (unsure about the best format; is this something that goes in the Drake docs?). For convex quadratic constraints, we should only add the linearized version, as it implies the original convex constraint.

On another but related note: For general SOCCs we should only keep the SOCC (right now we don't have support for keeping these around in the relaxation). It can actually be weaker to square the constraint and add it as a quadratic + linear constraint which are then linearized. It is fairly easy to come up with simple examples in R^2 that are feasible for the linearized version but not for the SOCC

[AlexandreAmice]

I would think that if you add the product of the quadratic and the linear constraint along with quadratic + linear constraint that implies the SOCC then you wouldn't lose this tightness, but again I would need to check the proof.