Section 4.3.1: Compute the Chebyshev center of a polyhedron

% Boyd & Vandenberghe "Convex Optimization"
% Joëlle Skaf - 08/16/05
%
% The goal is to find the largest Euclidean ball (i.e. its center and
% radius) that lies in a polyhedron described by linear inequalites in this
% fashion: P = {x : a_i'*x <= b_i, i=1,...,m}

% Generate the data
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);

% Build and execute model
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');

% Display results
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