% 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 4.0: 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      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|3.8e+02|1.2e+01|7.0e+03| 2.720000e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|0.853|0.899|5.5e+01|1.3e+00|1.0e+03| 1.615618e+02 -2.109186e+01| 0:0:00| chol  1  1 
 2|0.566|0.691|2.4e+01|3.9e-01|5.3e+02| 1.512875e+02 -3.702322e+01| 0:0:00| chol  1  1 
 3|0.552|0.970|1.1e+01|1.2e-02|2.9e+02| 1.310951e+02 -5.398869e+01| 0:0:00| chol  1  1 
 4|0.497|1.000|5.4e+00|6.7e-05|2.1e+02| 1.518878e+02 -2.788832e+01| 0:0:00| chol  1  1 
 5|0.965|1.000|1.9e-01|6.7e-06|7.0e+01| 3.934317e+01 -2.987917e+01| 0:0:00| chol  1  1 
 6|1.000|1.000|5.2e-09|6.7e-07|1.7e+01| 6.782943e+00 -1.013722e+01| 0:0:00| chol  1  1 
 7|1.000|1.000|8.0e-10|6.8e-08|3.4e+00|-2.433570e+00 -5.793188e+00| 0:0:00| chol  1  1 
 8|1.000|1.000|1.3e-10|6.9e-09|9.4e-01|-4.464812e+00 -5.401832e+00| 0:0:00| chol  1  1 
 9|0.946|0.934|5.6e-11|1.1e-09|6.9e-02|-5.125936e+00 -5.195268e+00| 0:0:00| chol  1  1 
10|1.000|1.000|9.7e-15|7.8e-11|2.0e-02|-5.166203e+00 -5.185744e+00| 0:0:00| chol  1  1 
11|0.972|0.961|1.1e-14|1.1e-11|6.0e-04|-5.182011e+00 -5.182616e+00| 0:0:00| chol  1  1 
12|0.980|0.975|4.7e-14|1.3e-12|1.3e-05|-5.182468e+00 -5.182481e+00| 0:0:00| chol  1  1 
13|1.000|1.000|2.0e-13|1.0e-12|1.1e-06|-5.182477e+00 -5.182478e+00| 0:0:00| chol  1  1 
14|1.000|1.000|6.0e-13|1.0e-12|2.9e-08|-5.182477e+00 -5.182477e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 14
 primal objective value = -5.18247739e+00
 dual   objective value = -5.18247742e+00
 gap := trace(XZ)       = 2.88e-08
 relative gap           = 2.53e-09
 actual relative gap    = 2.53e-09
 rel. primal infeas (scaled problem)   = 5.95e-13
 rel. dual     "        "       "      = 1.00e-12
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 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.22  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 6.0e-13  0.0e+00  3.0e-12  0.0e+00  2.5e-09  2.5e-09
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
 
Computing optimal solution for 2nd formulation...
 
Calling SDPT3 4.0: 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      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|3.8e+02|1.2e+01|7.0e+03| 2.720000e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|0.853|0.899|5.5e+01|1.3e+00|1.0e+03| 1.615618e+02 -2.109186e+01| 0:0:00| chol  1  1 
 2|0.566|0.691|2.4e+01|3.9e-01|5.3e+02| 1.512875e+02 -3.702322e+01| 0:0:00| chol  1  1 
 3|0.552|0.970|1.1e+01|1.2e-02|2.9e+02| 1.310951e+02 -5.398869e+01| 0:0:00| chol  1  1 
 4|0.497|1.000|5.4e+00|6.7e-05|2.1e+02| 1.518878e+02 -2.788832e+01| 0:0:00| chol  1  1 
 5|0.965|1.000|1.9e-01|6.7e-06|7.0e+01| 3.934317e+01 -2.987917e+01| 0:0:00| chol  1  1 
 6|1.000|1.000|5.2e-09|6.7e-07|1.7e+01| 6.782943e+00 -1.013722e+01| 0:0:00| chol  1  1 
 7|1.000|1.000|8.0e-10|6.8e-08|3.4e+00|-2.433570e+00 -5.793188e+00| 0:0:00| chol  1  1 
 8|1.000|1.000|1.3e-10|6.9e-09|9.4e-01|-4.464812e+00 -5.401832e+00| 0:0:00| chol  1  1 
 9|0.946|0.934|5.6e-11|1.1e-09|6.9e-02|-5.125936e+00 -5.195268e+00| 0:0:00| chol  1  1 
