Automatic dualization

jie · December 1, 2014, 1:18pm

I’m trying to solve a cone optimization problem. I found something different between using CVX/Mosek and directly calling Mosek.

When using CVX/Mosek, I get Mosek reports the problem have 38 constraints while if I call Mosek directly, it reports having 1450 constraints, while the number cones is 289 in both cases. I noticed the following output with cvx
Calling Mosek 7.0.0.140: 1739 variables, 329 equality constraints
For improved efficiency, Mosek is solving the dual problem.

So is CVX dualize the problem automatically for performance reason?
If yes, is there anyway to turn off this automatic dualization behavior in CVX?

For some cases, CVX reports infeasible or fail while directly calling mosek gives valid results. Could this be due to the dualization, that the primal form having multiple optimal solution implies the dual form being infeasible? In this case, what can I do to get valid solution using CVX?
For small optimization problem, calling CVX takes much more (~ 10 times) time than calling Mosek directly. Why this behavior?What could be the bottleneck?

mcg · December 1, 2014, 3:52pm

Yes, dualization is performed for performance reasons. Sometimes the differences are extremely large, which is why it’s needed. There is currently no way to turn off dualization in CVX, but I am experimenting with such a facility for CVX 3.0 beta.

The overhead of calling CVX is simply the cost of convenience. After all, CVX is designed to do a lot of work for you, converting problems into solvable form. For small problems, the fixed costs of using CVX will certainly be more expensive than calling Mosek directly. CVX 3.0 beta has reduced some of that overhead, but it is still there, and it always will be.

CVX is designed for your convenience, not for raw speed. If performance is your goal, and you have determined that using CVX is your bottleneck, you will have to start calling Mosek directly. Since you’re finding that CVX’s reformulation might be introducing some numerical issues, you may indeed need to call Mosek directly, at least until the dualization switch is complete. Of course, you should also try the other solvers, to make sure that the numerical values coincide.

Erling · December 1, 2014, 8:16pm

Figuring out when to dualize is actually quite hard in practice in my exprience. I know because I am responsible for the rules implemented in MOSEK.

Btw MOSEK v8 will most likely have an automatic rule. I already got it working for all conic problems without semidefinite variables. So maybe you do not have dualize in the future in case of MOSEK Michael :-). Maybe that is good news. At least you would be able to blaime MOSEK for bad choices.

Regarding the feasibility issue. Then if you post the MOSEK log for one of the infeasible problems, then I can easily tell whether the infeasibility is genuine i.e. a bug in CVX or in your model.

mcg · December 1, 2014, 9:38pm

Agreed, it is difficult! I do not use a complex rule, so it gets tripped up sometimes. I will be happy to let MOSEK do the dualization when it is ready. But of course, solvers like SeDuMi and SDPT3 do not, so my code will always be necessary.

jie · December 2, 2014, 11:19am

Following is the MOSEK log for one of the infeasible problems,

Calling Mosek 7.0.0.140: 1739 variables, 329 equality constraints
   For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

MOSEK Version 7.0.0.140 (Build date: 2014-11-26 12:50:57)
Copyright (c) 1998-2014 MOSEK ApS, Denmark. WWW: http://mosek.com

Computer
  Platform               : Windows/64-X86
  Cores                  : 4

Problem
  Name                   :
  Objective sense        : min
  Type                   : CONIC (conic optimization problem)
  Constraints            : 329
  Cones                  : 289
  Scalar variables       : 1739
  Matrix variables       : 0
  Integer variables      : 0

Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator - tries                  : 0                 time                   :
 0.00
Eliminator - elim's                 : 0
Lin. dep.  - tries                  : 1                 time                   :
 0.00
