I’m using MOSEK 7.1 directly through its c++ API.
I’m solving a portfolio optimization problem in a conic form with linear constraints.
I’m seeing a cutoff point in my problem, where when it goes above a critical size, the solution time goes up 3 fold, and some statistics change (I noticed “Factor - dense dim.” goes to 1 after slowdown).
Please help me understand why this is happening, and whether I can tweak with MOSEK parameters to keep it efficient as the problem grows.
Following are the outputs of MOSEK for the problem when it’s slightly smaller and fast, and when it’s slightly bigger and much slower:
fast:
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 4860
Cones : 1
Scalar variables : 4859
Matrix variables : 0
Integer variables : 0
Optimizer started.
Conic interior-point optimizer started.
MOSEK warning 950: No automatic dualizer is available for the specified problem.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Total number of eliminations : 1680
Eliminator terminated.
Eliminator started.
Total number of eliminations : 1680
Eliminator terminated.
Eliminator - tries : 2 time : 0.00
Eliminator - elim’s : 1680
Lin. dep. - tries : 1 time : 0.01
Lin. dep. - number : 0
Presolve terminated. Time: 0.83
Optimizer - threads : 16
Optimizer - solved problem : the primal
Optimizer - Constraints : 3178
Optimizer - Cones : 1
Optimizer - Scalar variables : 6418 conic : 1621
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.83 dense det. time : 0.24
Factor - ML order time : 0.01 GP order time : 0.00
Factor - nonzeros before factor : 1.38e+06 after factor : 2.20e+06
Factor - dense dim. : 1282 flops : 2.16e+09
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.1e+02 1.0e+00 1.7e+00 0.00e+00 7.074786277e-01 0.000000000e+00 1.0e+00 1.86
1 1.6e+02 7.5e-01 1.3e+00 2.07e+00 2.516418434e-01 -3.809220057e-01 7.5e-01 2.03
2 1.1e+02 5.5e-01 9.3e-01 4.47e+00 4.361376873e-03 -1.385106900e-01 5.5e-01 2.19
3 1.1e+02 5.3e-01 9.1e-01 4.24e+01 2.569599960e-03 -1.302797623e-02 5.3e-01 2.35
4 4.4e+01 2.1e-01 3.6e-01 6.52e+00 9.633175002e-04 1.827048602e-04 2.1e-01 2.52
5 1.7e+01 8.1e-02 1.4e-01 1.07e+00 2.710907206e-04 -2.565649152e-05 8.1e-02 2.69
6 4.6e+00 2.2e-02 3.8e-02 1.29e+00 3.210192008e-05 -4.345222212e-05 2.2e-02 2.85
7 2.6e+00 1.3e-02 2.1e-02 1.54e+00 7.250876264e-06 -2.940169709e-05 1.3e-02 3.02
8 8.3e-01 4.0e-03 6.8e-03 1.34e+00 -4.616866217e-06 -1.483847058e-05 4.0e-03 3.18
9 4.5e-01 2.2e-03 3.7e-03 1.11e+00 -7.288954003e-06 -1.278646323e-05 2.2e-03 3.34
10 1.9e-01 9.0e-04 1.5e-03 1.06e+00 -9.893579588e-06 -1.215761189e-05 9.0e-04 3.52
11 9.1e-02 4.4e-04 7.5e-04 1.03e+00 -1.095326795e-05 -1.204995360e-05 4.4e-04 3.69
12 3.3e-02 1.6e-04 2.7e-04 1.01e+00 -1.167550317e-05 -1.207334468e-05 1.6e-04 3.86
13 1.0e-02 5.0e-05 8.6e-05 1.01e+00 -1.200046768e-05 -1.212673653e-05 5.0e-05 4.02
14 1.9e-03 9.2e-06 1.6e-05 1.00e+00 -1.214171233e-05 -1.216498953e-05 9.2e-06 4.19
15 3.2e-04 1.5e-06 2.6e-06 1.00e+00 -1.217159930e-05 -1.217551151e-05 1.5e-06 4.35
16 5.6e-05 2.7e-07 4.6e-07 1.00e+00 -1.217692969e-05 -1.217761609e-05 2.7e-07 4.51
17 1.1e-05 5.3e-08 9.1e-08 1.00e+00 -1.217787455e-05 -1.217800930e-05 5.3e-08 4.67
Interior-point optimizer terminated. Time: 4.67.
Optimizer terminated. Time: 4.78
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -1.2177874547e-05 Viol. con: 1e-07 var: 0e+00 cones: 0e+00
Dual. obj: -1.2178021702e-05 Viol. con: 8e-11 var: 2e-11 cones: 6e-11
slow:
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 4899
Cones : 1
Scalar variables : 4898
Matrix variables : 0
Integer variables : 0
Optimizer started.
Conic interior-point optimizer started.
MOSEK warning 950: No automatic dualizer is available for the specified problem.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Total number of eliminations : 1693
Eliminator terminated.
Eliminator started.
Total number of eliminations : 1693
Eliminator terminated.
Eliminator - tries : 2 time : 0.00
Eliminator - elim’s : 1693
Lin. dep. - tries : 1 time : 0.01
Lin. dep. - number : 0
Presolve terminated. Time: 1.00
Optimizer - threads : 16
Optimizer - solved problem : the primal
Optimizer - Constraints : 3204
Optimizer - Cones : 1
Optimizer - Scalar variables : 6470 conic : 1634
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 1.27 dense det. time : 0.26
Factor - ML order time : 0.20 GP order time : 0.00
Factor - nonzeros before factor : 2.67e+06 after factor : 2.67e+06
Factor - dense dim. : 1 flops : 4.39e+09
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.1e+02 1.0e+00 1.7e+00 0.00e+00 7.074836223e-01 0.000000000e+00 1.0e+00 2.52
1 1.6e+02 7.5e-01 1.3e+00 2.07e+00 2.515309331e-01 -3.806852284e-01 7.5e-01 3.09
2 1.1e+02 5.5e-01 9.3e-01 4.47e+00 4.362751587e-03 -1.383168401e-01 5.5e-01 3.74
3 1.1e+02 5.3e-01 9.1e-01 4.25e+01 2.554048752e-03 -1.300578760e-02 5.3e-01 4.35
4 4.4e+01 2.1e-01 3.6e-01 6.56e+00 9.618521112e-04 1.818413155e-04 2.1e-01 4.98
5 1.7e+01 8.1e-02 1.4e-01 1.07e+00 2.701127771e-04 -2.662372669e-05 8.1e-02 5.61
6 4.7e+00 2.3e-02 3.8e-02 1.29e+00 3.337679137e-05 -4.309069518e-05 2.3e-02 6.28
7 2.7e+00 1.3e-02 2.2e-02 1.54e+00 7.442825160e-06 -2.927554645e-05 1.3e-02 6.94
8 8.6e-01 4.1e-03 7.0e-03 1.34e+00 -4.467829299e-06 -1.488637179e-05 4.1e-03 7.58
9 4.7e-01 2.3e-03 3.9e-03 1.12e+00 -7.179227559e-06 -1.281892723e-05 2.3e-03 8.27
10 1.9e-01 9.1e-04 1.6e-03 1.06e+00 -9.845670097e-06 -1.211214891e-05 9.1e-04 8.95
11 9.3e-02 4.5e-04 7.6e-04 1.03e+00 -1.091310345e-05 -1.201989125e-05 4.5e-04 9.69
12 3.3e-02 1.6e-04 2.7e-04 1.01e+00 -1.165405059e-05 -1.205083040e-05 1.6e-04 10.34
13 1.0e-02 5.0e-05 8.5e-05 1.01e+00 -1.198083323e-05 -1.210559663e-05 5.0e-05 11.02
14 3.0e-03 1.5e-05 2.5e-05 1.00e+00 -1.210274910e-05 -1.213915201e-05 1.5e-05 11.64
15 4.2e-04 2.0e-06 3.4e-06 1.00e+00 -1.214905474e-05 -1.215410890e-05 2.0e-06 12.25
16 5.7e-05 2.7e-07 4.7e-07 1.00e+00 -1.215619068e-05 -1.215688066e-05 2.7e-07 12.87
17 8.4e-06 4.0e-08 6.9e-08 1.00e+00 -1.215718093e-05 -1.215728216e-05 4.0e-08 13.56
Interior-point optimizer terminated. Time: 13.56.
Optimizer terminated. Time: 13.72
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -1.2157180928e-05 Viol. con: 1e-07 var: 0e+00 cones: 0e+00
Dual. obj: -1.2157291494e-05 Viol. con: 6e-11 var: 2e-11 cones: 4e-11