Compute the distance from a point inside a convex set to the boundary of the set

Question

Problem

Let $\mathcal C = \{ X \in \mathbb{R}^n \mid g(X) \leq 0\}$ where $g$ is convex, and let $X_c \in \mathcal{C}$. Is there any algorithm to compute the distance from $X_c$ to the boundary of $\mathcal{C}$ ? This can be formulated like the following optimization problem:

$$ \min_{X\in \mathbb{R}^n} \hspace{0.5cm} (X-X_c)^\top\cdot (X - X_c) \quad \text{s.t} \quad g(X) = 0 $$ or even worse:

$$ \min_{X\in \mathbb{R}^n} \hspace{0.5cm} (X-X_c)^\top\cdot (X - X_c) \quad \text{s.t} \quad g(X) \geq 0 $$ which is a minimization of a convex function over a concave domain.

Question

Are there any known algorithms for this problem? Is the distance from point to boundary convex in general?

Update

Indeed, based on the answer of @batwing below it is enough to solve: \begin{align}\max &\quad r\\\text{s.t}&\quad g(X_c + r\cdot u) \leq 0\\&\quad\forall \|u\| \leq 1\end{align} which is an infinite programming problem (it has an infinity of constraints). One can reformulate this in the following way: \begin{align}\max&\quad r\\\text{s.t}&\quad g(X_c + r\cdot u) \leq 0\\&\quad\|u\| \leq 1\end{align} which is unfortunately not convex in variables $u$ and $r$.

Answer 1

You should be able to modify the maximum volume inscribed ellipsoid within a convex set formulation provided in slide 3 of https://see.stanford.edu/materials/lsocoee364a/08GeometricalProbs.pdf for your problem.

The formulation can be adapted to your case as follows: \begin{align} \underset{ B \in S_{++}^{n}, r}{\max}&\quad r\\ \text{s.t.}&\quad \underset{\|u\|_{2} \leq 1}{\sup} I_{\mathcal{C}}(B u + X_c) \leq 0\\ &\quad B_{ij} = 0, i\neq j\\ &\quad B_{ii} = r, \forall i \in \lbrace{1, 2 , \dotsc, n \rbrace} \end{align} where $I_{\mathcal{C}} (\cdot)$ is the indicator function for convex set $\mathcal{C}$. The optimal $r$ corresponding to the problem above is the distance you required. The constraints on $B$ basically enforce $B$ to be an identity matrix scaled by $r$, to force $B$ to be a euclidean ball instead of an ellipsoid.

As mentioned in the link above, evaluating whether $Bu + X_{c} \in \mathcal{C}$ is hard in general even for convex $\mathcal{C}$. However, if $\mathcal{C}$ has a special structure or is simple enough, then you may be able to use the formulation above.