The Quadratic Graver Cone, Quadratic Integer Minimization, and Extensions

Consider the general nonlinear integer minimization problem in standard form,
, (1) with with , and .

It is well known to be NP-hard already for linear functions. However, recently it was shown that, if the Graver basis G(A) of A is given as part of the input, then the problem can be solved in polynomial time for the following classes of functions. First, in [1], for composite concave functions , with concave, and d fixed. Second, in [3], for separable convex functions with each fi univariate convex, and in particular for linear functions . While the Graver basis is a complex object, it can be computed in polynomial time from A for many natural and useful classes of matrices as demonstrated in [1, 3]. Moreover, the results of [2] imply that there is a parameterized scheme that enables to construct increasingly better approximations of the Graver basis of any matrix A and obtain increasingly better approximations to problem (1), see [4] for details.

In this article we continue this line of investigation and consider problem (1) for quadratic functions with , , and . We also discuss extensions to multivariate polynomial functions of arbitrary degree.

We begin by noting that problem (1) remains NP-hard even if the Graver basis is part of the input and even if the objective function is quadratic convex of rank 1.