Exercise 4.27: Matrix fractional minimization using second-order cone programming

% From Boyd & Vandenberghe, "Convex Optimization"
% Joëlle Skaf - 09/26/05
%
% Shows the equivalence of the following formulations:
% 1)        minimize    (Ax + b)'*inv(I + B*diag(x)*B')*(Ax + b)
%               s.t.    x >= 0
% 2)        minimize    (Ax + b)'*inv(I + B*Y*B')*(Ax + b)
%               s.t.    x >= 0
%                       Y = diag(x)
% 3)        minimize    v'*v + w'*inv(diag(x))*w
%               s.t.    v + Bw = Ax + b
%                       x >= 0
% 4)        minimize    v'*v + w'*inv(Y)*w
%               s.t.    Y = diag(x)
%                       v + Bw = Ax + b
%                       x >= 0

% Generate input data
randn('state',0);
m = 16; n = 8;
A = randn(m,n);
b = randn(m,1);
B = randn(m,n);

% Problem 1: original formulation
disp('Computing optimal solution for 1st formulation...');
cvx_begin
    variable x1(n)
    minimize( matrix_frac(A*x1 + b , eye(m) + B*diag(x1)*B') )
    x1 >= 0;
cvx_end
opt1 = cvx_optval;

% Problem 2: original formulation (modified)
disp('Computing optimal solution for 2nd formulation...');
cvx_begin
    variable x2(n)
    variable Y(n,n) diagonal
    minimize( matrix_frac(A*x2 + b , eye(m) + B*Y*B') )
    x2 >= 0;
    Y == diag(x2);
cvx_end
opt2 = cvx_optval;

% Problem 3: equivalent formulation (as given in the book)
disp('Computing optimal solution for 3rd formulation...');
cvx_begin
    variables x3(n) w(n) v(m)
    minimize( square_pos(norm(v)) + matrix_frac(w, diag(x3)) )
    v + B*w == A*x3 + b;
    x3 >= 0;
cvx_end
opt3 = cvx_optval;

% Problem 4: equivalent formulation (modified)
disp('Computing optimal solution for 4th formulation...');
cvx_begin
    variables x4(n) w(n) v(m)
    variable Y(n,n) diagonal
    minimize( square_pos(norm(v)) + matrix_frac(w, Y) )
    v + B*w == A*x4 + b;
    x4 >= 0;
    Y == diag(x4);
cvx_end
opt4 = cvx_optval;

% Display the results
disp('------------------------------------------------------------------------');
disp('The optimal value for each of the 4 formulations is: ');
[opt1 opt2 opt3 opt4]
disp('They should be equal!')
Computing optimal solution for 1st formulation...
 
Calling SDPT3: 161 variables, 9 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints =  9
 dim. of sdp    var  = 17,   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|3.7e+02|1.1e+01|6.3e+03| 1.360000e+02| 0:0:00| chol  1  1 
 1|0.863|0.907|5.1e+01|1.1e+00|8.8e+02| 6.969822e+01| 0:0:00| chol  1  1 
 2|0.611|0.706|2.0e+01|3.3e-01|4.2e+02| 5.191702e+01| 0:0:00| chol  1  1 
 3|0.598|1.000|7.9e+00|6.7e-04|2.2e+02| 3.054778e+01| 0:0:00| chol  1  1 
 4|0.806|1.000|1.5e+00|6.7e-05|1.4e+02| 3.219147e+01| 0:0:00| chol  1  1 
 5|1.000|1.000|1.0e-08|6.7e-06|5.3e+01| 6.955446e-01| 0:0:00| chol  1  1 
 6|1.000|1.000|4.7e-09|6.7e-07|1.2e+01|-2.011606e+00| 0:0:00| chol  1  1 
 7|1.000|1.000|6.5e-10|6.8e-08|3.2e+00|-4.393583e+00| 0:0:00| chol  1  1 
 8|0.976|0.950|1.7e-10|9.9e-09|4.0e-01|-5.041775e+00| 0:0:00| chol  1  1 
 9|1.000|1.000|3.6e-11|7.0e-10|7.9e-02|-5.157350e+00| 0:0:00| chol  1  1 
10|0.952|0.933|1.7e-12|1.2e-10|4.5e-03|-5.181293e+00| 0:0:00| chol  1  1 
11|0.987|0.967|3.6e-14|1.1e-11|2.4e-04|-5.182422e+00| 0:0:00| chol  1  1 
12|0.948|0.982|2.2e-13|1.2e-12|1.1e-05|-5.182473e+00| 0:0:00| chol  1  1 
13|0.979|1.000|2.9e-12|1.0e-12|3.7e-06|-5.182476e+00| 0:0:00| chol  1  1 
14|1.000|1.000|3.5e-13|1.0e-12|3.7e-07|-5.182477e+00| 0:0:00| chol  1  1 
15|1.000|1.000|1.5e-12|1.0e-12|2.8e-08|-5.182477e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 15
 primal objective value = -5.18247739e+00
 dual   objective value = -5.18247742e+00
 gap := trace(XZ)       = 2.77e-08
 relative gap           = 2.44e-09
 actual relative gap    = 2.44e-09
 rel. primal infeas     = 1.47e-12
 rel. dual   infeas     = 1.00e-12
 norm(X), norm(y), norm(Z) = 6.9e+00, 5.2e+00, 1.4e+01
 norm(A), norm(b), norm(C) = 4.6e+01, 2.0e+00, 7.5e+00
 Total CPU time (secs)  = 0.5  
 CPU time per iteration = 0.0  
 termination code       =  0
 DIMACS: 1.5e-12  0.0e+00  3.0e-12  0.0e+00  2.4e-09  2.4e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
Computing optimal solution for 2nd formulation...
 
Calling SDPT3: 161 variables, 9 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints =  9
 dim. of sdp    var  = 17,   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|3.7e+02|1.1e+01|6.3e+03| 1.360000e+02| 0:0:00| chol  1  1 
 1|0.863|0.907|5.1e+01|1.1e+00|8.8e+02| 6.969822e+01| 0:0:00| chol  1  1 
 2|0.611|0.706|2.0e+01|3.3e-01|4.2e+02| 5.191702e+01| 0:0:00| chol  1  1 
 3|0.598|1.000|7.9e+00|6.7e-04|2.2e+02| 3.054778e+01| 0:0:00| chol  1  1 
 4|0.806|1.000|1.5e+00|6.7e-05|1.4e+02| 3.219147e+01| 0:0:00| chol  1  1 
 5|1.000|1.000|1.0e-08|6.7e-06|5.3e+01| 6.955446e-01| 0:0:00| chol  1  1 
 6|1.000|1.000|4.7e-09|6.7e-07|1.2e+01|-2.011606e+00| 0:0:00| chol  1  1 
 7|1.000|1.000|6.5e-10|6.8e-08|3.2e+00|-4.393583e+00| 0:0:00| chol  1  1 
 8|0.976|0.950|1.7e-10|9.9e-09|4.0e-01|-5.041775e+00| 0:0:00| chol  1  1 
 9|1.000|1.000|3.6e-11|7.0e-10|7.9e-02|-5.157350e+00| 0:0:00| chol  1  1 
10|0.952|0.933|1.7e-12|1.2e-10|4.5e-03|-5.181293e+00| 0:0:00| chol  1  1 
11|0.987|0.967|3.6e-14|1.1e-11|2.4e-04|-5.182422e+00| 0:0:00| chol  1  1 
12|0.948|0.982|2.2e-13|1.2e-12|1.1e-05|-5.182473e+00| 0:0:00| chol  1  1 
13|0.979|1.000|2.9e-12|1.0e-12|3.7e-06|-5.182476e+00| 0:0:00| chol  1  1 
14|1.000|1.000|3.5e-13|1.0e-12|3.7e-07|-5.182477e+00| 0:0:00| chol  1  1 
15|1.000|1.000|1.5e-12|1.0e-12|2.8e-08|-5.182477e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 15
 primal objective value = -5.18247739e+00
 dual   objective value = -5.18247742e+00
 gap := trace(XZ)       = 2.77e-08
 relative gap           = 2.44e-09
 actual relative gap    = 2.44e-09
 rel. primal infeas     = 1.47e-12
 rel. dual   infeas     = 1.00e-12
 norm(X), norm(y), norm(Z) = 6.9e+00, 5.2e+00, 1.4e+01
 norm(A), norm(b), norm(C) = 4.6e+01, 2.0e+00, 7.5e+00
 Total CPU time (secs)  = 0.5  
 CPU time per iteration = 0.0  
 termination code       =  0
 DIMACS: 1.5e-12  0.0e+00  3.0e-12  0.0e+00  2.4e-09  2.4e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
Computing optimal solution for 3rd formulation...
 
Calling SDPT3: 74 variables, 20 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 20
 dim. of sdp    var  = 11,   num. of sdp  blk  =  2
 dim. of socp   var  = 17,   num. of socp blk  =  1
 dim. of linear var  =  9
*******************************************************************
   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|2.9e+01|3.1e+00|7.1e+02| 2.000000e+00| 0:0:00| chol  1  1 
 1|0.453|0.444|1.6e+01|1.8e+00|4.5e+02|-1.713434e+00| 0:0:00| chol  1  1 
 2|0.625|0.349|6.0e+00|1.1e+00|2.9e+02|-5.556666e-02| 0:0:00| chol  1  1 
 3|0.839|0.432|9.7e-01|6.5e-01|1.4e+02|-5.447366e+00| 0:0:00| chol  1  1 
 4|0.694|1.000|3.0e-01|9.7e-05|2.7e+01|-7.949518e+00| 0:0:00| chol  1  1 
 5|0.345|0.145|1.9e-01|8.4e-05|3.5e+01| 6.391739e+00| 0:0:00| chol  1  1 
 6|0.574|1.000|8.2e-02|9.7e-07|2.6e+01|-6.875378e+00| 0:0:00| chol  1  1 
 7|1.000|0.453|2.0e-09|1.6e-02|1.5e+01|-6.881816e+00| 0:0:00| chol  1  1 
 8|1.000|1.000|6.9e-10|1.0e-08|4.9e+00|-5.428063e+00| 0:0:00| chol  1  1 
 9|1.000|0.874|1.6e-10|2.3e-09|8.0e-01|-5.239931e+00| 0:0:00| chol  1  1 
10|1.000|0.996|1.6e-14|1.4e-10|1.5e-01|-5.175864e+00| 0:0:00| chol  1  1 
11|0.821|1.000|4.6e-14|1.1e-11|3.7e-02|-5.177070e+00| 0:0:00| chol  1  1 
12|1.000|0.993|4.2e-14|2.0e-12|4.5e-03|-5.182223e+00| 0:0:00| chol  1  1 
13|0.958|0.978|8.7e-14|1.1e-12|1.6e-04|-5.182450e+00| 0:0:00| chol  1  1 
14|0.960|0.982|3.8e-13|1.0e-12|5.5e-06|-5.182476e+00| 0:0:00| chol  1  1 
15|0.968|1.000|1.8e-11|1.0e-12|6.5e-07|-5.182477e+00| 0:0:01| chol  1  1 
16|1.000|1.000|4.7e-11|1.5e-12|3.4e-08|-5.182477e+00| 0:0:01|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 16
 primal objective value = -5.18247740e+00
 dual   objective value = -5.18247743e+00
 gap := trace(XZ)       = 3.37e-08
 relative gap           = 2.96e-09
 actual relative gap    = 2.92e-09
 rel. primal infeas     = 4.65e-11
 rel. dual   infeas     = 1.50e-12
 norm(X), norm(y), norm(Z) = 1.2e+01, 4.9e+00, 6.2e+00
 norm(A), norm(b), norm(C) = 1.7e+01, 2.4e+00, 4.7e+00
 Total CPU time (secs)  = 0.5  
 CPU time per iteration = 0.0  
 termination code       =  0
 DIMACS: 5.6e-11  0.0e+00  2.8e-12  0.0e+00  2.9e-09  3.0e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
Computing optimal solution for 4th formulation...
 
Calling SDPT3: 74 variables, 20 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 20
 dim. of sdp    var  = 11,   num. of sdp  blk  =  2
 dim. of socp   var  = 17,   num. of socp blk  =  1
 dim. of linear var  =  9
*******************************************************************
   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|2.9e+01|3.1e+00|7.1e+02| 2.000000e+00| 0:0:00| chol  1  1 
 1|0.453|0.444|1.6e+01|1.8e+00|4.5e+02|-1.713434e+00| 0:0:00| chol  1  1 
 2|0.625|0.349|6.0e+00|1.1e+00|2.9e+02|-5.556666e-02| 0:0:00| chol  1  1 
 3|0.839|0.432|9.7e-01|6.5e-01|1.4e+02|-5.447366e+00| 0:0:00| chol  1  1 
 4|0.694|1.000|3.0e-01|9.7e-05|2.7e+01|-7.949518e+00| 0:0:00| chol  1  1 
 5|0.345|0.145|1.9e-01|8.4e-05|3.5e+01| 6.391739e+00| 0:0:00| chol  1  1 
 6|0.574|1.000|8.2e-02|9.7e-07|2.6e+01|-6.875378e+00| 0:0:00| chol  1  1 
 7|1.000|0.453|2.0e-09|1.6e-02|1.5e+01|-6.881816e+00| 0:0:00| chol  1  1 
 8|1.000|1.000|6.9e-10|1.0e-08|4.9e+00|-5.428063e+00| 0:0:00| chol  1  1 
 9|1.000|0.874|1.6e-10|2.3e-09|8.0e-01|-5.239931e+00| 0:0:00| chol  1  1 
10|1.000|0.996|1.6e-14|1.4e-10|1.5e-01|-5.175864e+00| 0:0:00| chol  1  1 
11|0.821|1.000|4.6e-14|1.1e-11|3.7e-02|-5.177070e+00| 0:0:00| chol  1  1 
12|1.000|0.993|4.2e-14|2.0e-12|4.5e-03|-5.182223e+00| 0:0:00| chol  1  1 
13|0.958|0.978|8.7e-14|1.1e-12|1.6e-04|-5.182450e+00| 0:0:00| chol  1  1 
14|0.960|0.982|3.8e-13|1.0e-12|5.5e-06|-5.182476e+00| 0:0:00| chol  1  1 
15|0.968|1.000|1.8e-11|1.0e-12|6.5e-07|-5.182477e+00| 0:0:00| chol  1  1 
16|1.000|1.000|4.7e-11|1.5e-12|3.4e-08|-5.182477e+00| 0:0:01|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 16
 primal objective value = -5.18247740e+00
 dual   objective value = -5.18247743e+00
 gap := trace(XZ)       = 3.37e-08
 relative gap           = 2.96e-09
 actual relative gap    = 2.92e-09
 rel. primal infeas     = 4.65e-11
 rel. dual   infeas     = 1.50e-12
 norm(X), norm(y), norm(Z) = 1.2e+01, 4.9e+00, 6.2e+00
 norm(A), norm(b), norm(C) = 1.7e+01, 2.4e+00, 4.7e+00
 Total CPU time (secs)  = 0.5  
 CPU time per iteration = 0.0  
 termination code       =  0
 DIMACS: 5.6e-11  0.0e+00  2.8e-12  0.0e+00  2.9e-09  3.0e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
------------------------------------------------------------------------
The optimal value for each of the 4 formulations is: 

ans =

    5.1825    5.1825    5.1825    5.1825

They should be equal!