Norm bounds and underestimators for unconstrained polynomial integer minimization
From MaRDI portal
Publication:684153
DOI10.1007/S00186-017-0608-YzbMATH Open1408.90324arXiv1502.05107OpenAlexW2963814313MaRDI QIDQ684153FDOQ684153
Authors: Sönke Behrends, Ruth Hübner, Anita Schöbel 
Publication date: 9 February 2018
Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)
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. 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. Our radius and lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework.
Full work available at URL: https://arxiv.org/abs/1502.05107
Recommendations
- Box-constrained mixed-integer polynomial optimization using separable underestimators
- Geometric and algebraic approaches to mixed-integer polynomial optimization using sos programming
- Integer Polynomial Optimization in Fixed Dimension
- Convex underestimators of polynomials
- Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10) Discrete location and assignment (90B80)
Cites Work
- CSDP, A C library for semidefinite programming
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Global optimization with polynomials and the problem of moments
- Minimizing polynomials via sum of squares over the gradient ideal
- Sums of squares, moment matrices and optimization over polynomials
- 50 Years of Integer Programming 1958-2008
- Class of global minimum bounds of polynomial functions
- Title not available (Why is that?)
- Semidefinite Optimization and Convex Algebraic Geometry
- Optimization of Polynomials on Compact Semialgebraic Sets
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Mixed integer nonlinear programming. Selected papers based on the presentations at the IMA workshop mixed-integer nonlinear optimization: Algorithmic advances and applications, Minneapolis, MN, USA, November 17--21, 2008
- Pseudo-Boolean optimization
- On the complexity of Putinar's Positivstellensatz
- Title not available (Why is that?)
- Integer Polynomial Optimization in Fixed Dimension
- Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
- Title not available (Why is that?)
- Optimization of Polynomial Functions
- Handbook on semidefinite, conic and polynomial optimization
- Modified \(r\)-algorithm to find the global minimum of polynomial functions
- Branch and Bound Experiments in Convex Nonlinear Integer Programming
- L’algebre de Boole et ses applications en recherche operationnelle
- There Cannot be any Algorithm for Integer Programming with Quadratic Constraints
- Title not available (Why is that?)
- A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
- Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
- Box-constrained mixed-integer polynomial optimization using separable underestimators
- Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces
- Integer optimization on convex semialgebraic sets
- Ellipsoid bounds for convex quadratic integer programming
Cited In (6)
- On stability and the Łojasiewicz exponent at infinity of coercive polynomials.
- Box-constrained mixed-integer polynomial optimization using separable underestimators
- Polynomially bounded minimization problems which are hard to approximate
- An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
- Geometric and algebraic approaches to mixed-integer polynomial optimization using sos programming
- Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization
Uses Software
This page was built for publication: Norm bounds and underestimators for unconstrained polynomial integer minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q684153)