Lin. dep.  - number                 : 2
Presolve terminated. Time: 0.00
Optimizer  - threads                : 4
Optimizer  - solved problem         : the primal
Optimizer  - Constraints            : 38
Optimizer  - Cones                  : 289
Optimizer  - Scalar variables       : 1452              conic                  : 1441
Optimizer  - Semi-definite variables: 0                 scalarized             : 0
Factor     - setup time             : 0.00              dense det. time        : 0.00
Factor     - ML order time          : 0.00              GP order time          : 0.00
Factor     - nonzeros before factor : 741               after factor           : 741
Factor     - dense dim.             : 0                 flops                  : 1.16e+006
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME
0   2.8e+000 2.4e+000 1.0e+000 0.00e+000  0.000000000e+000  0.000000000e+000  1.0e+000 0.00
1   2.3e+000 1.9e+000 8.3e-001 4.38e+000  -3.820368780e-001 -9.970535622e-001 8.3e-001 0.01
2   1.8e+000 1.5e+000 6.4e-001 -5.34e-002 -3.001112790e+001 -2.347960132e+001 6.4e-001 0.01
3   7.4e-001 6.3e-001 2.7e-001 1.84e+000  -3.235941588e+001 -2.575373321e+001 2.7e-001 0.01
4   3.0e-001 2.5e-001 1.1e-001 -6.59e-001 -6.787708978e+001 -4.726196885e+001 1.1e-001 0.01
5   1.0e-001 8.8e-002 3.7e-002 -8.39e-001 -1.895324953e+002 -1.304369276e+002 3.7e-002 0.01
6   2.0e-002 1.7e-002 7.1e-003 -9.70e-001 -6.959620230e+002 -4.208365535e+002 7.1e-003 0.01
7   1.3e-003 1.1e-003 4.6e-004 -9.95e-001 -1.070956173e+004 -6.456471961e+003 4.6e-004 0.01
8   6.4e-005 5.4e-005 2.3e-005 -1.00e+000 -2.143920263e+005 -1.293502812e+005 2.3e-005 0.01
9   3.2e-006 2.7e-006 1.2e-006 -1.00e+000 -4.288212327e+006 -2.587330013e+006 1.2e-006 0.01
10  9.6e-011 1.2e-010 9.3e-011 -1.00e+000 -4.288212327e+006 -2.587330013e+006 2.2e-011 0.03
Interior-point optimizer terminated. Time: 0.03.


MOSEK DUAL INFEASIBILITY REPORT.

Problem status: The problem is dual infeasible
Optimizer terminated. Time: 0.05

Interior-point solution summary
  Problem status  : DUAL_INFEASIBLE
  Solution status : DUAL_INFEASIBLE_CER
  Primal.  obj: -1.0708335641e+001  Viol.  con: 5e-011   var: 0e+000   cones: 5e
-011
Optimizer summary
  Optimizer                 -                        time: 0.05
    Interior-point          - iterations : 10        time: 0.03
      Basis identification  -                        time: 0.00
        Primal              - iterations : 0         time: 0.00
        Dual                - iterations : 0         time: 0.00
        Clean primal        - iterations : 0         time: 0.00
        Clean dual          - iterations : 0         time: 0.00
        Clean primal-dual   - iterations : 0         time: 0.00
    Simplex                 -                        time: 0.00
      Primal simplex        - iterations : 0         time: 0.00
      Dual simplex          - iterations : 0         time: 0.00
      Primal-dual simplex   - iterations : 0         time: 0.00
    Mixed integer           - relaxations: 0         time: 0.00

------------------------------------------------------------
Status: Infeasible
Optimal value (cvx_optval): +Inf

Erling · December 2, 2014, 1:52pm

The objective value has to be negative and the ratio -1.0708335641e+001 / 5e-011 large for the certificate to be good. That is the case so I would trust it. There is either modeling error or a CVX bug.

mcg · December 2, 2014, 3:31pm

If you are sure that you’re feeding exactly the same model to Mosek directly and to CVX, feel free to submit a bug report to http://support.cvxr.com with the data and model that reproduces the issue.