4

Consider the set $\mathcal S \subseteq \mathbb{R}^n$

$\mathcal S = \{x|f(x)\le c\}$

where $x\in\mathbb{R}^n$, $c\in\mathbb{R}$, and $f:\mathbb{R}^n\to\mathbb{R}$ is convex (so $\mathcal S$ is a convex set). Say I have a point $\hat x\in\mathbb{R}^n$ that is not in $\mathcal S$. I want to determine a vector $z$ such that $\hat x - z \in \mathcal S$.

I was thinking that the shortest distance vector, with respect to the Euclidean norm in $\mathbb{R}^n$, from $\hat x$ to $\mathcal S$ would yield the "best" $z$ vector, but I'm not sure how to obtain the shortest distance in $n$-dimensions.

I know in two dimensions we just take the derivative of $D(x) = \sqrt{(a-x)^2+(b-f(x))^2}$ and equate it to zero to determine the shortest distance from $(a,b)$ to the curve $y=f(x)$, but how does this generalize to $n$-dimensions?

jonem
  • 383
  • Can you give more restrictions on $f$? Your 2d case suggests that it might be differentiable. Is is perhaps polynomial? – MvG Feb 24 '14 at 07:50
  • 2
    The boundary $\partial S$ of $S$ is the level set of $f$ corresponding to the level $c$. The gradient $\nabla f$ will be orthogonal to that level set. You are looking for $z\in\partial S$ such that $\hat x=z+\lambda\nabla f(z)$. Depending on the exact form of $f$, this may or may not be of use to you. – MvG Feb 24 '14 at 07:58

2 Answers2

1

Consider, as you indicated, the function $h(z)=|\hat{x}-z|^2$. This is a convex function and what you are attempting is to minimize this function on the closed (I assume that your $f$ is also continuous here) convex set ${\mathcal S}$. There is a huge field of research called convex optimization which deals with exactly this problem, which very important for many applied math problems. If $f$ is also smooth, you can use Lagrange multipliers to find critical points and, then, minima. In general, take a look at the list of methods and references at the wikipedia page above or just google "convex optimization".

Moishe Kohan
  • 97,719
0

We observe that the problem is well defined. As $f$ is convex, then it is continuous; so $S$ is a closed set. It can be shown that given $x\in\mathbb{R}^n$, $\exists\, \overline{s}\in S$ such that $d(x,\overline{s})=d(x,S)$. Where $$d(x,S):=\text{inf }\lbrace d(x,s)\mid s\in S\rbrace$$ and the metric is the usual metric in $\mathbb{R}^n$.

We thus want to find such $\overline{s}$. We assume $x\in\mathbb{R}^n-S$, otherwise it is straightforward. So we look for the the solution of the following problem:

$$\overline{s}=\text{argmin } \lbrace d(x, s)\mid s\in S\rbrace$$

Consider $Y:=\lbrace y\in S\mid d(x,y) \leq d(x,a)\rbrace$ where $a\in S$. $Y$ is closed because the distance function $d(x,\cdot)$ is continuous, and $Y$ is also bounded; then it is compact (Heine-Borel). So

$$\overline{s}=\text{argmin } \lbrace d(x, s)\mid s\in Y\rbrace$$

which is again a well posed problem by Weierstrass Maximum Theorem, and can be solved (assuming smoothness) with Lagrange multipliers (actually KKT but it can be proven that the minimum is achieved on the boundary as mentioned in the comments).

Hope it helped.

Chazz
  • 827
  • 6
  • 18