Coverage for src / min_circle / msk.py: 94%

1"""MOSEK implementation for finding the minimum enclosing circle. 

2 

3This module provides functions to find the minimum enclosing circle 

4using the MOSEK Fusion optimization library. 

5 

6Note: 

7 The MOSEK dependency is optional. Importing this module no longer requires 

8 MOSEK to be installed. The import happens lazily inside the solver function. 

9""" 

10 

11from typing import Any 

12 

13import numpy as np 

14 

15from .utils.circle import Circle 

16 

17_MOSEK_IMPORT_ERROR = ( 

18 "MOSEK is required for min_circle_mosek(). Install with `pip install 'min_circle[solvers]'` " 

19 "or install the `mosek` package manually." 

20) 

21 

22 

23def min_circle_mosek(points: np.ndarray, **kwargs: Any) -> Circle: 

24 """Find the minimum enclosing circle using MOSEK Fusion. 

25 

26 Uses the MOSEK Fusion API to formulate and solve the minimum enclosing circle 

27 problem as a second-order cone program (SOCP). 

28 

29 Args: 

30 points: Array of 2D points with shape (n, 2) 

31 **kwargs: Additional keyword arguments to pass to the solver 

32 

33 Returns: 

34 Circle object containing the center and radius of the minimum enclosing circle 

35 

36 Raises: 

37 ImportError: If the `mosek` package is not installed. Install with 

38 `pip install 'min_circle[solvers]'` or add the `solvers` extra. 

39 

40 Notes: 

41 Implementation based on MOSEK's minimum ellipsoid tutorial: 

42 https://github.com/MOSEK/Tutorials/blob/master/minimum-ellipsoid/minimum-ellipsoid.ipynb 

43 """ 

44 try: 

45 import mosek.fusion as mf 

46 except Exception as exc: # pragma: no cover - only hit when MOSEK is missing 

47 raise ImportError(_MOSEK_IMPORT_ERROR) from exc 

48 

49 with mf.Model() as model: 

50 # Create variables for radius and center 

51 r = model.variable("Radius", 1) 

52 x = model.variable("Midpoint", [1, points.shape[1]]) 

53 

54 # Number of points 

55 k = points.shape[0] 

56 

57 # Repeat the radius and center variables for each point 

58 r0 = mf.Var.repeat(r, k) 

59 x0 = mf.Var.repeat(x, k) 

60 

61 # Create second-order cone constraints ensuring all points are within the circle 

62 model.constraint(mf.Expr.hstack(r0, mf.Expr.sub(x0, points)), mf.Domain.inQCone()) 

63 

64 # Set the objective to minimize the radius 

65 model.objective("obj", mf.ObjectiveSense.Minimize, r) 

66 

67 # Solve the optimization problem 

68 model.solve(**kwargs) 

69 

70 # Return the circle with the optimal center and radius 

71 return Circle(radius=r.level(), center=x.level())