I am doing an optimization problem with a data of size 133 x 133 x 50 by calling MOSEK in CVX. There are 2675839 equality constraints. The results are okay, with runtime equal to 40 minutes. My question is whether this runtime can be reduced if I implement the problem outside CVX (but still with MOSEK)? Or is the runtime something independent of CVX?
It depends on whether most of the time is spent inside CVX modeling before calling Mosek or inside Mosek. That should be easy for you to check by comparing the runtime of your full code and the time of the optimizer printed by Mosek in the log.
Maybe you can post the log output?
Thanks. Here’s the log. If the answer is no, then can anyone suggest as to how to speed up the process, because this is just a part of the optimization problem that I am doing, so need to process more such datasets.
Calling Mosek 8.0.0.60: 6200342 variables, 2675839 equality constraints
------------------------------------------------------------
MOSEK Version 8.0.0.60 (Build date: 2017-3-1 13:09:33)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col '' (35741) of matrix 'A'.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col '' (35742) of matrix 'A'.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col '' (35743) of matrix 'A'.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col '' (35744) of matrix 'A'.
MOSEK warning 710: #4 (nearly) zero elements are specified in sparse col '' (35745) of matrix 'A'.
MOSEK warning 710: #4 (nearly) zero elements are specified in sparse col '' (35746) of matrix 'A'.
MOSEK warning 710: #3 (nearly) zero elements are specified in sparse col '' (35747) of matrix 'A'.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col '' (35748) of matrix 'A'.
MOSEK warning 710: #3 (nearly) zero elements are specified in sparse col '' (35749) of matrix 'A'.
MOSEK warning 710: #4 (nearly) zero elements are specified in sparse col '' (35750) of matrix 'A'.
Warning number 710 is disabled.
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 2675839
Cones : 2640053
Scalar variables : 6200342
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
Lin. dep. - tries : 1 time : 0.48
Lin. dep. - number : 0
Presolve terminated. Time: 2.84
GP based matrix reordering started.
GP based matrix reordering terminated.
Optimizer - threads : 10
Optimizer - solved problem : the primal
Optimizer - Constraints : 1791389
Optimizer - Cones : 2640053
Optimizer - Scalar variables : 5315892 conic : 5315892
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 155.14 dense det. time : 3.39
Factor - ML order time : 7.00 GP order time : 122.08
Factor - nonzeros before factor : 2.21e+007 after factor : 1.00e+009
Factor - dense dim. : 4 flops : 1.06e+013
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 1.2e+005 1.0e+000 1.3e+000 0.00e+000 1.257308480e+003 0.000000000e+000 1.0e+000 160.14
1 1.1e+005 9.9e-001 1.3e+000 -9.77e-001 1.368737158e+004 1.246119188e+004 9.9e-001 227.80
2 1.1e+005 9.9e-001 1.3e+000 -7.41e-001 1.588403380e+004 1.467437442e+004 9.9e-001 293.36
3 1.1e+005 9.3e-001 1.2e+000 -7.38e-001 3.885052547e+004 3.782969883e+004 9.3e-001 359.64
4 1.0e+005 8.8e-001 1.1e+000 -7.03e-001 4.369597063e+004 4.282631814e+004 8.8e-001 425.94
5 5.9e+004 5.1e-001 5.8e-001 -6.79e-001 2.718979481e+005 2.728273355e+005 5.1e-001 496.75
6 2.8e+004 2.5e-001 2.6e-001 -4.19e-001 6.229025533e+005 6.256357120e+005 2.5e-001 562.13
7 5.3e+003 4.6e-002 6.0e-002 -5.67e-002 1.220934235e+006 1.223984141e+006 4.6e-002 627.58
8 4.6e+001 4.0e-004 5.4e-003 6.66e-001 1.454400205e+006 1.454425947e+006 4.0e-004 704.99
9 2.3e+001 2.0e-004 7.1e-003 1.24e+000 7.682304965e+005 7.682326517e+005 2.0e-004 776.42
10 1.9e+001 1.6e-004 6.3e-003 6.63e+000 2.622458637e+005 2.622494098e+005 1.6e-004 843.70
11 1.9e+001 1.6e-004 6.1e-003 3.41e+000 2.592729934e+005 2.592766594e+005 1.6e-004 908.94
12 7.1e+000 6.2e-005 3.7e-003 3.34e+000 7.319103114e+004 7.319273528e+004 6.2e-005 975.31
13 2.8e+000 2.4e-005 2.5e-003 1.20e+000 4.493627579e+004 4.493682408e+004 2.4e-005 1041.02
14 8.4e-001 7.2e-006 1.9e-003 1.13e+000 2.794888001e+004 2.794895653e+004 7.2e-006 1112.75
15 4.3e-001 3.7e-006 1.6e-003 1.14e+000 2.441577352e+004 2.441579997e+004 3.7e-006 1180.95
16 2.9e-001 2.5e-006 1.4e-003 1.21e+000 2.301213385e+004 2.301214712e+004 2.5e-006 1246.58
17 1.6e-001 1.4e-006 1.3e-003 1.25e+000 2.163256406e+004 2.163256826e+004 1.4e-006 1314.19
18 8.0e-002 6.9e-007 1.1e-003 1.34e+000 2.071993254e+004 2.071993358e+004 6.9e-007 1385.58
19 5.6e-002 4.8e-007 1.0e-003 1.46e+000 2.043403039e+004 2.043403086e+004 4.8e-007 1455.05
20 4.4e-002 3.8e-007 9.7e-004 1.42e+000 2.031111825e+004 2.031111854e+004 3.8e-007 1523.33
21 3.3e-002 2.9e-007 9.0e-004 1.37e+000 2.020892778e+004 2.020892793e+004 2.9e-007 1593.19
22 2.7e-002 2.3e-007 8.4e-004 1.31e+000 2.015455759e+004 2.015455768e+004 2.3e-007 1662.81
23 1.8e-002 1.6e-007 7.4e-004 1.27e+000 2.008223993e+004 2.008223996e+004 1.6e-007 1737.66
24 1.2e-002 1.0e-007 6.4e-004 1.20e+000 2.003401972e+004 2.003401972e+004 1.0e-007 1809.67
25 7.7e-003 6.7e-008 5.5e-004 1.16e+000 2.000436211e+004 2.000436211e+004 6.7e-008 1883.17
26 4.5e-003 4.0e-008 4.6e-004 1.13e+000 1.998191344e+004 1.998191343e+004 4.0e-008 1957.34
Interior-point optimizer terminated. Time: 1959.39.
Optimizer terminated. Time: 1959.50
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 1.9981913438e+004 nrm: 2e+007 Viol. con: 9e-002 var: 0e+000 cones: 0e+000
Dual. obj: 1.9981913427e+004 nrm: 1e+000 Viol. con: 0e+000 var: 8e-007 cones: 0e+000
Optimizer summary
Optimizer - time: 1959.50
Interior-point - iterations : 26 time: 1959.39
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): +19981.9
Elapsed time is 2111.300954 seconds.That’s a nice big problem! The time spent in the solver seems fair enough for that size.
One thing you can do is to update to the latest version 9.2 of Mosek instead of 8.0. Another thing you could do is to save your data to a file (cvx_solver_settings('write', 'dump.task.gz')) and deliver to Mosek support at support@mosek.com.
I wonder what your CVX model is that generates so many cones.
Can those near zero elements Mosek warns about slow down Mosek?
Since the model solve in 25 iterations it is likely to be a well posed problems so I would not worry about the warnings.
The reason it takes long time to solve is that 10^13 flops is required in every iteration to solve a linear equation system. See
https://erlingdandersen.blogspot.com/2013/11/complexity-of-solving-conic-quadratic.html
for explanation.
We will be happy to take a look at the problem as @Michal_Adamaszek writes.
1 Like
Thanks. Sent the dumpfile to mosek support.