CVX 3.0 beta interesting features


(Lucas) #1

Does anyone know what new features have been added to CVX 3.0 beta??
Anything like new capabilities for sparsity or chordal sparsity patterns?

I’d like to give it a try, should it have new interesting features…


(Mark L. Stone) #2

I don’t think there are new cap[abilities in CVX 3.0beta for sparsity or chordal sparsity patterns. I don’t know whether there have been any improvements inside solvers callable from CVX, such as Mosek. A Mosek,developer, @Joachim_Dahl is co-author of “Linear matrix inequalities with chordal sparsity patterns andapplications to robust quadratic optimization” http://www.seas.ucla.edu/~vandenbe/publications/cacsd10.pdf

For info on changes in CVX 3.0beta vs. CVX 2.1, read the top text box at http://cvxr.com/cvx/beta/ and the links provided there.

The most significant changes can be found in the DCP ruleset section, due to the introduction of sign-sensitive convexity analysis.

Unfortunately, CVX 3.0beta is riddled with serious bugs, so use at your own peril.

One other thing CVX 3.0beta offers is the ability to use the native exponential cone capability of ECOS abd SCS. Unfortunately, the likelihood of encountering CXV 3.0beta bugs when trying to do so may negate this advantage. Also, CVXQUAD is now available for use under CVX, and that alows CVX;'s Successive Approximation method to be avoided - see CVXQUAD: How to use CVXQUAD's Pade Approximant instead of CVX's unreliable Successive Approximation for GP mode, log, exp, entr, rel_entr, kl_div, log_det, det_rootn, exponential cone. CVXQUAD's Quantum (Matrix) Entropy & Matrix Log related functions


#3

There are no new features for semidefinite optimization in MOSEK 9. Perhaps we will investigate new possibilities in MOSEK 10.

The current state of exploiting chordal sparsity requires a good deal of knowledge and is not easy to fit into a modeling language such as CVX. The chordal conversion methods are most interesting for large very sparse SDPs, which is not what CVX was designed for. A few users (including Martin Andersen) have succesfully solved very large chordal SDPs using MOSEK, but it required careful implementation using the solver API.


(Lucas) #4

Dear @Joachim_Dahl

thanks for that valuable information. By the way, you’re one of the coauthors of the solver conelp implemented in cvxopt, not written for matlab though, but which can be coupled with chompack developed by Andersen and Vanderberghe to solve problems with chordal patterns. My question to you then is: if I know that my problem is both convex and has chordal sparse structure for all blocks (SOCPs and SDP blocks), then is it enough to apply the chordal conversion implemented in chompack (theory by fukuda et al.) so that the solver conelp takes advantage of the structure?


#5

CHOMPACK cannot be used directly with CVXOPT, but it is used in SMCP by Martin Andersen.

I think currently the most competitive method is to perform the chordal conversion manually and then solve the problem using MOSEK.


(Lucas) #6

By manually you mean writing the problem in conic form, do the chordal conversion using Fukuda et al method and then passing it to MOSEK outside CVX or is there a way to use CVX’s modelling capabilities along the way?


#7

I mean what you wrote.


(Lucas) #8

@Joachim_Dahl,

Even though I rewrite a chordal convex problem in conic form so that Mosek hopefully does its job faster due to chordality, chordal sparsity is actually not doing the trick since the conic form does not have the exact same sparsity pattern as the originally chordal formulation. Then what is Mosek taking advantage of to reach faster performance?
Or can I actually say that the conic equivalent to separate blocks of SOCPS and SDPs retains chordality?


#9

I am not sure I understand the question.

MOSEK does not exploit chordal structure explicitly - MOSEK is a very general purpose code, similar to SeDuMi and SDPT3.

You can convert sparse SDPs manually to chordal form and feed them into MOSEK, but you have to do more than recognize chordal structure; you have use a so-called “chordal conversion” method, which involves adding extra constraints. For example, a chordal matrix [x11 x12 0; x21 x22 x23; 0 x32 x33] can be modeled in MOSEK as two smaller 2x2 matrices Y = [ x11 x12; x21 x22], Z = [z11 x23; x32 x33] with the additional constraint that x22=z11.

But MOSEK will not assist you in that. As to why you should use the MOSEK API directly, that is just based on our observation that the modeling time in CVX or Yalmip is prohibitive for large models, and exceeds the solution-time by a large factor. And apparently the resulting MOSEK problem (using CVX or Yalmip) is not as parsimonious as an implementation using the MOSEK API/Fusion directly, but I encourage you to try both.

A good reference is:

Martin also co-authored a very extensive survey on semidefinite optimization over chordal matrices.