# Comparing the complexity of two conic problems solved using CVX and MOSEK

I’m solving two similar convex conic optimization problems. One of the problems has a lesser number of constraints and optimization varaiables compared to the other, hence I expect it to have a lower run-time/computational complexity. However, it is not the case.

``````cvx_begin

variable Q(m,n) complex

C = G + A*Q*B
objective=max(max(abs(C)));
minimise (objective);

# Constraint 1
pow_pos((norm(A*Q,'fro')),2) + 2*sum(real(diag(X*A*Q))) <= alpha;

``````

Problem 2 (P2):

``````cvx_begin

variable T(l,n) complex

C = G + T*B
objective=max(max(abs(C)));
minimise (objective);

# Constraint 1
pow_pos((norm(T,'fro')),2) + 2*sum(real(diag(X*T))) <= alpha;

# Constraint 2
for k=1:K
E, Hk, S;                         # E ,Hk, and S  are known constant matrices
temp_n=0;
for n_in=1:N_in
evec = E(:,n_ind);
T_tild=[zeros(l,r),T,zeros(l,r)];
temp_n = temp_n + ((evec).*trace(Hk* fliplr(T_tild(:,n_ind:n_ind+r))));
end
temp_n = temp_n + S(k,:);
temp_UE=[temp_UE, pow_pos(norm(temp_n,2),2)];
end
sum(temp_UE) <=  beta;

``````

Considering the optimization variables in P1 and P2, m < l. i.e., P1 has less optimization variables than P2. Further, B in both problems is sparse.

Considering the similarity between the problems, I believe, P1 is a simpler problem compared to P2, as P1 has less optimization variables and only one constraint. This can also be confirmed from the log-files of the optimizer. Hence, I expect P1 to be solved faster than the P2.

Log File of P1:

``````Calling Mosek 9.1.9: 35972 variables, 10625 equality constraints
For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:27:13)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: Linux/64-X86

MOSEK warning 710: #2434 (nearly) zero elements are specified in sparse col '' (35969) of matrix 'A'.
Problem
Name                   :
Objective sense        : min
Type                   : CONIC (conic optimization problem)
Constraints            : 10625
Cones                  : 7938
Scalar variables       : 35972
Matrix variables       : 0
Integer variables      : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 1                 time                   : 0.00
Lin. dep.  - tries                  : 1                 time                   : 0.45
Lin. dep.  - number                 : 0
Presolve terminated. Time: 1.62
Problem
Name                   :
Objective sense        : min
Type                   : CONIC (conic optimization problem)
Constraints            : 10625
Cones                  : 7938
Scalar variables       : 35972
Matrix variables       : 0
Integer variables      : 0

Optimizer  - solved problem         : the primal
Optimizer  - Constraints            : 2686
Optimizer  - Cones                  : 7938
Optimizer  - Scalar variables       : 28033             conic                  : 27908
Optimizer  - Semi-definite variables: 0                 scalarized             : 0
Factor     - setup time             : 3.69              dense det. time        : 0.00
Factor     - ML order time          : 0.42              GP order time          : 0.00
Factor     - nonzeros before factor : 3.36e+06          after factor           : 3.36e+06
Factor     - dense dim.             : 0                 flops                  : 1.70e+10
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME
0   6.4e+01  1.0e+00  2.3e+00  0.00e+00   1.320000000e+00   0.000000000e+00   1.0e+00  7.47
1   7.9e+00  1.2e-01  6.2e-01  -9.28e-01  -1.241490807e+01  -9.202494843e+00  1.2e-01  8.10
2   5.7e-01  8.9e-03  2.7e-03  1.00e+00   -5.684195155e+00  -5.727791137e+00  8.9e-03  8.59
3   2.9e-01  4.6e-03  1.1e-03  5.55e+00   -8.744247122e-01  -8.714346161e-01  4.6e-03  9.04
4   1.5e-01  2.3e-03  2.4e-04  2.68e+00   -4.216794418e-01  -4.217316575e-01  2.3e-03  9.51
5   1.2e-01  1.8e-03  1.6e-04  1.97e+00   -3.660731467e-01  -3.661161296e-01  1.8e-03  10.07
6   6.6e-02  1.0e-03  6.2e-05  1.72e+00   -3.084925217e-01  -3.085242456e-01  1.0e-03  10.54
7   2.7e-02  4.2e-04  1.5e-05  1.30e+00   -2.868755690e-01  -2.869192276e-01  4.2e-04  11.01
8   2.1e-03  3.2e-05  1.6e-07  1.07e+00   -2.781946659e-01  -2.782100569e-01  3.2e-05  11.59
9   1.1e-03  1.7e-05  5.6e-08  1.00e+00   -2.779007636e-01  -2.779090666e-01  1.7e-05  12.14
10  3.4e-04  5.3e-06  8.6e-09  1.00e+00   -2.777193395e-01  -2.777220305e-01  5.3e-06  12.62
11  4.0e-05  6.3e-07  3.0e-10  1.00e+00   -2.776622393e-01  -2.776625785e-01  6.3e-07  13.13
12  5.8e-06  9.1e-08  1.7e-11  1.00e+00   -2.776588444e-01  -2.776588935e-01  9.1e-08  13.65
13  2.3e-07  3.6e-09  1.3e-13  1.00e+00   -2.776583692e-01  -2.776583711e-01  3.6e-09  14.20
14  3.7e-08  5.8e-10  8.4e-15  1.00e+00   -2.776583523e-01  -2.776583526e-01  5.8e-10  14.67
Optimizer terminated. Time: 15.38

