Implement interface for conic programming in C++

[hongkai-dai]

This is meant to introduce conic programming (SOCP, SDP) and their mixed-integer counterparts (MILP,MIQP,MISOCP,MISDP) into Drake.

We have at least two solvers that (partially) support these optimization problems

	LP	QP	SOCP	SDP	MILP	MIQP	MISOCP	MISDP
Gurobi	Y	Y	Y	N	Y	Y	Y	N
Mosek	Y	Y	Y	Y	Y	Y	Y	N
SCIP					Y	Y	Y	Y

Notice that SCIP is not free for commercial users. LP and QP are already in Drake now. SDP with Mosek was introduced from #3072 .

My plan is to build the interface more like spotprog, but as a sub-class of OptimizationProblem. Namely, it should support following function calls

• AddContinuousVariables, this should be like withFreeVar in spotprog, to add a vector of continuous decision variables.
• AddSymmetricMatrixVariables, this should be like withSym in spotprog, to add a symmetric matrix as decision variables
• AddIntegerVariables, this was commented out in OptimizationProblem, I will turn it on.

There are two types of new conic constraints, the second order cone constraint, and the positive semi-definite matrix constraint

• LorentzConeConstraint, this imposes a constraint x0>=sqrt(x_1^2+...+x_n^2). It can have a Eval function that evaluates x_0-sqrt(x_1^2+...+x_n^2), in case we want to solve the socp as a nonlinear optimization problem.
• RotatedLorentzConeConstraint, this imposes the constraint x0*x1>=sqrt(x_2^2+...+x_n^2). It can have a Eval function that evaluates x0*x1-sqrt(x_2^2+...+x_n^2, in case we want to solve the socp as a nonlinear optimization problem.
• PositiveSemidefiniteConstraint, this imposes a constraint X is psd for a symmetric matrix X. It does not have an Eval function. (Maybe later supports to evaluate X = Y*Y', but not in the initial implementation.) This constraint can only be used inside SDP problem.

For a symmetric matrix X, we will also support the inner product trace(A*X'). So we will introduce a constraint MatrixInnerProductConstraint as

lb <= trace(A*X') <= ub

[hongkai-dai]

@rdeits , @RussTedrake what do you think about this?

[RussTedrake]

this sounds great to me. but i'm not sure if we want to subclass OptimizationProblem, or simply add methods to the main problem.

[hongkai-dai]

OptimizationProblem already has a sub-class SemidefiniteProblem (I think I will need to re-structure part of it). The QP and LP are also in OptimizationProblem. What is the advantage of not subclassing OptimizationProblem, but create a new base class like ConicProgramming?

The conic programming does not fit our OptimizationProblem exactly, as the Lorentz cone and PSD cone are not meant to be evaluated to a scalar. This is probably one counter-argument to subclass from OptimizationProblem.

[RussTedrake]

The design started out as being flat -- there is a single optimization problem class which you can add all of these objectives and constraints and it can figure out what problem type you have dynamically. A major advantage of this approach is that we avoid subclass explosion -- if we have trajectory optimization as a subclass and sdp as a subclass then what happens when we want to add an sdp constraint in a trajectory optimization? I think i'd vote for putting all the new variable and constraint types right into the base class, but would value more comments from the developers

[sherm1]

My 2 cents: flatter is better. One of my favorite books, "API Design for C++" by Martin Reddy says "any more than two or three levels is already getting too complex." Composition is generally better than inheritance.

[hongkai-dai]

@RussTedrake , got it. Sorry I misunderstood it when you say "main problem". I totally agree on the just adding methods to OptimizationProblem class, instead of sub-classing it. @sherm1 , Thanks for referring the book, I also like the flatter one.

[rdeits]

Does the new version of Mosek support MISDP? I'm pretty sure Mosek 7 does not.

[hongkai-dai]

@rdeits, you are right. Mosek does not support mixed integer SDP, even in Mosek 8. Which solver would you recommend for MI-SDP problem? Have you tried cutsdp http://www.swmath.org/software/5123?

[hongkai-dai]

@rdeits , have you tested SCIP? YALMIP does not recommend to use its branch and bound package, for speed reason.

[rdeits]

When I did the UAV work, I used YALMIP's branch-and-bound with Mosek, and it was not great. It was indeed very slow, and I had a lot of problems with Mosek returning the TRM_STALL status which confused the branch-and-bound solver. Ultimately, I ended up just sticking to MISOCP in Mosek for the results I used in the paper.

[rdeits]

I haven't tried SCIP or cutsdp either.

[hongkai-dai]

The last piece missing is the sum-of-squares optimization, which is described in #4421