Measure the number of flops in MOSEK
85 views
Skip to first unread message
Giang Nguyen Kien
Oct 6, 2015, 10:22:25 AM10/6/15
to mosek
Hi,
I have a question with the information MSK_DINF_INTPNT_FACTOR_NUM_FLOPS in MOSEK.
I want to compare the complexity of two conic programmings with MSK_DINF_INTPNT_FACTOR_NUM_FLOPS in MOSEK. They share the same objective and most of the constraints (linear or conic), except the one which can be represented by two different system of conic constraints. The following is output information:
1st conic programming
Computer
Platform : Windows/64-X86
Cores : 4
Problem
Name :
Objective sense : max
Type : CONIC (conic optimization problem)
Constraints : 393
Cones : 33
Scalar variables : 562
Matrix variables : 0
Integer variables : 0
Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Total number of eliminations : 3
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Eliminator - elim's : 3
Lin. dep. - tries : 1 time : 0.02
Lin. dep. - number : 0
Presolve terminated. Time: 0.02
Optimizer - threads : 4
Optimizer - solved problem : the primal
Optimizer - Constraints : 378
Optimizer - Cones : 33
Optimizer - Scalar variables : 562 conic : 546
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 : 2.36e+004 after factor : 2.79e+004
Factor - dense dim. : 0 flops : 2.65e+006
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.0e+000 2.0e+000 0.0e+000 0.00e+000 4.000000000e+000 0.000000000e+000 1.0e+000 0.03
1 5.7e-001 5.7e-001 1.8e-015 1.88e-001 1.346360499e+000 1.727025160e-001 2.9e-001 0.06
2 1.7e-001 1.7e-001 8.3e-017 1.72e+000 3.129931867e-001 2.375070835e-001 8.6e-002 0.06
3 4.8e-002 4.8e-002 3.8e-016 1.89e+000 6.193623859e-002 4.526863463e-002 2.4e-002 0.06
4 1.2e-002 1.2e-002 5.2e-017 1.48e+000 1.640697159e-002 1.355093683e-002 6.1e-003 0.08
5 3.7e-003 3.7e-003 8.2e-018 1.38e+000 4.345808444e-003 3.659745860e-003 1.8e-003 0.08
6 7.4e-004 7.3e-004 3.5e-018 1.26e+000 2.779874284e-003 2.677826341e-003 3.7e-004 0.08
7 1.6e-004 1.6e-004 1.7e-018 1.13e+000 2.734903240e-003 2.713560521e-003 8.2e-005 0.08
8 6.0e-005 5.9e-005 4.3e-019 1.00e+000 2.730367081e-003 2.722276694e-003 3.0e-005 0.09
9 2.7e-005 2.7e-005 0.0e+000 9.60e-001 2.736863221e-003 2.732981342e-003 1.3e-005 0.09
10 1.7e-005 1.7e-005 3.0e-018 8.45e-001 2.752868762e-003 2.750041385e-003 8.6e-006 0.09
11 6.3e-006 6.2e-006 2.6e-018 9.13e-001 2.753621990e-003 2.752511686e-003 3.1e-006 0.09
12 2.8e-006 2.8e-006 1.2e-016 7.70e-001 2.762798260e-003 2.762145776e-003 1.4e-006 0.11
13 1.7e-006 1.7e-006 8.5e-017 8.18e-001 2.764649321e-003 2.764220190e-003 8.3e-007 0.11
14 5.4e-007 5.4e-007 2.2e-017 9.86e-001 2.765047294e-003 2.764921867e-003 2.7e-007 0.11
15 9.5e-008 9.5e-008 1.1e-016 9.75e-001 2.765886733e-003 2.765865101e-003 4.8e-008 0.11
16 3.7e-008 3.7e-008 4.5e-016 1.02e+000 2.766026149e-003 2.766017778e-003 1.9e-008 0.11
Interior-point optimizer terminated. Time: 0.11.
Optimizer terminated. Time: 0.16
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 2.7660261485e-003 Viol. con: 2e-007 var: 0e+000 cones: 0e+000
Dual. obj: 2.7660177775e-003 Viol. con: 7e-009 var: 1e-008 cones: 5e-009
Optimizer summary
Optimizer - time: 0.16
Interior-point - iterations : 16 time: 0.11
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
2nd conic programming
Computer
Platform : Windows/64-X86
Cores : 4
Problem
Name :
Objective sense : max
Type : CONIC (conic optimization problem)
Constraints : 597
Cones : 177
Scalar variables : 1054
Matrix variables : 0
Integer variables : 0
Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Total number of eliminations : 8
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Eliminator - elim's : 8
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.00
Optimizer - threads : 4
Optimizer - solved problem : the primal
Optimizer - Constraints : 530
Optimizer - Cones : 177
Optimizer - Scalar variables : 1029 conic : 978
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 : 2.33e+004 after factor : 2.63e+004
Factor - dense dim. : 0 flops : 2.36e+006
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.0e+000 2.0e+000 0.0e+000 0.00e+000 4.000000000e+000 0.000000000e+000 1.0e+000 0.01
1 1.3e+000 1.2e+000 2.7e-015 1.29e+000 1.835236356e+000 1.713239398e+000 6.2e-001 0.05
2 5.7e-001 5.6e-001 4.1e-015 1.91e+000 6.119771736e-001 5.608051028e-001 2.8e-001 0.05
3 3.4e-001 3.3e-001 4.1e-015 1.28e+000 3.609982767e-001 3.240281483e-001 1.7e-001 0.05
4 1.7e-001 1.7e-001 2.5e-015 1.15e+000 2.477198705e-001 2.248758911e-001 8.3e-002 0.05
5 6.0e-002 5.8e-002 1.4e-015 1.01e+000 3.012574856e-001 2.894899846e-001 2.9e-002 0.05
6 3.9e-002 3.8e-002 1.9e-015 7.21e-001 5.557501679e-001 5.449109738e-001 1.9e-002 0.05
7 1.9e-002 1.8e-002 1.6e-015 7.45e-001 6.267357868e-001 6.196929162e-001 9.2e-003 0.06
8 7.9e-003 7.8e-003 3.6e-015 1.75e-001 1.262287084e+000 1.252397386e+000 3.9e-003 0.06
9 4.6e-003 4.5e-003 1.4e-015 2.87e-001 1.104871273e+000 1.095972957e+000 2.2e-003 0.06
10 1.3e-003 1.2e-003 2.6e-015 5.04e-001 4.270184823e-001 4.242214721e-001 6.2e-004 0.06
11 3.1e-004 3.0e-004 3.5e-015 4.09e-001 2.956085324e-001 2.938688981e-001 1.5e-004 0.06
12 1.1e-004 1.1e-004 2.4e-015 3.54e-001 2.350433133e-001 2.338246082e-001 5.6e-005 0.06
13 4.0e-005 3.9e-005 1.5e-015 8.35e-001 1.910870260e-001 1.906073228e-001 2.0e-005 0.08
14 1.1e-005 1.1e-005 1.1e-015 8.80e-001 1.758491304e-001 1.756824650e-001 5.4e-006 0.08
15 5.7e-006 5.6e-006 6.1e-015 9.58e-001 1.673390218e-001 1.672505848e-001 2.8e-006 0.08
16 4.1e-006 4.0e-006 1.1e-015 9.85e-001 1.647030413e-001 1.646385519e-001 2.0e-006 0.08
17 2.5e-006 2.4e-006 2.2e-015 9.90e-001 1.616722393e-001 1.616322862e-001 1.2e-006 0.08
18 1.5e-006 1.5e-006 6.0e-016 1.01e+000 1.602588445e-001 1.602339714e-001 7.5e-007 0.09
19 9.4e-007 9.2e-007 3.3e-015 1.01e+000 1.592341634e-001 1.592185954e-001 4.6e-007 0.09
20 3.6e-007 3.6e-007 1.7e-015 1.02e+000 1.583781767e-001 1.583721366e-001 1.8e-007 0.09
21 1.6e-007 1.6e-007 6.9e-015 1.02e+000 1.580773687e-001 1.580746393e-001 8.0e-008 0.09
22 6.4e-008 6.3e-008 6.1e-015 1.02e+000 1.579595961e-001 1.579585226e-001 3.1e-008 0.09
23 2.1e-008 2.1e-008 4.5e-015 1.01e+000 1.579113453e-001 1.579109897e-001 1.0e-008 0.09
24 2.5e-009 2.4e-009 1.2e-014 1.01e+000 1.578913106e-001 1.578912682e-001 1.2e-009 0.09
Interior-point optimizer terminated. Time: 0.09.
Optimizer terminated. Time: 0.14
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 1.5789131064e-001 Viol. con: 5e-005 var: 0e+000 cones: 5e-009
Dual. obj: 1.5789125655e-001 Viol. con: 4e-009 var: 7e-009 cones: 5e-010
Optimizer summary
Optimizer - time: 0.14
Interior-point - iterations : 24 time: 0.09
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
Could you please tell me why the 2nd conic programming (which has more constraints and variables than 1st conic programming) used smaller number of flops? and where might the extra flops of 1st conic programming come from?
Are the flops measured for the whole program (including the calculation to assign the values for matrices A of prob.a=sparse(A) ) or when executing the command mosekopt()?
Thank you.
I have a question with the information MSK_DINF_INTPNT_FACTOR_NUM_FLOPS in MOSEK.
I want to compare the complexity of two conic programmings with MSK_DINF_INTPNT_FACTOR_NUM_FLOPS in MOSEK. They share the same objective and most of the constraints (linear or conic), except the one which can be represented by two different system of conic constraints. The following is output information:
1st conic programming
Computer
Platform : Windows/64-X86
Cores : 4
Problem
Name :
Objective sense : max
Type : CONIC (conic optimization problem)
Constraints : 393
Cones : 33
Scalar variables : 562
Matrix variables : 0
Integer variables : 0
Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Total number of eliminations : 3
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Eliminator - elim's : 3
Lin. dep. - tries : 1 time : 0.02
Lin. dep. - number : 0
Presolve terminated. Time: 0.02
Optimizer - threads : 4
Optimizer - solved problem : the primal
Optimizer - Constraints : 378
Optimizer - Cones : 33
Optimizer - Scalar variables : 562 conic : 546
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 : 2.36e+004 after factor : 2.79e+004
Factor - dense dim. : 0 flops : 2.65e+006
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.0e+000 2.0e+000 0.0e+000 0.00e+000 4.000000000e+000 0.000000000e+000 1.0e+000 0.03
1 5.7e-001 5.7e-001 1.8e-015 1.88e-001 1.346360499e+000 1.727025160e-001 2.9e-001 0.06
2 1.7e-001 1.7e-001 8.3e-017 1.72e+000 3.129931867e-001 2.375070835e-001 8.6e-002 0.06
3 4.8e-002 4.8e-002 3.8e-016 1.89e+000 6.193623859e-002 4.526863463e-002 2.4e-002 0.06
4 1.2e-002 1.2e-002 5.2e-017 1.48e+000 1.640697159e-002 1.355093683e-002 6.1e-003 0.08
5 3.7e-003 3.7e-003 8.2e-018 1.38e+000 4.345808444e-003 3.659745860e-003 1.8e-003 0.08
6 7.4e-004 7.3e-004 3.5e-018 1.26e+000 2.779874284e-003 2.677826341e-003 3.7e-004 0.08
7 1.6e-004 1.6e-004 1.7e-018 1.13e+000 2.734903240e-003 2.713560521e-003 8.2e-005 0.08
8 6.0e-005 5.9e-005 4.3e-019 1.00e+000 2.730367081e-003 2.722276694e-003 3.0e-005 0.09
9 2.7e-005 2.7e-005 0.0e+000 9.60e-001 2.736863221e-003 2.732981342e-003 1.3e-005 0.09
10 1.7e-005 1.7e-005 3.0e-018 8.45e-001 2.752868762e-003 2.750041385e-003 8.6e-006 0.09
11 6.3e-006 6.2e-006 2.6e-018 9.13e-001 2.753621990e-003 2.752511686e-003 3.1e-006 0.09
12 2.8e-006 2.8e-006 1.2e-016 7.70e-001 2.762798260e-003 2.762145776e-003 1.4e-006 0.11
13 1.7e-006 1.7e-006 8.5e-017 8.18e-001 2.764649321e-003 2.764220190e-003 8.3e-007 0.11
14 5.4e-007 5.4e-007 2.2e-017 9.86e-001 2.765047294e-003 2.764921867e-003 2.7e-007 0.11
15 9.5e-008 9.5e-008 1.1e-016 9.75e-001 2.765886733e-003 2.765865101e-003 4.8e-008 0.11
16 3.7e-008 3.7e-008 4.5e-016 1.02e+000 2.766026149e-003 2.766017778e-003 1.9e-008 0.11
Interior-point optimizer terminated. Time: 0.11.
Optimizer terminated. Time: 0.16
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 2.7660261485e-003 Viol. con: 2e-007 var: 0e+000 cones: 0e+000
Dual. obj: 2.7660177775e-003 Viol. con: 7e-009 var: 1e-008 cones: 5e-009
Optimizer summary
Optimizer - time: 0.16
Interior-point - iterations : 16 time: 0.11
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
2nd conic programming
Computer
Platform : Windows/64-X86
Cores : 4
Problem
Name :
Objective sense : max
Type : CONIC (conic optimization problem)
Constraints : 597
Cones : 177
Scalar variables : 1054
Matrix variables : 0
Integer variables : 0
Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Total number of eliminations : 8
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Eliminator - elim's : 8
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.00
Optimizer - threads : 4
Optimizer - solved problem : the primal
Optimizer - Constraints : 530
Optimizer - Cones : 177
Optimizer - Scalar variables : 1029 conic : 978
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 : 2.33e+004 after factor : 2.63e+004
Factor - dense dim. : 0 flops : 2.36e+006
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.0e+000 2.0e+000 0.0e+000 0.00e+000 4.000000000e+000 0.000000000e+000 1.0e+000 0.01
1 1.3e+000 1.2e+000 2.7e-015 1.29e+000 1.835236356e+000 1.713239398e+000 6.2e-001 0.05
2 5.7e-001 5.6e-001 4.1e-015 1.91e+000 6.119771736e-001 5.608051028e-001 2.8e-001 0.05
3 3.4e-001 3.3e-001 4.1e-015 1.28e+000 3.609982767e-001 3.240281483e-001 1.7e-001 0.05
4 1.7e-001 1.7e-001 2.5e-015 1.15e+000 2.477198705e-001 2.248758911e-001 8.3e-002 0.05
5 6.0e-002 5.8e-002 1.4e-015 1.01e+000 3.012574856e-001 2.894899846e-001 2.9e-002 0.05
6 3.9e-002 3.8e-002 1.9e-015 7.21e-001 5.557501679e-001 5.449109738e-001 1.9e-002 0.05
7 1.9e-002 1.8e-002 1.6e-015 7.45e-001 6.267357868e-001 6.196929162e-001 9.2e-003 0.06
8 7.9e-003 7.8e-003 3.6e-015 1.75e-001 1.262287084e+000 1.252397386e+000 3.9e-003 0.06
9 4.6e-003 4.5e-003 1.4e-015 2.87e-001 1.104871273e+000 1.095972957e+000 2.2e-003 0.06
10 1.3e-003 1.2e-003 2.6e-015 5.04e-001 4.270184823e-001 4.242214721e-001 6.2e-004 0.06
11 3.1e-004 3.0e-004 3.5e-015 4.09e-001 2.956085324e-001 2.938688981e-001 1.5e-004 0.06
12 1.1e-004 1.1e-004 2.4e-015 3.54e-001 2.350433133e-001 2.338246082e-001 5.6e-005 0.06
13 4.0e-005 3.9e-005 1.5e-015 8.35e-001 1.910870260e-001 1.906073228e-001 2.0e-005 0.08
14 1.1e-005 1.1e-005 1.1e-015 8.80e-001 1.758491304e-001 1.756824650e-001 5.4e-006 0.08
15 5.7e-006 5.6e-006 6.1e-015 9.58e-001 1.673390218e-001 1.672505848e-001 2.8e-006 0.08
16 4.1e-006 4.0e-006 1.1e-015 9.85e-001 1.647030413e-001 1.646385519e-001 2.0e-006 0.08
17 2.5e-006 2.4e-006 2.2e-015 9.90e-001 1.616722393e-001 1.616322862e-001 1.2e-006 0.08
18 1.5e-006 1.5e-006 6.0e-016 1.01e+000 1.602588445e-001 1.602339714e-001 7.5e-007 0.09
19 9.4e-007 9.2e-007 3.3e-015 1.01e+000 1.592341634e-001 1.592185954e-001 4.6e-007 0.09
20 3.6e-007 3.6e-007 1.7e-015 1.02e+000 1.583781767e-001 1.583721366e-001 1.8e-007 0.09
21 1.6e-007 1.6e-007 6.9e-015 1.02e+000 1.580773687e-001 1.580746393e-001 8.0e-008 0.09
22 6.4e-008 6.3e-008 6.1e-015 1.02e+000 1.579595961e-001 1.579585226e-001 3.1e-008 0.09
23 2.1e-008 2.1e-008 4.5e-015 1.01e+000 1.579113453e-001 1.579109897e-001 1.0e-008 0.09
24 2.5e-009 2.4e-009 1.2e-014 1.01e+000 1.578913106e-001 1.578912682e-001 1.2e-009 0.09
Interior-point optimizer terminated. Time: 0.09.
Optimizer terminated. Time: 0.14
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 1.5789131064e-001 Viol. con: 5e-005 var: 0e+000 cones: 5e-009
Dual. obj: 1.5789125655e-001 Viol. con: 4e-009 var: 7e-009 cones: 5e-010
Optimizer summary
Optimizer - time: 0.14
Interior-point - iterations : 24 time: 0.09
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
Could you please tell me why the 2nd conic programming (which has more constraints and variables than 1st conic programming) used smaller number of flops? and where might the extra flops of 1st conic programming come from?
Are the flops measured for the whole program (including the calculation to assign the values for matrices A of prob.a=sparse(A) ) or when executing the command mosekopt()?
Thank you.
erl...@andersens.name
Oct 9, 2015, 4:34:15 AM10/9/15
to mosek
First of all the difference in flops you are seeing is negible. The solution time depends on number flops but also many other factors such as how well the cache is caches are exploited.
The flops reported is approximately the number of flops required to compute a factorization of (*) mentioned in the blog post
Hence it is approximately the cost of one iteration. Also the above blog post tells you why the flops is not a simple function of the number of constraints and variables.
Giang Nguyen Kien
Oct 9, 2015, 4:52:57 AM10/9/15
to mo...@googlegroups.com
Hi,
Thank you. It's very helpful.--
You received this message because you are subscribed to a topic in the Google Groups "mosek" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/mosek/4VhE6LD_6Nk/unsubscribe.
To unsubscribe from this group and all its topics, send an email to mosek+un...@googlegroups.com.
To post to this group, send email to mo...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--
Nguyen Kien Giang
Reply all
Reply to author
Forward
0 new messages