Interior-point solution summary
Problem status  : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal.  obj: -2.7765835232e-01   nrm: 1e+00    Viol.  con: 1e-08    var: 8e-12    cones: 0e+00
Dual.    obj: -2.7765835263e-01   nrm: 1e+00    Viol.  con: 0e+00    var: 1e-10    cones: 0e+00
Optimizer summary
Optimizer                 -                        time: 15.38
Interior-point          - iterations : 14        time: 15.35
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
Simplex                 -                        time: 0.00
Primal simplex        - iterations : 0         time: 0.00
Dual simplex          - iterations : 0         time: 0.00
Mixed integer           - relaxations: 0         time: 0.00

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.277658

``````

Log file of P2

``````Calling Mosek 9.1.9: 36533 variables, 12193 equality constraints
For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:27:13)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: Linux/64-X86

MOSEK warning 710: #3968 (nearly) zero elements are specified in sparse col '' (31889) of matrix 'A'.
MOSEK warning 710: #3968 (nearly) zero elements are specified in sparse col '' (31890) of matrix 'A'.
MOSEK warning 710: #3840 (nearly) zero elements are specified in sparse col '' (31891) of matrix 'A'.
MOSEK warning 710: #3840 (nearly) zero elements are specified in sparse col '' (31892) of matrix 'A'.
MOSEK warning 710: #3712 (nearly) zero elements are specified in sparse col '' (31893) of matrix 'A'.
MOSEK warning 710: #3712 (nearly) zero elements are specified in sparse col '' (31894) of matrix 'A'.
MOSEK warning 710: #3584 (nearly) zero elements are specified in sparse col '' (31895) of matrix 'A'.
MOSEK warning 710: #3584 (nearly) zero elements are specified in sparse col '' (31896) of matrix 'A'.
MOSEK warning 710: #3456 (nearly) zero elements are specified in sparse col '' (31897) of matrix 'A'.
MOSEK warning 710: #3456 (nearly) zero elements are specified in sparse col '' (31898) of matrix 'A'.
Warning number 710 is disabled.
Problem
Name                   :
Objective sense        : min
Type                   : CONIC (conic optimization problem)
Constraints            : 12193
Cones                  : 7954
Scalar variables       : 36533
Matrix variables       : 0
Integer variables      : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 1                 time                   : 0.00
Lin. dep.  - tries                  : 1                 time                   : 0.01
Lin. dep.  - number                 : 0
Presolve terminated. Time: 0.09
Problem
Name                   :
Objective sense        : min
Type                   : CONIC (conic optimization problem)
Constraints            : 12193
Cones                  : 7954
Scalar variables       : 36533
Matrix variables       : 0
Integer variables      : 0

