<p>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), <a href="http://rd.springer.com/article/10.1007/s00454-002-2756-x#">Brieden  proved</a> 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.</p>

<p>As far as approximation algorithms, I believe the <a href="http://dx.doi.org/10.1112/S0025579300014364">best known result</a> 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 <a href="https://web.math.princeton.edu/~naor/homepage%20files/subu.pdf">achievable</a> 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.</p>

<p><strong>EDIT</strong>: 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. </p>

<p>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:</p>

<p>$$
\begin{align}
&amp;\max \sqrt{\sum_{j = 1}^n \|v_j\|_2^2} \text{ s.t.}\\
&amp;\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.</p>

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

CC BY-SA 3.0
2015-05-05T00:40:18.760Z
What is known in terms of upper bounds for approximation?
Chandra Chekuri
CC BY-SA 3.0
2015-05-05T02:40:22.413Z
@ChandraChekuri I edited what I know about approximation into the answer.
Sasho Nikolov
CC BY-SA 3.0
2015-05-07T17:52:32.793Z
@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
CC BY-SA 3.0
2015-05-07T21:43:33.893Z
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
CC BY-SA 3.0
2015-05-07T21:45:21.910Z
@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
CC BY-SA 3.0
2015-05-04T21:09:19.873Z
2015-05-07T03:39:17.853Z
2015-05-07T03:39:17.853Z
Sasho Nikolov
<p>Consider the problem  </p>

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

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

CC BY-SA 3.0
2015-05-04T20:30:28.060Z
This is easy assuming the vertices of $P$ are part of the input.
Tim
<cc.complexity-theory><complexity-classes><convex-optimization>
Complexity of max problem
Star
# Complexity of max problem

(Asked by: username_0 on 2015-05-04)

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?

**Tags:** cc.complexity-theory, complexity-classes, convex-optimization

> **Comments:**
> **username_1**: This is easy assuming the vertices of $P$ are part of the input.  

---

## 1 answers

### Answer by username_2 on 2015-05-04. Score: 13

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 username_1 mentioned in the comments. In the H-polytope presentation (i.e. $P$ is given as an intersection of halfspaces defined by inequalities), [Brieden proved](http://rd.springer.com/article/10.1007/s00454-002-2756-x#) 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](http://dx.doi.org/10.1112/S0025579300014364) 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](https://web.math.princeton.edu/~naor/homepage%20files/subu.pdf) 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?

> **Comments:**
> **username_3**: What is known in terms of upper bounds for approximation?  
> **username_2**: @ChandraChekuri I edited what I know about approximation into the answer.  
> **username_0**: @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$.  
> **username_2**: 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.  
> **username_2**: @username_0 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).  

---

