Exercise 4.27: Matrix fractional minimization using second-order cone programming
randn('state',0);
m = 16; n = 8;
A = randn(m,n);
b = randn(m,1);
B = randn(m,n);
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;
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;
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;
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;
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!