How to write this constraints for this convex problem in cvx?

1

I want to find the smallest circle containing all the points of the set S. This is how I considered the model:

minimize r
subject to
(x_i - x_d)^2 + (y_i-y_d)^2 <= r^2
for all points (x_i,y_i) in set S.

where r is the radius and (x_d,y_d) is the center of the circle.

I know this is convex. But I’m not sure how to write it in cvx. I did this:

S = [-2 5;-4 10;-2 0;5 1;-1 6;0 0;9 7;8 -7;-2 -6; 5 -3];
cvx_begin
variables x_d y_d r  
B = [x_d y_d;x_d y_d;x_d y_d;x_d y_d;x_d y_d;x_d y_d;x_d y_d;x_d y_d;x_d y_d;x_d y_d]
norm(S-B)<=r
minimize(r)
cvx_end

And for displaying the circle and points:

  for j=1:10
    xx = S(j,1);
    yy = S(j,2);
    hold on
    plot(xx,yy,'.r')
  end
  circle(x_d,y_d,r)
  hold off

It was solved by cvx, but my problem is that the result is not quite optimal because I can see the circle could have been a lot smaller. I’m very new in cvx, so would someone help me to make it better? I think the way I defined B is not good.

2

Welcome to the forum!!

Your program minimizes the matrix (operator) 2-norm of a 10 by 2 matrix, i.e., minimizes the largest singular value of the 10 by 2 matrix, which is not what you intended to do.

I think what you want is the following. It computes the 2 norm separately for each of the 10 data points (see help below for norms), and minimizes the maximum of those norms.

cvx_begin
variables x_d y_d r  
minimize(max(norms(S-repmat([x_d y_d],[size(S,1),1]),2,2)))
cvx_end

help norms

norms Computation of multiple vector norms.
norms( X ) provides a means to compute the norms of multiple vectors
packed into a matrix or N-D array. This is useful for performing
max-of-norms or sum-of-norms calculations.

All of the vector norms, including the false "-inf" norm, supported
by NORM() have been implemented in the norms() command.
  norms(X,P)           = sum(abs(X).^P).^(1/P)
  norms(X)             = norms(X,2).
  norms(X,inf)         = max(abs(X)).
  norms(X,-inf)        = min(abs(X)).
If X is a vector, these computations are completely identical to
their NORM equivalents. If X is a matrix, a row vector is returned
of the norms of each column of X. If X is an N-D matrix, the norms
are computed along the first non-singleton dimension.

norms( X, [], DIM ) or norms( X, 2, DIM ) computes Euclidean norms
along the dimension DIM. norms( X, P, DIM ) computes its norms
along the dimension DIM.

Disciplined convex programming information:
    norms is convex, except when P<1, so an error will result if these
    non-convex "norms" are used within CVX expressions. norms is
    nonmonotonic, so its input must be affine.
1 Like
3

Thank you very much!

4

Actually, there’s an extraneous r I forgot to remove from the variable declaration statement. But it does no harm.

1 Like