Complexity of max problem

Question

Consider the problem

$\max_x \;||x||_2\\ x\in P\subseteq \mathbb{R}_{\geq 0}^n$

where $||\cdot||$ is Euclidean 2-norm and $P$ is a polytope in positive orthant of $\mathbb{R}^n$. Is this problem computationally hard?

Answer 1

It depends how the polytope is represented. In the V-polytope presentation (i.e. $P$ is given in terms of its vertices), the problem is trivial, as Tim mentioned in the comments. In the H-polytope presentation (i.e. $P$ is given as an intersection of halfspaces defined by inequalities), Brieden proved that a constant factor approximation is impossible unless P=NP. You can check that his proof indeed uses a polytope contained in the positive orthant.

As far as approximation algorithms, I believe the best known result is a factor $O(\sqrt{n/\log n})$ approximation ($n$ is dimension). The algorithm only needs a separation oracle, and this is the best possible approximation achievable in the oracle model, even by randomized algorithms. The same factor is achievable if the $\ell_2$ norm is replaced by an $\ell_p$ norm for $1\leq p \leq 2$. A better approximation may be possible for H-polytopes, but I am not aware of any such result.

EDIT: Actually I am now realizing that for the very similar problem of approximating the radius of a centrally symmetric H-polytope with $m$ facets, there is a simple SDP rounding that gives $O(\sqrt{\log m})$ approximation.

Let's say the problem is given as $\max\{\|x\|_2: -b \leq Ax \leq b\}$, where $A$ is an $m\times n$ matrix and $b \geq 0$ is an $m$-dimensional vector. The following vector program, which can be turned into an SDP in the usual way, is a relaxation:

$$ \begin{align} &\max \sqrt{\sum_{j = 1}^n \|v_j\|_2^2} \text{ s.t.}\\ &\left\|\sum a_{ij} v_j\right\|_2 \leq b_i \ \ \ \ \ \forall 1 \leq i \leq m \end{align} $$ where $v_1, \ldots, v_n$ range over $n$-dimensional vectors. A Gaussian projection now gives an approximation. Let $g$ be a standard $n$-dimensional Gaussian, and define a random $x$ by $x_i = \frac{1}{C\sqrt{\log m}} g^Tv_i$ for a big constant $C$. Then $\mathbb{E}\|x\|_2 = \frac{SDP}{C\sqrt{\log m}}$, where $SDP$ is the value of the relaxation, and for $C$ sufficiently big, $$ \mathbb{E} \max_{i = 1}^m \frac{|(Ax)_i|}{b_i} \leq 1. $$ The last inequality comes from the fact that $(Ax)_i/b_i$ is a Guassian random variable with variance $(C^2\log m)^{-1}$, and the maximum of $m$ such random variables is no more than 1 in expectation by a standard concentration argument.

I very much doubt that I am the first one to think of this approximation: does anyone know of a reference?