EXACT OPTIMIZATION VIA SUMS OF NONNEGATIVE CIRCUITS AND SUMS OF AM/GM EXPONENTIALS - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Article Dans Une Revue ACM Communications in Computer Algebra Année : 2019

EXACT OPTIMIZATION VIA SUMS OF NONNEGATIVE CIRCUITS AND SUMS OF AM/GM EXPONENTIALS

Résumé

We provide two hybrid numeric-symbolic optimization algorithms, computing exact sums of nonnegative circuits (SONC) and sums of arithmetic-geometric-exponentials (SAGE) decompositions. Moreover, we provide a hybrid numeric-symbolic decision algorithm for polynomials lying in the interior of the SAGE cone. Each framework , inspired by previous contributions of Parrilo and Peyrl, is a rounding-projection procedure. For a polynomial lying in the interior of the SAGE cone, we prove that the decision algorithm terminates within a number of arithmetic operations, which is polynomial in the degree and number of terms of the input, and singly exponential in the number of variables. We also provide experimental comparisons regarding the implementation of the two optimization algorithms.
Fichier principal
Vignette du fichier
exactsonc_ArXiv1.pdf (488.51 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02006899 , version 1 (04-02-2019)

Identifiants

Citer

Victor Magron, Henning Seidler, Timo de Wolff. EXACT OPTIMIZATION VIA SUMS OF NONNEGATIVE CIRCUITS AND SUMS OF AM/GM EXPONENTIALS. ACM Communications in Computer Algebra, 2019, ⟨10.1145/3326229.3326271⟩. ⟨hal-02006899⟩
63 Consultations
14 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More