6
$\begingroup$

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?

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

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?

$\endgroup$
  • $\begingroup$ What is known in terms of upper bounds for approximation? $\endgroup$ – Chandra Chekuri May 5 '15 at 0:40
  • $\begingroup$ @ChandraChekuri I edited what I know about approximation into the answer. $\endgroup$ – Sasho Nikolov May 5 '15 at 2:40
  • $\begingroup$ @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$. $\endgroup$ – Star May 7 '15 at 17:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov May 7 '15 at 21:43
  • 1
    $\begingroup$ @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). $\endgroup$ – Sasho Nikolov May 7 '15 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.