Why is CVX 2.0 not solving the dual problem?

1

I have a project in which I am solving the following problem using CVX:

$$\underset{x}{\text{minimize}} \quad ||Ax-b||_2 + \lambda||x||_1$$

Where A, x, and b are all complex. Without changing any of the code, this problem gets solved in two different ways on two different machines. On machine 1, I get a message stating “For improved efficiency, sedumi is solving the dual problem.” but on machine 2 I receive no such message. Both machines give the same answer in the end, but machine 2 take about 5 times longer to get to that answer. My question is Why does CVX decide to solve the dual problem on one machine, yet does not on the other machine? Do I have any control over this?

This is the code used to invoke CVX:

cvx_begin
    cvx_solver sedumi
    variable x(size(A,2)) complex
    minimize ( norm(A*x - b) + lambda*norm(x,1) )
cvx_end

Below is the version information for each machine:

MACHINE 1:

CVX version 1.22
    Code: build 841, 2012-08-16 16:01:21
    Documentation: build 827, 2012-02-01 09:48:08
MATLAB version 7.14 (R2012a)

MACHINE 2:

CVX version 2.0 (beta)
    Code: build 973, 2013-07-12 17:09:25
    Documentation: build 970, 2013-0702 20:55:39
MATLAB version 8.0 (R2012b)
2

Thanks for the interesting question! As you may know, all convex optimization problems have a dual problem, and this dual is also convex. In nearly all useful cases, solving the primal problem allows you to obtain the full solution to the dual problem, and vice versa. Sometimes the primal problem is a better fit for the underlying solver, and sometimes the dual is. CVX has to use a heuristic approach to determine which one would be the most efficient choice for a given solver. I call this “automatic dualization.”

Unfortunately, that heuristic is not perfect, as you are seeing. If you wouldn’t mind filing a bug report to http://support.cvxr.com with an example data set, I’ll see if there are obvious flaws in the heuristic that should be corrected in this case. Otherwise, it might be reasonable for me to consider whether or not I should expose the ability to force CVX to solve the dual problem (or prevent it from doing so), so that users can override the heuristic.

I should point out that at this time, CVX does not perform automatic dualization in Gurobi, because its solver interface doesn’t provide quite the level of primal/dual symmetry that I would like. I’m in regular contact with them, though, and as their solver evolves I will revisit this choice. In my view, CVX should not be doing automatic dualization at all—the solver should! Indeed, Gurobi and MOSEK do perform automatic dualization in some cases, but I would like to see them do more. SDPT3 and SeDuMi are unlikely to ever do so, so CVX will always need automatic dualization in its code.