1
$\begingroup$

I have a simple question. Often times in optimization, the following function is used:

Let $H$ be a real Hilbert space and $C$ a nonempty closed convex subset of $H$, then the metric projection is defined as the function,

$$P_C(x) = \text{argmin}_{y \in C} ||x - y||$$

Sometimes (not always), this function will have a closed form. For example, if $C$ is the interval $[-1,1]$ in $\mathbb{R}$, then $P_C(x) = \min(\max(x,-1),1)$.

Is there a pattern to when $P_C$ has a closed form versus when you have to solve it numerically?

Improve this question
$\endgroup$
9
  • $\begingroup$ In finite dimensions at least the formula for the distance to an ellipsoid is known. They use this quite a bit in geodesy. $\endgroup$
    – alvarezpaiva
    Commented May 14, 2021 at 21:44
  • 1
    $\begingroup$ @alvarezpaiva Ok. I am asking because currently what I see in optimization related research is a disclaimer: "$C$ has to be simple", but I do not quite understand what types of sets this "simple" definition encompass. $\endgroup$
    – Sin Nombre
    Commented May 14, 2021 at 21:50
  • $\begingroup$ So the question is "for what convex bodies in a Hilbert space, besides affine subspaces and quadrics, does the projection function admit a closed form?" ? $\endgroup$
    – alvarezpaiva
    Commented May 14, 2021 at 22:14
  • $\begingroup$ That is one way to sharpen the question. yes $\endgroup$
    – Sin Nombre
    Commented May 14, 2021 at 22:16
  • 1
    $\begingroup$ Say $C$ is a polytope, like a cube or a tetrahedron, in $n$-dimensions. Then the closed-form solution is to exhaustively enumerate all the corners, but most polytopes have an exponential number of corners (e.g. a hypercube has $2^n$ corners). On the other hand, a numerical algorithm can exactly solve this projection as a quadratic program in $n^{3.5}$ time. Why look for a closed-form solution? $\endgroup$
    – Richard Zhang
    Commented May 14, 2021 at 23:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .