Is this problem convex

I have a set of points U with known locations (x_i,y_i). I want to find the smallest circle that can enclose the points. This can formulated as

minimum r
subject to
$(x_i-x_d)^2+(y_i-y_d)<=r^2 $for all the points in the set U

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

My question is: Is this problem convex or not?.

You should be able to formulate this in CVX almost as you have written it, using norm to express the constraints. Declare r and the center of the circle to be variables. Therefore, it is convex.

CVX can convert this into a Second Order Cone Problem and pass to solver. There are other more specialized and faster algorithms to solve this well-studied problem.

Thank you Mark for your answer. Actually, I solved the problem using CVX. However, I was wondering if the problem is a convex problem. The objective function is a linear function so it is a convex function. Is the constraint convex?.

Given that the problem can be formulated for and accepted by CVX without use of integer (or binary) variables, it is a convex optimization problem. Yes, the constraints are convex.

I think this is a first! By far, the largest cohort of support questions received for CVX involve models that are not convex; people who simply have failed to understand that CVX does not even attempt to handle models that are not convex—indeed, not even all models that are.

So this is a pleasant and interesting reversal! :slight_smile: