# Complexity of max problem

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?

• This is easy assuming the vertices of $P$ are part of the input. – Tim May 4 '15 at 20:30

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?

• What is known in terms of upper bounds for approximation? – Chandra Chekuri May 5 '15 at 0:40
• @ChandraChekuri I edited what I know about approximation into the answer. – Sasho Nikolov May 5 '15 at 2:40
• @Sasho: How is this approximation related to the structure of polytope $P$, i.e., if $P$ is a parallelotope? In your approximation, you violated the assumption that $P$ is in positive orthant of $R^n$. – Star May 7 '15 at 17:52
• I can't say much about how the structure of $P$ can help in the SDP algorithm above, except that it needs to be centrally symmetric. You are correct, the central symmetry is in tension with the the positive orthant condition: that's why I said that the problem is related but not the same. In some cases you may be able to transform your positive polytope to make it centrally symmetric, but that's all I can say at the moment. – Sasho Nikolov May 7 '15 at 21:43
• @Star on the other hand, your original problem appears to be easy if $P$ is a parallelotope in the positive orthant. A parallelotope is representable as $P = \{Ax: 0 \leq x \leq 1\}$ for an $n\times n$ matrix $A$ and 0 and 1 respectively the all zero and all ones vectors. If $P \in \mathbb{R}_+^n$, then $A$ has all positive entries, and the $\ell_2$ norm is maximized at $A1$ ($A$ times the all-ones vector, i.e. the sum of the columns of $A$). This in fact works for all zonotopes in the positive orthant (for a zonotope $A$ doesn't have to be a square matrix). – Sasho Nikolov May 7 '15 at 21:45