% 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 sedumi: 20 variables, 11 equality constraints
   For improved efficiency, sedumi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 11, order n = 21, dim = 21, blocks = 1
nnz(A) = 220 + 0, nnz(ADA) = 121, nnz(L) = 66
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            1.53E+02 0.000
  1 :  -6.06E-01 3.12E+01 0.000 0.2043 0.9000 0.9000   1.15  1  1  2.1E+01
  2 :  -9.46E-03 9.65E+00 0.000 0.3093 0.9000 0.9000   2.65  1  1  3.1E+00
  3 :   2.00E-01 3.30E+00 0.000 0.3422 0.9000 0.9000   1.53  1  1  1.1E+00
  4 :   2.68E-01 8.55E-01 0.000 0.2588 0.9000 0.9000   1.11  1  1  2.9E-01
  5 :   2.87E-01 2.97E-01 0.000 0.3480 0.9000 0.9000   0.85  1  1  1.3E-01
  6 :   3.02E-01 1.42E-01 0.000 0.4782 0.9000 0.9000  -0.03  1  1  1.2E-01
  7 :   3.24E-01 4.47E-02 0.000 0.3140 0.9000 0.9000   0.54  1  1  4.3E-02
  8 :   3.33E-01 1.11E-02 0.000 0.2478 0.9000 0.9000   0.98  1  1  1.1E-02
  9 :   3.36E-01 1.62E-03 0.000 0.1468 0.9167 0.9000   1.00  1  1  2.3E-03
 10 :   3.37E-01 3.67E-05 0.000 0.0226 0.9901 0.9900   1.00  1  1  
iter seconds digits       c*x               b*y
 10      0.0  15.8  3.3705939820e-01  3.3705939820e-01
|Ax-b| =   1.8e-16, [Ay-c]_+ =   1.3E-15, |x|=  1.5e-01, |y|=  7.7e+00

Detailed timing (sec)
   Pre          IPM          Post
1.000E-02    4.000E-02    0.000E+00    
Max-norms: ||b||=1, ||c|| = 2.835687e+00,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 13.8708.
------------------------------------------------------------
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