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 - threads : 24
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 - threads : 24
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.
Thanks in advance.