Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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