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.

  • $\begingroup$ What is the input of the problem, and what is $F$? $\endgroup$ – Emil Jeřábek Nov 16 '12 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 '12 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$ – Emil Jeřábek Nov 16 '12 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 '12 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$ – Emil Jeřábek Nov 16 '12 at 18:28

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

| cite | improve this answer | |

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.