Norm bounds and underestimators for unconstrained polynomial integer minimization (Q684153)

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.