9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – batwing Mar 17 at 18:31
  • $\begingroup$ @batwing I am interested a general approach $\endgroup$ – C Marius Mar 17 at 19:09
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – C Marius Mar 19 at 9:25
  • $\begingroup$ Oops yes, that's what I meant to write. $\endgroup$ – batwing Mar 19 at 14:21
  • $\begingroup$ @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. $\endgroup$ – batwing Mar 19 at 20:07
  • $\begingroup$ @batwing I just withdrew my comment. $\endgroup$ – Mark L. Stone Mar 19 at 20:20
  • $\begingroup$ @batwing can you expand on converting the supremum to infimum? What are the means of doing this? And in what circumstances is this possible? $\endgroup$ – C Marius Mar 19 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.