Consider the following optimization problem:

$\text{max}_{p} \quad ||p||^2 \\ s.t: x\geq 0\\ p\in D$

where $D$ is a convex set. Is this problem $\mathcal{NP}$-hard?

  • $\begingroup$ You might just as well write this problem as $\max \| p \|^{2}$ subject to $p \in D$. $\endgroup$ Jan 27 '14 at 19:54
  • $\begingroup$ Do you mean to say $x\le \|p\|^2$ for any $p\in D$, or for all $p\in D$? I suppose the former, but it would help to clarify your question. $\endgroup$ Jan 28 '14 at 4:11
  • $\begingroup$ The "for all $p \in D$" version of the problem is convex- it amounts to $\min \| p \|$ subject to $p \in D$. $\endgroup$ Jan 28 '14 at 5:49
  • $\begingroup$ possible duplicate of Feasibility checking $\endgroup$
    – Star
    Jan 28 '14 at 15:10
  • $\begingroup$ @Star: This question isn't a duplicate of the feasibility checking question. $\endgroup$ Jan 29 '14 at 2:52

Your original problem statement is vague in that you haven't described how the convex set $D$ would be encoded.

The problem simplifies immediately to

$\max \| p \|^{2}$

subject to

$p \in D$.

We'll show that this problem is NP-Hard by reduction from 0-1 Integer Linear Programming feasibility.

The 0-1 Integer Linear Programming feasibility problem is a well known NP-Complete problem: "Given integer matrices $A$ and $b$, is there a 0-1 vector $x$ such that $Ax=b$?"

Consider the change of variables $y_{i}=2x_{i}-1$. Then our original problem becomes "Is there a vector $y$ with $y_{i}=\pm 1$ for $i=1, 2, \ldots, n$, such that $\hat{A}y=\hat{b}$?" It's easy to see that this transformation produces a new instance of size polynomial in the size of the original problem.

Now, suppose that we could solve

$\max \| y \|^{2}$

subject to


$ -1 \leq y_{i} \leq 1$, for $i=1, 2, \ldots, n$.

in polynomial time. The optimal value is $n$ if and only $y$ has a solution in which all entries are $\pm 1$. The feasible set for this optimization problem is clearly convex. A polynomial time algorithm to find the optimal $y$ would give us a polynomial time algorithm for the original 0-1 ILP feasibility problem.

This shows that in general, the problem

$\max \| p \|^{2}$

subject to

$p \in D$

is NP-Hard, even if $D$ is restricted to being convex.

  • $\begingroup$ Aren't you making the assumption here that $D$ is given as the intersection of half-spaces, i.e., as a polytope? What if $D$ is a general but smoothly bounded convex set? $\endgroup$ Jan 28 '14 at 4:10
  • $\begingroup$ @WolfgangBangerth you've got the logic slightly backwards. I'm saying that if you can solve the problem for an arbitrary convex set $D$ in polynomial time then you can solve the problem for the particular convex set ${y | \hat{A}y=\hat{b}, -1 \leq y_{i} \leq 1, i=1, 2, \ldots, n}$ in polynomial time, and if you can do that you can solve the 0-1 ILP feasibility problem in polynomial time. $\endgroup$ Jan 28 '14 at 5:16
  • $\begingroup$ @ Brian Borchers: What is your assumption on $D$. I think that for the sets $D$ that are empty or can be described as a polynomial number of extreme points, the problem is still tractable. However, it may be intractable in general. $\endgroup$
    – Star
    Jan 28 '14 at 9:33
  • $\begingroup$ @BrianBorchers: But there are, of course, sets $D$ for which the problem is very simple to solve. For example if $D$ is described by a very small number of variables, e.g., a ball of known radius and known center. This problem is much simpler to solve than if I gave you either an interior or exterior polyhedral approximation to the ball. $\endgroup$ Jan 29 '14 at 2:04
  • $\begingroup$ @WolfgangBangerth: BrianBorchers is making the type of argument I suggested Star make. Essentially, you argue that an instance of an NP-complete problem can be transformed "easily" into the problem class described by Star. It's true that as you narrow the problem class, it may be possible to construct more efficient means of solving the problem (for instance, knowing that an optimization problem is convex enables the use of polynomial-time algorithms; for a problem that is not known to be convex, it may not be possible to use those algorithms and obtain a solution). $\endgroup$ Jan 29 '14 at 2:49

Show that an $\mathcal{NP}$-complete problem reduces to your problem in polynomial time. A classic example of this for nonconvex optimization is the reduction from subset sum to nonconvex optimization by Murty and Kabadi. For your specific problem, you will have to formulate a similar type of reduction. You might be able to leverage work done on quadratically-constrained quadratic programs.


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.