Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 5 von 12
Zurück zur Trefferliste

Strengthening SONC Relaxations with Constraints Derived from Variable Bounds

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-88306
  • 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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Ksenia BestuzhevaORCiD, Ambros GleixnerORCiD, Helena Völker
Dokumentart:ZIB-Report
MSC-Klassifikation:14-XX ALGEBRAIC GEOMETRY / 14-04 Explicit machine computation and programs (not the theory of computation or programming)
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-08 Computational methods
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C26 Nonconvex programming, global optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C30 Nonlinear programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
CCS-Klassifikation:I. Computing Methodologies
Datum der Erstveröffentlichung:23.11.2022
Schriftenreihe (Bandnummer):ZIB-Report (22-23)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.