10|1.000|1.000|9.7e-15|7.8e-11|2.0e-02|-5.166203e+00 -5.185744e+00| 0:0:00| chol  1  1 
11|0.972|0.961|1.1e-14|1.1e-11|6.0e-04|-5.182011e+00 -5.182616e+00| 0:0:00| chol  1  1 
12|0.980|0.975|4.7e-14|1.3e-12|1.3e-05|-5.182468e+00 -5.182481e+00| 0:0:00| chol  1  1 
13|1.000|1.000|2.0e-13|1.0e-12|1.1e-06|-5.182477e+00 -5.182478e+00| 0:0:00| chol  1  1 
14|1.000|1.000|6.0e-13|1.0e-12|2.9e-08|-5.182477e+00 -5.182477e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 14
 primal objective value = -5.18247739e+00
 dual   objective value = -5.18247742e+00
 gap := trace(XZ)       = 2.88e-08
 relative gap           = 2.53e-09
 actual relative gap    = 2.53e-09
 rel. primal infeas (scaled problem)   = 5.95e-13
 rel. dual     "        "       "      = 1.00e-12
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 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.20  
 CPU time per iteration = 0.01  
 termination code       =  0
 DIMACS: 6.0e-13  0.0e+00  3.0e-12  0.0e+00  2.5e-09  2.5e-09
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
 
Computing optimal solution for 3rd formulation...
 
Calling SDPT3 4.0: 75 variables, 21 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 21
 dim. of sdp    var  = 11,   num. of sdp  blk  =  2
 dim. of socp   var  = 17,   num. of socp blk  =  1
 dim. of linear var  = 10
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|3.4e+01|9.8e+00|2.9e+03| 1.000000e+01  0.000000e+00| 0:0:00| chol  1  1 
 1|0.378|0.391|2.1e+01|6.0e+00|2.0e+03|-1.785520e-01 -1.093555e+01| 0:0:00| chol  1  1 
 2|0.554|0.558|9.4e+00|2.6e+00|1.1e+03| 1.630251e+01 -3.670481e+01| 0:0:00| chol  1  1 
 3|0.526|0.537|4.5e+00|1.2e+00|6.3e+02| 4.423539e+01 -6.788671e+01| 0:0:00| chol  1  1 
 4|0.724|0.741|1.2e+00|3.2e-01|2.7e+02| 6.217691e+01 -8.370752e+01| 0:0:00| chol  1  1 
 5|1.000|1.000|1.2e-07|9.9e-06|7.9e+01| 3.265667e+01 -4.623591e+01| 0:0:00| chol  1  1 
 6|1.000|1.000|2.0e-08|1.0e-06|2.4e+01| 5.676782e+00 -1.866301e+01| 0:0:00| chol  1  1 
 7|0.907|1.000|6.7e-09|1.0e-07|5.9e+00|-1.665115e+00 -7.596274e+00| 0:0:00| chol  1  1 
 8|1.000|1.000|1.2e-09|1.1e-08|1.9e+00|-4.270126e+00 -6.135431e+00| 0:0:00| chol  1  1 
 9|0.889|0.937|3.9e-10|1.9e-09|2.8e-01|-5.018792e+00 -5.301623e+00| 0:0:00| chol  1  1 
