Example 8.3: Bounding correlation coefficients

% Boyd & Vandenberghe "Convex Optimization"
% Joelle Skaf - 10/09/05
%
% Let C be a correlation matrix. Given lower and upper bounds on
% some of the angles (or correlation coeff.), find the maximum and minimum
% possible values of rho_14 by solving 2 SDP's
%           minimize/maximize   rho_14
%                        s.t.   C >=0
%                               0.6 <= rho_12 <=  0.9
%                               0.8 <= rho_13 <=  0.9
%                               0.5 <= rho_24 <=  0.7
%                              -0.8 <= rho_34 <= -0.4

n = 4;

% Upper bound SDP
fprintf(1,'Solving the upper bound SDP ...');

cvx_begin sdp
    variable C1(n,n) symmetric
    maximize ( C1(1,4) )
    C1 >= 0;
    diag(C1) == ones(n,1);
    C1(1,2) >= 0.6;
    C1(1,2) <= 0.9;
    C1(1,3) >= 0.8;
    C1(1,3) <= 0.9;
    C1(2,4) >= 0.5;
    C1(2,4) <= 0.7;
    C1(3,4) >= -0.8;
    C1(3,4) <= -0.4;
cvx_end

fprintf(1,'Done! \n');

% Lower bound SDP
fprintf(1,'Solving the lower bound SDP ...');

cvx_begin sdp
    variable C2(n,n) symmetric
    minimize ( C2(1,4) )
    C2 >= 0;
    diag(C2) == ones(n,1);
    C2(1,2) >= 0.6;
    C2(1,2) <= 0.9;
    C2(1,3) >= 0.8;
    C2(1,3) <= 0.9;
    C2(2,4) >= 0.5;
    C2(2,4) <= 0.7;
    C2(3,4) >= -0.8;
    C2(3,4) <= -0.4;
cvx_end

fprintf(1,'Done! \n');
% Displaying results
disp('--------------------------------------------------------------------------------');
disp(['The minimum and maximum values of rho_14 are: ' num2str(C2(1,4)) ' and ' num2str(C1(1,4))]);
disp('with corresponding correlation matrices: ');
disp(C2)
disp(C1)
Solving the upper bound SDP ... 
Calling SDPT3: 18 variables, 6 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints =  6
 dim. of sdp    var  =  4,   num. of sdp  blk  =  1
 dim. of linear var  =  8
*******************************************************************
   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|5.0e-01|2.4e+00|1.8e+02| 9.455844e+00| 0:0:00| chol  1  1 
 1|1.000|0.965|1.2e-06|1.7e-01|1.6e+01| 3.569251e+00| 0:0:00| chol  1  1 
 2|0.984|1.000|1.7e-06|9.0e-03|2.0e+00| 1.040621e+00| 0:0:00| chol  1  1 
 3|0.928|1.000|1.9e-07|9.0e-04|1.5e-01| 2.644014e-01| 0:0:00| chol  1  1 
 4|0.951|0.987|1.2e-07|1.0e-04|8.2e-03| 2.328182e-01| 0:0:00| chol  1  1 
 5|0.956|0.992|1.1e-08|9.7e-06|4.4e-04| 2.300940e-01| 0:0:00| chol  1  1 
 6|0.958|0.991|3.7e-09|9.8e-07|2.0e-05| 2.299200e-01| 0:0:00| chol  1  1 
 7|0.997|1.000|1.8e-09|7.5e-10|1.0e-06| 2.299093e-01| 0:0:00| chol  1  1 
 8|1.000|1.000|1.6e-09|3.6e-10|8.3e-08| 2.299091e-01| 0:0:00| chol  1  1 
 9|1.000|1.000|2.7e-10|7.0e-11|4.0e-09| 2.299091e-01| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   =  9
 primal objective value =  2.29909086e-01
 dual   objective value =  2.29909082e-01
 gap := trace(XZ)       = 3.95e-09
 relative gap           = 2.71e-09
 actual relative gap    = 2.12e-09
 rel. primal infeas     = 2.73e-10
 rel. dual   infeas     = 6.96e-11
 norm(X), norm(y), norm(Z) = 2.8e+00, 1.3e+00, 2.8e+00
 norm(A), norm(b), norm(C) = 5.5e+00, 2.0e+00, 3.9e+00
 Total CPU time (secs)  = 0.2  
 CPU time per iteration = 0.0  
 termination code       =  0
 DIMACS: 2.7e-10  0.0e+00  1.3e-10  0.0e+00  2.1e-09  2.7e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.229909
Done! 
Solving the lower bound SDP ... 
Calling SDPT3: 18 variables, 6 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints =  6
 dim. of sdp    var  =  4,   num. of sdp  blk  =  1
 dim. of linear var  =  8
*******************************************************************
   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|5.0e-01|2.4e+00|1.8e+02| 9.455844e+00| 0:0:00| chol  1  1 
 1|1.000|0.978|1.2e-06|1.4e-01|1.4e+01| 3.594871e+00| 0:0:00| chol  1  1 
 2|0.990|1.000|1.4e-06|9.0e-03|1.7e+00| 1.044015e+00| 0:0:00| chol  1  1 
 3|0.912|1.000|1.5e-07|9.0e-04|1.5e-01| 4.325185e-01| 0:0:00| chol  1  1 
 4|0.993|0.994|5.5e-08|9.4e-05|5.5e-03| 3.943689e-01| 0:0:00| chol  1  1 
 5|0.934|0.985|5.3e-09|1.0e-05|3.1e-04| 3.929550e-01| 0:0:00| chol  1  1 
 6|1.000|1.000|1.7e-08|9.0e-07|3.8e-05| 3.928326e-01| 0:0:00| chol  1  1 
 7|0.970|0.983|2.8e-09|1.6e-08|1.1e-06| 3.928207e-01| 0:0:00| chol  1  1 
 8|1.000|1.000|3.4e-09|5.6e-10|1.7e-07| 3.928204e-01| 0:0:00| chol  1  1 
 9|1.000|1.000|2.8e-10|1.1e-10|5.3e-09| 3.928203e-01| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   =  9
 primal objective value =  3.92820326e-01
 dual   objective value =  3.92820322e-01
 gap := trace(XZ)       = 5.28e-09
 relative gap           = 2.96e-09
 actual relative gap    = 2.37e-09
 rel. primal infeas     = 2.78e-10
 rel. dual   infeas     = 1.13e-10
 norm(X), norm(y), norm(Z) = 2.2e+00, 1.4e+00, 2.8e+00
 norm(A), norm(b), norm(C) = 5.5e+00, 2.0e+00, 3.9e+00
 Total CPU time (secs)  = 0.2  
 CPU time per iteration = 0.0  
 termination code       =  0
 DIMACS: 2.8e-10  0.0e+00  2.2e-10  0.0e+00  2.4e-09  3.0e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): -0.39282
Done! 
--------------------------------------------------------------------------------
The minimum and maximum values of rho_14 are: -0.39282 and 0.22991
with corresponding correlation matrices: 
    1.0000    0.6000    0.8239   -0.3928
    0.6000    1.0000    0.2979    0.5000
    0.8239    0.2979    1.0000   -0.5494
   -0.3928    0.5000   -0.5494    1.0000

    1.0000    0.6907    0.8000    0.2299
    0.6907    1.0000    0.2994    0.5694
    0.8000    0.2994    1.0000   -0.4000
    0.2299    0.5694   -0.4000    1.0000