8951
eng
reportzib
0
--
2023-01-19
--
Strengthening SONC Relaxations with Constraints Derived from Variable Bounds
Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set.
1438-0064
urn:nbn:de:0297-zib-89510
publish
Ksenia Bestuzheva
Ksenia Bestuzheva
Helena Völker
Ambros Gleixner
None of the above, but in this section
Explicit machine computation and programs (not the theory of computation or programming)
Nonconvex programming, global optimization
Polyhedral combinatorics, branch-and-bound, branch-and-cut
Mathematical Optimization
Gleixner, Ambros
MODAL-SynLab
MODAL-Gesamt
Bestuzheva, Ksenia
Müller, Helena
AI in Society, Science, and Technology
https://opus4.kobv.de/opus4-zib/files/8951/zr.pdf