Norm bounds and underestimators for unconstrained polynomial integer minimization
This paper presents a new way of finding underestimators for integer polynomial optimization and improves the bounds on the norm of integer and continuous minimizers. Both ideas are implemented within a branch \& bound approach showing how they improve its performance. Currently, one can compute one underestimator at the beginning of the branch and bound process which is used for generating lower bounds throughout the whole algorithm. Instead, one could also compute a new underestimator at each node of the branch and bound tree. This would improve the bounds but due to the comparatively large computation time for solving an sos-program does not pay off in terms of overall efficiency. The authors analyze in which nodes the computation of a new underestimator improves the procedure and analyze how to find an underestimator which is likely to be a good one for all subnodes. It is shown that the norm bound \(R\) obtained by them is drastically smaller than the norm bound \(R_{lit}\) available in the literature. The proposed procedure can be extended to mixed integer polynomial optimization. The radius and lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework.
- 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
- 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
- Class of global minimum bounds of polynomial functions
- CSDP, A C library for semidefinite programming
- 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
- 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?)
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Integer optimization on convex semialgebraic sets
- Integer Polynomial Optimization in Fixed Dimension
- 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
- Geometric and algebraic approaches to mixed-integer polynomial optimization using sos programming
- 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
- On stability and the Łojasiewicz exponent at infinity of coercive polynomials.
- Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization
- Box-constrained mixed-integer polynomial optimization using separable underestimators
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)
