Norm bounds and underestimators for unconstrained polynomial integer minimization
From MaRDI portal
Publication:684153
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.
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
Cites work
- scientific article; zbMATH DE number 3473554 (Why is no real title available?)
- scientific article; zbMATH DE number 1984325 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 3336816 (Why is no real title available?)
- 50 Years of Integer Programming 1958-2008
- A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
- Box-constrained mixed-integer polynomial optimization using separable underestimators
- Branch and Bound Experiments in Convex Nonlinear Integer Programming
- CSDP, A C library for semidefinite programming
- Class of global minimum bounds of polynomial functions
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
- Ellipsoid bounds for convex quadratic integer programming
- Global optimization with polynomials and the problem of moments
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Handbook on semidefinite, conic and polynomial optimization
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Integer Polynomial Optimization in Fixed Dimension
- Integer optimization on convex semialgebraic sets
- L’algebre de Boole et ses applications en recherche operationnelle
- Minimizing polynomials via sum of squares over the gradient ideal
- 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
- Modified \(r\)-algorithm to find the global minimum of polynomial functions
- On the complexity of Putinar's Positivstellensatz
- Optimization of Polynomial Functions
- Optimization of Polynomials on Compact Semialgebraic Sets
- Pseudo-Boolean optimization
- Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Semidefinite Optimization and Convex Algebraic Geometry
- Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces
- Sums of squares, moment matrices and optimization over polynomials
- There Cannot be any Algorithm for Integer Programming with Quadratic Constraints
Cited in
(6)- Box-constrained mixed-integer polynomial optimization using separable underestimators
- On stability and the Łojasiewicz exponent at infinity of coercive polynomials.
- 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
- Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization
- Geometric and algebraic approaches to mixed-integer polynomial optimization using sos programming
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)
