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

Victor Magron 1 Henning Seidler 2 Timo De Wolff 2
1 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Abstract : 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.
Type de document :
Pré-publication, Document de travail
Rapport LAAS n° 19039. 2019
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.laas.fr/hal-02006899
Contributeur : Victor Magron <>
Soumis le : lundi 4 février 2019 - 22:56:59
Dernière modification le : mercredi 13 février 2019 - 16:00:38

Fichier

exactsonc_ArXiv1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-02006899, version 1

Citation

Victor Magron, Henning Seidler, Timo De Wolff. EXACT OPTIMIZATION VIA SUMS OF NONNEGATIVE CIRCUITS AND SUMS OF AM/GM EXPONENTIALS. Rapport LAAS n° 19039. 2019. 〈hal-02006899〉

Partager

Métriques

Consultations de la notice

22

Téléchargements de fichiers

11