Chebyshev center of a polytope

[optim]

Hi There.

Can we use YALMIP to compute the chebyshev center of a polytope?  I have generated a polytope using Matlab's convhull() and the vertices of the polytope are :

a1 = [-1.131334    ;            -0.5561309];
a2 = [ -0.8957677     ;           -0.6011374];
a3 = [-0.7868264      ;          -0.2029448];
a4 = [-0.7016037        ;        -0.4832039];
a5 = [ -0.9607944 ;               -0.3226388];
a6 = [-1.131334    ;            -0.5561309];

If I solve using CVX, the solution is infeasible. (pg : 149 of CO).



 A = [a1 a2 a3 a4 a5 a6 ];
cvx_begin
variables x(2) r
minimize(r)
subject to
for i = 1:6
    norm(x-A(:,i))<=r
end
cvx_end
[x(1) x(2)]
r


Thanks.

[Johan Löfberg]

You are not computing the Chebychev ball. I have no idea what you actually compute geometrically

The problem is feasible though

x = sdpvar(2,1);
sdpvar r
Constraints = [];

for i = 1:6

    Constraints = [Constraints, norm(x-A(:,i))<=r];
end
optimize(Constraints,r);
ans =

    yalmiptime: 0.2232
    solvertime: 0.0108
          info: 'Successfully solved (GUROBI-GUROBI)'
       problem: 0

[optim]

Thanks Johan for your response. I have posted a wrong question/code earlier. The code, I pasted earlier is feasible and calculates the Chebychev ball correctly as you have identified. What I am trying to solve is find the largest Euclidean ball with the polyhedron as mentioned in the below link.

 http://web.cvxr.com/cvx/examples/cvxbook/Ch04_cvx_opt_probs/html/chebyshev_center.html

With my coordinates of the polytope given as:
a1 = [-2.000187 ; -0.9914489] ;
a2 = [ -1.810649; -1.057275] ;
a3 = [-1.485188 ;-1.117004] ;
a4 = [-1.212682 ;-0.8645709];
a5 = [ -1.659109 ; -0.8895376] ;
a6 = [-2.000187 ; -0.9914489] ;

The polytope is convex,where as the half spaces generated are thin and long (Attached *m file plots it), which is making the problem infeasible. Wondering if I can use YALMIP to solve for center by fitting the largest Euclidean ball for the provided coordinates.

Response greatly appreciated.

[Johan Löfberg]

Chebychev polytopes requires an half-space presentation Ax<=b. You have vertices vi, something completely different. You have to derive the half-space representation first (facet enumeration)

[Johan Löfberg]

Missed your definition of b.

Your polytope is not bounded, it extends arbitrary north-east

x = sdpvar(2,1);
plot([A*x <= b, x <= 1000])

Cheby-code

sdpvar r
x_c=sdpvar(2,1);
optimize(A*x_c + r*norm_ai <= b,-r)

[Marc Wijnand]

See also http://control.ee.ethz.ch/~mpt/3/Geometry/OperationsWithPolyhedra#ChebyCenter

[optim]

Thanks Johan & Marc..It works now.