Set of solutions for nearest point to a convex polyhedron (simplex)

euclidean-geometrygeometryoptimizationpolyhedrasimplex

I'm working on a problem that involves the sets of solutions to the problem of finding nearest point of a convex polyhedron to a given point. Let $y$ be a point in a convex polyhedron defined by a set of linear inequalities $Ay \leq b$ and $x \in \Bbb R^n$ a target point. Specifically, I'm concerned with solutions when in terms of Euclidean distance where the convex polyhedron is the interior of a simplex, i.e.,

\begin{gather*}
\min_y \, y^\top y – 2 x^\top y \\
\text{subject to } Ay \leq b
\end{gather*}

with

\begin{align*}
A = \begin{bmatrix} -I_n \\ 1_n^\top \end{bmatrix} \quad \text{and} \quad b = \begin{bmatrix} 0_n \\ 1 \end{bmatrix} .
\end{align*}

Now, my question concerns the solutions as $x$ changes. In particular, I'm pretty sure that the sets of $\Bbb R^n$ that get mapped to the simplex in this way can be separated by half-planes. Intuitively, this is because for each $x$ not in the simplex, the nearest point should either be a corner or a face. Using the algorithm here, I convinced myself this was true for $\Bbb R^2$, as I could find a pattern that looked something like this:

Solutions in R2

where the orange sets are closest to a corner and the blue sets are closer to a face. I'm looking for either:

  • A reference to this type of result and, ideally, a way to describe those sets that get mapped to the corners and faces when the dimensionality is larger than 2.

  • A way to make this argument rigorous.

Best Answer

I had written a previous answer, but I think my new answer supersedes it, so I'm replacing the old one with what follows.

I claim that if $S$ is convex polyhedron in $\mathbf{R}^n$, then:

  • for each $x \in \mathbf{R}^n$, there is a unique point $f(x) \in S$ closest to $x$;

  • for each $x \in \mathbf{R}^n$, the point $f(x)$ is the orthogonal projection of $f$ onto some face of $S$ (of dimension $0, \dots, n$);

  • this face can be chosen to be the smallest face of $S$ containing $f(x)$;

  • this choice being made, the boundaries of the sets in the corresponding partition of $\mathbf{R}^n$ are contained in the union of finitely many hyperplanes $H$, which can be determined as follows: for each face $k$-dimensional face $F$ of $S$ ($k = 1, \dots, n$) , and each $(k-1)$-dimensional subface $F'$ of $F$, let $H$ be the collection of all points whose orthogonal projection onto the subspace extending $F$ belongs to the subspace extending $F'$;

  • if $T \subseteq \mathbf{R}^n$ is one of the sets of the partition, and $F$ is the associated face, then $f(x)$ is the orthogonal projection of $x$ onto $F$ for all points $x$ in the closure of $T$ (not only for $x$ in $T$).

That the boundaries can be curved when $S$ is not assumed convex is shown by the following example. Let $S$ be the quadrilateral $ABCD$ with $A = (1,0)$, $B = (0,0)$, $C = (0,2)$, $D = (-1,-1)$. Then one of the boundaries is a portion of the parabola with focus $A$ and directrix $BC$.

I'll begin with some general comments about projecting onto a convex set.

If $S$ is any subset of $\mathbf{R}^n$, the function $x \mapsto d(x,S)$ is continuous on $\mathbf{R}^n$. If $S$ is closed, then by a simple compactness argument, the distance $d(x,S)$ is attained at at least one point $s \in S$.

If $S$ is closed and convex, then this point $s$ is unique, for if the minimum distance were attained in two points $s_1$ and $s_2$, the midpoint of the segment $s_1s_2$ would be still closer to $x$. Thus we can define a projection function $f \colon \mathbf{R}^n \to S$ assigning to each $x \in \mathbf{R}^n$ the unique point $f(x)$ of $S$ that is closest to it.

The projection function $f$ is in fact continuous. If $x \in \mathbf{R}^n$ and $\varepsilon > 0$, let $S' = S - B(f(x),\varepsilon)$. The distance $d(x,S')$ is attained at some point $s' \in S'$, and by the uniqueness of the projection we have $d(x,S') = d(x,s') > d(x,f(x)) = d(x,S)$. Now as $y \to x$, we have $d(y,S) \to d(x,S)$ and $d(y,S') \to d(x,S')$, hence for $y$ sufficiently close to $x$, we must have $f(y) \in B(f(x),\varepsilon)$, which shows that $f$ is continuous.

Now assume that $S$ is a convex polyhedron. For any $s \in S$, there is a face of minimum dimension $d$ (with $0 \leq d \leq n$) to which $s$ belongs. This face is contained in all other faces containing $s$, and it is also the unique face containing $s$ within its interior (where "interior" means the interior relative to the subspace extending the face). Thus we can partition space into a finite number of subsets by assigning to each $x \in \mathbf{R}^n$ the face associated in this way with $f(x)$.

If $f(x)$ belongs to the interior of a particular face $F$, it is easy to see that $f(x)$ is determined as the orthogonal projection of $x$ onto the subspace extending $F$ (since otherwise there must be nearby points of $F$ that are closer to $x$). More generally, if $f(x)$ belongs to a face $F$, though not necessarily to its interior, then $f(x)$ must be the orthogonal projection of $x$ onto the subspace extending some subface of $F$.

Now assume that $x$ is a boundary point of one of the subsets into which $\mathbf{R}^n$ is partitioned. Then $x$ is as close as we like to points associated with two distinct faces, say $F$ and $G$. By the continuity of $f$, the point $f(x)$ belongs to $F \cap G$. Thus $f(x)$ can be obtained by orthogonal projection onto some subface of $F \cap G$. At the same time, by continuity, $f(x)$ must be the orthogonal projection of $x$ onto $F$ as well as onto $G$. The faces $F$ and $G$ being assumed distinct, in any case $f(x)$ is simultaneously the orthogonal projection of $x$ onto a face of $S$ (either $F$ or $G$) and a proper subface of that face. Since we can always replace the subface by one of dimension one less than that of the face, the result follows.

Related Question