% 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 4.0: 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      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|2.9e+02|8.9e+00|2.8e+03| 1.721824e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|0.971|1.000|8.4e+00|6.8e-02|8.5e+01| 5.569883e+00 -4.336238e+00| 0:0:00| chol  1  1 
 2|0.940|1.000|5.0e-01|6.8e-03|8.0e+00| 6.227339e-01 -3.291097e+00| 0:0:00| chol  1  1 
 3|0.776|0.715|1.1e-01|2.4e-03|2.7e+00| 4.213392e-01 -1.146735e+00| 0:0:00| chol  1  1 
 4|0.831|0.952|1.9e-02|1.8e-04|4.0e-01| 3.637727e-01  9.795053e-02| 0:0:00| chol  1  1 
 5|1.000|0.969|5.3e-09|3.8e-03|6.9e-02| 3.535620e-01  2.863755e-01| 0:0:00| chol  1  1 
 6|1.000|0.987|5.8e-09|5.1e-05|2.6e-02| 3.479517e-01  3.218399e-01| 0:0:00| chol  1  1 
 7|0.988|1.000|4.5e-10|7.0e-08|1.0e-02| 3.392570e-01  3.288598e-01| 0:0:00| chol  1  1 
 8|1.000|0.844|4.5e-10|1.7e-08|1.8e-03| 3.374285e-01  3.356581e-01| 0:0:00| chol  1  1 
 9|1.000|1.000|1.4e-10|7.7e-10|3.5e-04| 3.371978e-01  3.368475e-01| 0:0:00| chol  1  1 
10|0.987|0.985|2.0e-12|1.1e-10|5.0e-06| 3.370613e-01  3.370563e-01| 0:0:00| chol  1  1 
11|1.000|0.996|3.9e-13|1.5e-12|7.2e-08| 3.370594e-01  3.370594e-01| 0:0:00| chol  1  1 
12|1.000|0.997|1.2e-13|1.0e-12|8.9e-10| 3.370594e-01  3.370594e-01| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 12
 primal objective value =  3.37059399e-01
 dual   objective value =  3.37059398e-01
 gap := trace(XZ)       = 8.91e-10
 relative gap           = 5.32e-10
 actual relative gap    = 5.32e-10
 rel. primal infeas (scaled problem)   = 1.19e-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) = 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.10  
 CPU time per iteration = 0.01  
 termination code       =  0
 DIMACS: 1.2e-13  0.0e+00  1.7e-12  0.0e+00  5.3e-10  5.3e-10
-------------------------------------------------------------------
 
------------------------------------------------------------
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