Optimizer  - solved problem         : the primal
Optimizer  - Constraints            : 4237
Optimizer  - Cones                  : 7954
Optimizer  - Scalar variables       : 28577             conic                  : 28452
Optimizer  - Semi-definite variables: 0                 scalarized             : 0
Factor     - setup time             : 0.35              dense det. time        : 0.07
Factor     - ML order time          : 0.02              GP order time          : 0.00
Factor     - nonzeros before factor : 7.59e+05          after factor           : 1.91e+06
Factor     - dense dim.             : 501               flops                  : 1.04e+09
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME
0   6.4e+01  1.0e+00  1.1e+01  0.00e+00   1.030541315e+01   0.000000000e+00   1.0e+00  0.55
1   7.9e+00  1.2e-01  2.2e+00  -7.77e-01  -3.577327873e+00  -5.809320896e+00  1.2e-01  0.71
2   5.0e-01  7.8e-03  1.9e-02  1.07e+00   -3.468365188e+00  -3.583730269e+00  7.8e-03  0.89
3   2.4e-01  3.7e-03  4.3e-03  3.48e+00   -7.777946909e-01  -7.972427757e-01  3.7e-03  1.00
4   7.6e-02  1.2e-03  3.8e-04  3.01e+00   -2.757885031e-01  -2.785334514e-01  1.2e-03  1.13
5   3.3e-02  5.1e-04  9.2e-05  1.91e+00   -2.066096351e-01  -2.075226164e-01  5.1e-04  1.25
6   1.7e-02  2.6e-04  2.9e-05  1.29e+00   -1.919600443e-01  -1.924091784e-01  2.6e-04  1.39
7   7.2e-03  1.1e-04  7.3e-06  1.12e+00   -1.864513861e-01  -1.866502557e-01  1.1e-04  1.51
8   3.4e-04  5.2e-06  2.9e-08  1.05e+00   -1.824842439e-01  -1.824945119e-01  5.2e-06  1.66
9   2.6e-04  4.1e-06  1.9e-08  1.00e+00   -1.824459142e-01  -1.824538679e-01  4.1e-06  1.78
10  1.6e-04  2.5e-06  9.0e-09  1.00e+00   -1.823688436e-01  -1.823736998e-01  2.5e-06  1.89
11  6.3e-05  9.9e-07  2.2e-09  1.00e+00   -1.823278397e-01  -1.823297760e-01  9.9e-07  2.01
12  2.7e-06  6.3e-08  1.7e-11  1.00e+00   -1.822956920e-01  -1.822957741e-01  4.2e-08  2.16
13  1.2e-06  1.7e-06  5.2e-12  1.00e+00   -1.822951534e-01  -1.822951907e-01  1.9e-08  2.28
14  1.8e-07  1.9e-06  2.9e-13  1.00e+00   -1.822947950e-01  -1.822948004e-01  2.8e-09  2.42
Optimizer terminated. Time: 2.46

Interior-point solution summary
Problem status  : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal.  obj: -1.8229479496e-01   nrm: 1e+00    Viol.  con: 3e-08    var: 2e-11    cones: 0e+00
Dual.    obj: -1.8229480045e-01   nrm: 8e+00    Viol.  con: 0e+00    var: 6e-16    cones: 0e+00
Optimizer summary
Optimizer                 -                        time: 2.46
Interior-point          - iterations : 14        time: 2.45
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
Simplex                 -                        time: 0.00
Primal simplex        - iterations : 0         time: 0.00
Dual simplex          - iterations : 0         time: 0.00
Mixed integer           - relaxations: 0         time: 0.00

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.182295
``````

It can be seen from the log files that P1 has a less number of constraints and variables than P2. However, P2 consumes much less time than P1. I would like to understand this behavior and take steps to fasten-up solving P1.

Here is my attempt:

My guess is, P2 has approximately 10 times less flops than P1. This makes P2 to be solved faster.

From few trial and error attempts, I understood that the difference in the flops in P1 and P2 originates from the difference in objective function of the problems. i.e., from (AQB) and (T*B) in P1 and P2, respectively.

1, Is my reasoning based on flops correct ? if not, why can P2 be solved much faster than P1 ?

2, If my reasoning is correct, Is there a way to rewrite the objective function of P1, such that it has less flops and hence less computation time than P2? (an additional tip A’*A=Identity matrix)

3, In general, is there a way to show theoretically or by CVX simulation time, that P1 is less complex and hence requires less computational effort than P2 ?

In my work, I’m considering to propose P1 as a low complexity alternative to P2. But I’m surprised to see that it is not, despite having less constraints and optimization variables.

then you will realize that the practical computational complexity is not based on the number of constraints and variables only.

Thanks @Erling for the blog.

I understand MOSEK uses a bunch of tricks that speed up the practical performance, which destroys the theoretical complexity proof. However, I can’t understand the exact trick that contributes to the difference in run-time between this problems.

Considering the similarity between the problems, do you think it is possible to identify the reason and rewrite the problem P1 so that it has less run time than P2 ?

Regards,
Abdur

For a given problem it is a NP hard problem to compute the minimal number of flops required to solve the problem. This implies although one formulation is better in theory it may not be the case in practice.

From what I see from your log output I cannot tell you the specific reason why one formulation is better than the other. I can see Mosek detects dense columns and/or high dimensional cones in the P2 version (dense dim.). This is done by a heuristic which is not perfect so maybe luck/unluck plays a role.

Note you use an old version of Mosek. Things can be different if you use the latest version.

Finally, observe CVX somehow converts your problem into a problem that Mosek can solve.
I have no idea what transformations Cvx does to achieve this and that makes it even tougher to answer your question.