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.
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
Actually, there’s an extraneous r
I forgot to remove from the variable declaration statement. But it does no harm.
1 Like