TY - CONF
A1 - Bestuzheva, Ksenia
A1 - Gleixner, Ambros
A1 - VĂ¶lker, Helena
T1 - Strengthening SONC Relaxations with Constraints Derived from Variable Bounds
T2 - Proceedings of the Hungarian Global Optimization Workshop HUGO 2022
N2 - Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches.
Y1 - 2022
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/8795
SP - 41
EP - 44
ER -