1
$\begingroup$

Does anyone know a reference to the answer if unconstrained integer convex optimization problem (i.e. $\min_{x\in \mathbb{Z}^N} F(x)$, $F$ is convex and $N$ is NOT fixed) is NP-hard?

Thank you in advance.

Well, thanks to your critical comments I've found the answer to the question, and here it is. Let $F$ be a piecewise linear convex function, i.e. $F(x)=\max_{j\in J} \sum_{i=1}^N a_i^j x_i + a_0^j$, then $\min_{x\in \mathbb{Z}^N} F(x) = \min_{x\in \mathbb{Z}^N} \max_{j\in J}\{\sum_{i=1}^N a_i^j x_i + a_0^j\} = \min_{x\in \mathbb{Z}^N} \min_{f\in \mathbb{R}} (f, s.t. f\geq \sum_{i=1}^N a_i^j x_i + a_0^j, \forall j\in J)$, the last optimization problem is a mixed integer linear program, which is known to be NP-Hard.

$\endgroup$
8
  • $\begingroup$ What is the input of the problem, and what is $F$? $\endgroup$ Nov 16, 2012 at 15:40
  • $\begingroup$ F is an arbitrary convex function, doesn't have to be smooth. I guess the only input is F, but I'm interested in a general result for any convex F. $\endgroup$
    – Vahan
    Nov 16, 2012 at 15:44
  • $\begingroup$ First, a function from where to where? Second, the input of a computational problem is a finite string in a finite alphabet. How do you represent your function in such a way? $\endgroup$ Nov 16, 2012 at 15:52
  • $\begingroup$ F:Z^N -> R and assume there is a oracle giving the value of F(x) for each integral x. $\endgroup$
    – Vahan
    Nov 16, 2012 at 15:54
  • 2
    $\begingroup$ The question needs to be rewritten so that it unambiguously defines the computational model being used and what is meant by “NP-hard” in this context, in sufficient detail so that it becomes a well-defined problem, rather than a vague metaphor. Until then I’m voting to close as not a real question. $\endgroup$ Nov 16, 2012 at 18:28

1 Answer 1

2
$\begingroup$

Yes, since the shortest vector in lattice problem is NP-hard, see http://en.wikipedia.org/wiki/Lattice_problem

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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