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.

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

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .