Norm bounds and underestimators for unconstrained polynomial integer minimization
Behrends S, Huebner R, Schoebel A (2018)
Publication Type: Journal article
Publication year: 2018
Journal
Book Volume: 87
Pages Range: 73-107
Journal Issue: 1
DOI: 10.1007/s00186-017-0608-y
Abstract
We consider the problem of minimizing a polynomial function over the integer lattice. Though impossible in general, we use a known sufficient condition for the existence of continuous minimizers to guarantee the existence of integer minimizers as well. In case this condition holds, we use sos programming to compute the radius of a p-norm ball which contains all integer minimizers. We prove that this radius is smaller than the radius known from the literature. Our numerical results show that the number of potentially optimal solutions is reduced by several orders of magnitude. Furthermore, we derive a new class of underestimators of the polynomial function. Using a Stellensatz from real algebraic geometry and again sos programming, we optimize over this class to get a strong lower bound on the integer minimum. Also our lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework.
Involved external institutions
Germany (DE)How to cite
APA:
Behrends, S., Huebner, R., & Schoebel, A. (2018). Norm bounds and underestimators for unconstrained polynomial integer minimization. Mathematical Methods of Operations Research, 87(1), 73-107. https://dx.doi.org/10.1007/s00186-017-0608-y
MLA:
Behrends, Sonke, Ruth Huebner, and Anita Schoebel. "Norm bounds and underestimators for unconstrained polynomial integer minimization." Mathematical Methods of Operations Research 87.1 (2018): 73-107.
BibTeX: Download