Let $C$ be a convex polytope in $\mathbb{R}^n$ with $m$ extremal points. Let $p\in \{1,2\}$.
Can the $\ell^p$-projection $\Pi_C:\mathbb{R}^n\to C$
$$
\Pi_C(x) \in \operatorname{argmin}_{z\in C}\, \|x-z\|_p^p
$$
be written as a tropical polynomial $p$? I.e.:
$$
p(x) = \Pi_C(x)
$$
for all $x\in \mathbb{R}^n$. If so, can we bound the degree of $p$ in terms of the data $(n,m,p)$?
$\begingroup$
$\endgroup$
Add a comment
|