Section 4.3.1: Compute the Chebyshev center of a polyhedron
randn('state',0);
n = 10; m = 2*n;
A = randn(m,n);
b = A*rand(n,1) + 2*rand(m,1);
norm_ai = sum(A.^2,2).^(.5);
fprintf(1,'Computing Chebyshev center...');
cvx_begin
variable r(1)
variable x_c(n)
dual variable y
maximize ( r )
y: A*x_c + r*norm_ai <= b;
cvx_end
fprintf(1,'Done! \n');
fprintf(1,'The Chebyshev center coordinates are: \n');
disp(x_c);
fprintf(1,'The radius of the largest Euclidean ball is: \n');
disp(r);
Computing Chebyshev center...
Calling SDPT3: 20 variables, 11 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 11
dim. of linear var = 20
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap mean(obj) cputime
-------------------------------------------------------------------
0|0.000|0.000|1.3e+02|8.9e+00|1.2e+03| 3.850116e+01| 0:0:00| chol 1 1
1|0.970|1.000|3.9e+00|6.8e-02|4.2e+01|-7.822279e-01| 0:0:00| chol 1 1
2|0.894|1.000|4.1e-01|6.8e-03|6.1e+00|-9.173179e-01| 0:0:00| chol 1 1
3|0.842|0.815|6.5e-02|1.8e-03|1.5e+00|-1.131967e-01| 0:0:00| chol 1 1
4|0.875|0.855|8.2e-03|1.3e-02|3.1e-01| 2.283673e-01| 0:0:00| chol 1 1
5|1.000|0.964|7.2e-09|2.1e-03|2.7e-02| 3.373936e-01| 0:0:00| chol 1 1
6|0.643|1.000|3.4e-10|6.9e-07|1.6e-02| 3.330254e-01| 0:0:00| chol 1 1
7|0.967|0.811|2.6e-09|1.9e-07|2.9e-03| 3.363071e-01| 0:0:00| chol 1 1
8|1.000|1.000|7.9e-10|6.9e-09|9.2e-04| 3.369376e-01| 0:0:00| chol 1 1
9|0.984|0.973|2.9e-11|1.0e-09|2.2e-05| 3.370553e-01| 0:0:00| chol 1 1
10|0.988|0.988|4.6e-13|1.7e-11|2.5e-07| 3.370594e-01| 0:0:00| chol 1 1
11|0.998|0.996|7.9e-15|1.1e-12|3.6e-09| 3.370594e-01| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 11
primal objective value = 3.37059400e-01
dual objective value = 3.37059396e-01
gap := trace(XZ) = 3.56e-09
relative gap = 2.13e-09
actual relative gap = 2.13e-09
rel. primal infeas = 7.87e-15
rel. dual infeas = 1.07e-12
norm(X), norm(y), norm(Z) = 1.5e-01, 7.7e+00, 2.4e+01
norm(A), norm(b), norm(C) = 1.9e+01, 2.0e+00, 6.5e+00
Total CPU time (secs) = 0.1
CPU time per iteration = 0.0
termination code = 0
DIMACS: 7.9e-15 0.0e+00 1.8e-12 0.0e+00 2.1e-09 2.1e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.337059
Done!
The Chebyshev center coordinates are:
-0.1116
-1.5760
0.1079
-2.1751
3.2264
3.5820
4.3394
3.0680
0.4449
0.3164
The radius of the largest Euclidean ball is:
0.3371