Coverage for src / cvx / ball / solver.py: 100%

1"""Convex utilities for computing the minimum enclosing circle/ball. 

2 

3Provides a CVXPY-based solver for the smallest enclosing ball problem used by 

4tests and experiments in this repository. 

5""" 

6 

7from typing import Any 

8 

9import cvxpy as cp 

10import numpy as np 

11 

12 

13def min_circle_cvx(points: np.ndarray, **kwargs: dict[str, Any]) -> tuple[float, np.ndarray]: 

14 """Compute the smallest enclosing circle for a set of points using convex optimization. 

15 

16 This function solves the convex optimization problem to find the minimum radius 

17 circle that contains all the given points. It uses a second-order cone constraint 

18 to enforce that all points lie within the circle. 

19 

20 Args: 

21 points: A numpy array of shape (n, d) where n is the number of points 

22 and d is the dimension of the space. 

23 **kwargs: Additional keyword arguments to pass to the solver. 

24 Common options include 'solver' to specify which CVXPY solver to use. 

25 

26 Returns: 

27 A tuple containing: 

28 - The radius of the minimum enclosing circle (float) 

29 - The center coordinates of the circle (numpy.ndarray) 

30 

31 Example: 

32 >>> import numpy as np 

33 >>> from cvx.ball.solver import min_circle_cvx 

34 >>> points = np.array([[0, 0], [1, 0], [0, 1]]) 

35 >>> radius, center = min_circle_cvx(points, solver="CLARABEL") 

36 """ 

37 # cvxpy variable for the radius 

38 r = cp.Variable(shape=1, name="Radius") 

39 # cvxpy variable for the midpoint 

40 x = cp.Variable(points.shape[1], name="Midpoint") 

41 objective = cp.Minimize(r) 

42 constraints = [ 

43 cp.SOC( 

44 r * np.ones(points.shape[0]), 

45 points - cp.outer(np.ones(points.shape[0]), x), 

46 axis=1, 

47 ) 

48 ] 

49 

50 problem = cp.Problem(objective=objective, constraints=constraints) 

51 problem.solve(**kwargs) 

52 

53 return r.value[0], x.value