The Quadratic Graver Cone, Quadratic Integer Minimization, and Extensions

We consider the nonlinear integer programming problem of minimizing a quadratic function over the integer points in variable dimension satisfying a system of linear inequalities. We show that when the Graver basis of the matrix defining the system is given, and the quadratic function lies in a suita...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2010-06
Main Authors: Lee, Jon, Onn, Shmuel, Romanchuk, Lyubov, Weismantel, Robert
Format: Article
Language:English
Subjects:
Cones
Integer programming
Linear functions
Mathematical analysis
Matrix methods
Optimization
Polynomials
Quadratic equations
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the nonlinear integer programming problem of minimizing a quadratic function over the integer points in variable dimension satisfying a system of linear inequalities. We show that when the Graver basis of the matrix defining the system is given, and the quadratic function lies in a suitable {\em dual Graver cone}, the problem can be solved in polynomial time. We discuss the relation between this cone and the cone of positive semidefinite matrices, and show that none contains the other. So we can minimize in polynomial time some non-convex and some (including all separable) convex quadrics. We conclude by extending our results to efficient integer minimization of multivariate polynomial functions of arbitrary degree lying in suitable cones.
ISSN:2331-8422