10|1.000|0.983|1.6e-14|2.1e-10|6.3e-02|-5.149938e+00 -5.212604e+00| 0:0:00| chol  1  1 
11|0.831|1.000|3.0e-14|1.1e-11|1.3e-02|-5.174211e+00 -5.186808e+00| 0:0:00| chol  1  1 
12|0.985|0.978|5.0e-14|2.2e-12|6.2e-04|-5.182137e+00 -5.182760e+00| 0:0:00| chol  1  1 
13|0.977|0.983|8.8e-15|1.0e-12|1.3e-05|-5.182470e+00 -5.182483e+00| 0:0:00| chol  1  1 
14|0.991|0.986|4.8e-13|1.0e-12|5.7e-07|-5.182477e+00 -5.182478e+00| 0:0:00| chol  1  1 
15|1.000|1.000|1.5e-11|1.0e-12|1.5e-08|-5.182477e+00 -5.182477e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 15
 primal objective value = -5.18247741e+00
 dual   objective value = -5.18247742e+00
 gap := trace(XZ)       = 1.51e-08
 relative gap           = 1.33e-09
 actual relative gap    = 1.34e-09
 rel. primal infeas (scaled problem)   = 1.53e-11
 rel. dual     "        "       "      = 1.00e-12
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 1.3e+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.27  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 1.9e-11  0.0e+00  1.9e-12  0.0e+00  1.3e-09  1.3e-09
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5.18248
 
Computing optimal solution for 4th formulation...
 
Calling SDPT3 4.0: 75 variables, 21 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 21
 dim. of sdp    var  = 11,   num. of sdp  blk  =  2
 dim. of socp   var  = 17,   num. of socp blk  =  1
 dim. of linear var  = 10
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|3.4e+01|9.8e+00|2.9e+03| 1.000000e+01  0.000000e+00| 0:0:00| chol  1  1 
 1|0.378|0.391|2.1e+01|6.0e+00|2.0e+03|-1.785520e-01 -1.093555e+01| 0:0:00| chol  1  1 
 2|0.554|0.558|9.4e+00|2.6e+00|1.1e+03| 1.630251e+01 -3.670481e+01| 0:0:00| chol  1  1 
 3|0.526|0.537|4.5e+00|1.2e+00|6.3e+02| 4.423539e+01 -6.788671e+01| 0:0:00| chol  1  1 
 4|0.724|0.741|1.2e+00|3.2e-01|2.7e+02| 6.217691e+01 -8.370752e+01| 0:0:00| chol  1  1 
 5|1.000|1.000|1.2e-07|9.9e-06|7.9e+01| 3.265667e+01 -4.623591e+01| 0:0:00| chol  1  1 
 6|1.000|1.000|2.0e-08|1.0e-06|2.4e+01| 5.676782e+00 -1.866301e+01| 0:0:00| chol  1  1 
 7|0.907|1.000|6.7e-09|1.0e-07|5.9e+00|-1.665115e+00 -7.596274e+00| 0:0:00| chol  1  1 
 8|1.000|1.000|1.2e-09|1.1e-08|1.9e+00|-4.270126e+00 -6.135431e+00| 0:0:00| chol  1  1 
 9|0.889|0.937|3.9e-10|1.9e-09|2.8e-01|-5.018792e+00 -5.301623e+00| 0:0:00| chol  1  1 
10|1.000|0.983|2.0e-14|2.1e-10|6.3e-02|-5.149938e+00 -5.212604e+00| 0:0:00| chol  1  1 
11|0.831|1.000|2.0e-14|1.1e-11|1.3e-02|-5.174211e+00 -5.186808e+00| 0:0:00| chol  1  1 
12|0.985|0.978|2.5e-14|2.2e-12|6.2e-04|-5.182137e+00 -5.182760e+00| 0:0:00| chol  1  1 
13|0.977|0.983|1.4e-14|1.0e-12|1.3e-05|-5.182470e+00 -5.182483e+00| 0:0:00| chol  1  1 
14|0.991|0.986|6.9e-13|1.0e-12|5.7e-07|-5.182477e+00 -5.182478e+00| 0:0:00| chol  1  1 
15|1.000|1.000|2.3e-12|1.0e-12|1.5e-08|-5.182477e+00 -5.182477e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 15
 primal objective value = -5.18247741e+00
 dual   objective value = -5.18247742e+00
 gap := trace(XZ)       = 1.51e-08
 relative gap           = 1.33e-09
 actual relative gap    = 1.33e-09
 rel. primal infeas (scaled problem)   = 2.28e-12
 rel. dual     "        "       "      = 1.00e-12
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 1.3e+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.26  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 2.7e-12  0.0e+00  1.9e-12  0.0e+00  1.3e-09  1.3e-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!