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

## 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$$.

• You are looking for the radius of the largest sphere that can be inscribed within $\mathcal{C}$ centered at $X_{c}$. If for instance $\mathcal{C}$ is a polyhedral set i.e. $g(X) = \underset{i \in [n]}{\max}(a_i^\top x - b_i)$, then the problem is trivial since you just compute the euclidean distance to each hyper-plane. So it helps to mention in the problem how exactly $g(X)$ is specified. Mar 17 '20 at 18:31
• @batwing I am interested a general approach Mar 17 '20 at 19:09

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.
• It seems to me that evaluating whether $B\cdot u + X_c \in \mathcal{C}$ is not difficult for o given $u, X_c, B$ but computing the the suppremum is. Mar 19 '20 at 9:25
• @MarkL.Stone - I think the LHS expression in the supremum constraint is convex with respect to $B$. In fact, depending on the definition of $\mathcal{C}$, it may be mathematically easier to solve, if we first convert the sup on the left-hand side to an infimum using convex duality (as is commonly done in robust optimization). Then, since the inequality in sup constraint is $\leq$, we can remove the inf altogether. Mar 19 '20 at 20:07