# Is unconstrained integer convex optimization problem NP-hard?

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.

• What is the input of the problem, and what is $F$? – Emil Jeřábek Nov 16 '12 at 15:40
• 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. – Vahan Nov 16 '12 at 15:44
• 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? – Emil Jeřábek Nov 16 '12 at 15:52
• F:Z^N -> R and assume there is a oracle giving the value of F(x) for each integral x. – Vahan Nov 16 '12 at 15:54
• 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. – Emil Jeřábek Nov 16 '12 at 18:28