Exercise 5.39: SDP relaxations of the two-way partitioning problem

% Boyd & Vandenberghe. "Convex Optimization"
% Joëlle Skaf - 09/07/05
% (a figure is generated)
%
% Compares the optimal values of:
% 1) the Lagrange dual of the two-way partitioning problem
%               maximize    -sum(nu)
%                   s.t.    W + diag(nu) >= 0
% 2) the SDP relaxation of the two-way partitioning problem
%               minimize    trace(WX)
%                   s.t.    X >= 0
%                           X_ii = 1

% Input data
randn('state',0);
n = 10;
W = randn(n); W = 0.5*(W + W');

% Lagrange dual
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;

% SDP relaxation
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;

% Displaying results
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 SDPT3: 55 variables, 10 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 10
 dim. of sdp    var  = 10,   num. of sdp  blk  =  1
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      mean(obj)   cputime
-------------------------------------------------------------------
 0|0.000|0.000|6.8e+00|3.3e+00|7.6e+02| 0.000000e+00| 0:0:00| chol  1  1 
 1|0.962|1.000|2.6e-01|4.2e-02|9.7e+01|-4.323987e+01| 0:0:00| chol  1  1 
 2|1.000|0.828|9.5e-08|1.1e-02|1.4e+01|-2.521487e+01| 0:0:00| chol  1  1 
 3|0.696|1.000|3.1e-08|4.2e-04|6.4e+00|-2.813839e+01| 0:0:00| chol  1  1 
 4|0.989|0.943|5.0e-09|6.3e-05|4.2e-01|-2.877724e+01| 0:0:00| chol  1  1 
 5|0.971|0.968|4.7e-10|6.1e-06|1.9e-02|-2.882181e+01| 0:0:00| chol  1  1 
 6|0.973|0.985|1.2e-10|5.0e-07|4.6e-04|-2.882555e+01| 0:0:00| chol  1  1 
 7|0.962|0.987|3.8e-10|6.5e-09|2.1e-05|-2.882567e+01| 0:0:00| chol  1  1 
 8|1.000|1.000|3.5e-11|3.7e-11|1.6e-06|-2.882567e+01| 0:0:00| chol  1  2 
 9|1.000|1.000|6.9e-12|7.1e-12|1.2e-07|-2.882567e+01| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   =  9
 primal objective value = -2.88256749e+01
 dual   objective value = -2.88256750e+01
 gap := trace(XZ)       = 1.25e-07
 relative gap           = 2.13e-09
 actual relative gap    = 2.12e-09
 rel. primal infeas     = 6.93e-12
 rel. dual   infeas     = 7.08e-12
 norm(X), norm(y), norm(Z) = 8.6e+00, 1.0e+01, 1.2e+01
 norm(A), norm(b), norm(C) = 4.2e+00, 4.2e+00, 7.6e+00
 Total CPU time (secs)  = 0.2  
 CPU time per iteration = 0.0  
 termination code       =  0
 DIMACS: 1.4e-11  0.0e+00  2.2e-11  0.0e+00  2.1e-09  2.1e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): -26.6924
Done! 
Solving the SDP relaxation of the two-way partitioning problem... 
Calling SDPT3: 55 variables, 10 equality constraints
------------------------------------------------------------

 num. of constraints = 10
 dim. of sdp    var  = 10,   num. of sdp  blk  =  1
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      mean(obj)   cputime
-------------------------------------------------------------------
 0|0.000|0.000|6.8e+00|3.3e+00|7.6e+02| 0.000000e+00| 0:0:00| chol  1  1 
 1|0.962|1.000|2.6e-01|4.2e-02|9.7e+01|-4.323987e+01| 0:0:00| chol  1  1 
 2|1.000|0.828|9.5e-08|1.1e-02|1.4e+01|-2.521487e+01| 0:0:00| chol  1  1 
 3|0.696|1.000|3.1e-08|4.2e-04|6.4e+00|-2.813839e+01| 0:0:00| chol  1  1 
 4|0.989|0.943|5.0e-09|6.3e-05|4.2e-01|-2.877724e+01| 0:0:00| chol  1  1 
 5|0.971|0.968|4.7e-10|6.1e-06|1.9e-02|-2.882181e+01| 0:0:00| chol  1  1 
 6|0.973|0.985|1.2e-10|5.0e-07|4.6e-04|-2.882555e+01| 0:0:00| chol  1  1 
 7|0.962|0.987|3.8e-10|6.5e-09|2.1e-05|-2.882567e+01| 0:0:00| chol  1  1 
 8|1.000|1.000|3.5e-11|3.7e-11|1.6e-06|-2.882567e+01| 0:0:00| chol  1  2 
 9|1.000|1.000|6.9e-12|7.1e-12|1.2e-07|-2.882567e+01| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   =  9
 primal objective value = -2.88256749e+01
 dual   objective value = -2.88256750e+01
 gap := trace(XZ)       = 1.25e-07
 relative gap           = 2.13e-09
 actual relative gap    = 2.12e-09
 rel. primal infeas     = 6.93e-12
 rel. dual   infeas     = 7.08e-12
 norm(X), norm(y), norm(Z) = 8.6e+00, 1.0e+01, 1.2e+01
 norm(A), norm(b), norm(C) = 4.2e+00, 4.2e+00, 7.6e+00
 Total CPU time (secs)  = 0.2  
 CPU time per iteration = 0.0  
 termination code       =  0
 DIMACS: 1.4e-11  0.0e+00  2.2e-11  0.0e+00  2.1e-09  2.1e-09
-------------------------------------------------------------------
------------------------------------------------------------
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!