randn('state',0);
n = 10;
W = randn(n); W = 0.5*(W + W');
fprintf(1,'Solving the dual of the two-way partitioning problem...');
cvx_begin sdp
variable nu(n)
maximize ( -sum(nu) )
W + diag(nu) >= 0;
cvx_end
fprintf(1,'Done! \n');
opt1 = cvx_optval;
fprintf(1,'Solving the SDP relaxation of the two-way partitioning problem...');
cvx_begin sdp
variable X(n,n) symmetric
minimize ( trace(W*X) )
diag(X) == 1;
X >= 0;
cvx_end
fprintf(1,'Done! \n');
opt2 = cvx_optval;
disp('------------------------------------------------------------------------');
disp('The optimal value of the Lagrange dual and the SDP relaxation fo the ');
disp('two-way partitioning problem are, respectively, ');
disp([opt1 opt2])
disp('They are equal as expected!');
Solving the dual of the two-way partitioning problem...
Calling Mosek 9.1.9: 55 variables, 10 equality constraints
For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------
MOSEK Version 9.1.9 (Build date: 2019-11-21 11:32:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 10
Cones : 0
Scalar variables : 0
Matrix variables : 1
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.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.00
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 10
Cones : 0
Scalar variables : 0
Matrix variables : 1
Integer variables : 0
Optimizer - threads : 8
Optimizer - solved problem : the primal
Optimizer - Constraints : 10
Optimizer - Cones : 0
Optimizer - Scalar variables : 0 conic : 0
Optimizer - Semi-definite variables: 1 scalarized : 55
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 : 55 after factor : 55
Factor - dense dim. : 0 flops : 3.68e+03
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 0.0e+00 1.4e+00 1.0e+00 0.00e+00 0.000000000e+00 0.000000000e+00 1.0e+00 0.00
1 0.0e+00 4.9e-01 3.8e-01 -5.95e-01 -9.080354971e+00 -8.460085053e+00 3.4e-01 0.01
2 3.1e-15 8.6e-02 5.4e-02 -5.95e-02 -2.390587759e+01 -2.327641307e+01 6.0e-02 0.01
3 5.0e-16 1.3e-02 3.5e-03 7.59e-01 -2.788646911e+01 -2.777288266e+01 9.2e-03 0.01
4 4.4e-15 1.7e-03 1.6e-04 9.53e-01 -2.870559007e+01 -2.869129036e+01 1.2e-03 0.01
5 1.7e-15 1.8e-04 5.5e-06 9.94e-01 -2.881292844e+01 -2.881141677e+01 1.2e-04 0.01
6 3.2e-15 1.0e-05 7.6e-08 9.99e-01 -2.882493585e+01 -2.882484866e+01 7.1e-06 0.01
7 3.5e-15 7.4e-07 1.5e-09 1.00e+00 -2.882562024e+01 -2.882561394e+01 5.2e-07 0.01
8 5.9e-15 7.9e-08 5.2e-11 1.00e+00 -2.882566899e+01 -2.882566831e+01 5.5e-08 0.01
9 2.2e-14 4.0e-09 5.9e-13 1.00e+00 -2.882567469e+01 -2.882567466e+01 2.8e-09 0.01
Optimizer terminated. Time: 0.02
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -2.8825674690e+01 nrm: 1e+00 Viol. con: 8e-14 barvar: 0e+00
Dual. obj: -2.8825674656e+01 nrm: 5e+00 Viol. con: 0e+00 barvar: 1e-08
Optimizer summary
Optimizer - time: 0.02
Interior-point - iterations : 9 time: 0.01
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): -26.6924
Done!
Solving the SDP relaxation of the two-way partitioning problem...
Calling Mosek 9.1.9: 55 variables, 10 equality constraints
------------------------------------------------------------
MOSEK Version 9.1.9 (Build date: 2019-11-21 11:32:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 10
Cones : 0
Scalar variables : 0
Matrix variables : 1
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.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.00
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 10
Cones : 0
Scalar variables : 0
Matrix variables : 1
Integer variables : 0
Optimizer - threads : 8
Optimizer - solved problem : the primal
Optimizer - Constraints : 10
Optimizer - Cones : 0
Optimizer - Scalar variables : 0 conic : 0
Optimizer - Semi-definite variables: 1 scalarized : 55
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 : 55 after factor : 55
Factor - dense dim. : 0 flops : 3.68e+03
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 0.0e+00 1.4e+00 1.0e+00 0.00e+00 0.000000000e+00 0.000000000e+00 1.0e+00 0.00
1 0.0e+00 4.9e-01 3.8e-01 -5.95e-01 -9.080354971e+00 -8.460085053e+00 3.4e-01 0.01
2 3.1e-15 8.6e-02 5.4e-02 -5.95e-02 -2.390587759e+01 -2.327641307e+01 6.0e-02 0.01
3 5.0e-16 1.3e-02 3.5e-03 7.59e-01 -2.788646911e+01 -2.777288266e+01 9.2e-03 0.01
4 4.4e-15 1.7e-03 1.6e-04 9.53e-01 -2.870559007e+01 -2.869129036e+01 1.2e-03 0.01
5 1.7e-15 1.8e-04 5.5e-06 9.94e-01 -2.881292844e+01 -2.881141677e+01 1.2e-04 0.01
6 3.2e-15 1.0e-05 7.6e-08 9.99e-01 -2.882493585e+01 -2.882484866e+01 7.1e-06 0.01
7 3.5e-15 7.4e-07 1.5e-09 1.00e+00 -2.882562024e+01 -2.882561394e+01 5.2e-07 0.01
8 5.9e-15 7.9e-08 5.2e-11 1.00e+00 -2.882566899e+01 -2.882566831e+01 5.5e-08 0.01
9 2.2e-14 4.0e-09 5.9e-13 1.00e+00 -2.882567469e+01 -2.882567466e+01 2.8e-09 0.01
Optimizer terminated. Time: 0.02
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -2.8825674690e+01 nrm: 1e+00 Viol. con: 8e-14 barvar: 0e+00
Dual. obj: -2.8825674656e+01 nrm: 5e+00 Viol. con: 0e+00 barvar: 1e-08
Optimizer summary
Optimizer - time: 0.02
Interior-point - iterations : 9 time: 0.01
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): -26.6924
Done!
------------------------------------------------------------------------
The optimal value of the Lagrange dual and the SDP relaxation fo the
two-way partitioning problem are, respectively,
-26.6924 -26.6924
They are equal as expected!