AEPS

Résumé

De nombreuses applications techniques (télécommunications sans fil, l'analyse des erreurs de circularité) nécessitent de résoudre des problèmes d'optimisation impliquant un certain degré d'incertitude, qu'elle soit déterministe ou stochastique. Le but de ce projet est de traiter de tels problèmes en développant, analysant et appliquant des cadres d'optimisation basés sur des relaxations de la programmation semi-définie (SDP pour semidefinite programming).

Coordinateurs

Bruno Gaujal (Inria/LIG)

Victor Magron (Verimag)

Résultats

Un problème de longue date lié à l'implémentation de programmes numériques en virgule flottante consiste à fournir une analyse efficace mais précise des erreurs de sortie en résolvant des problèmes d'optimisation déterministes incertains. Nous avons développé un cadre basé sur des relaxations de programmation semi-définie pour calculer les limites inférieures ou supérieures des erreurs d'arrondi absolues pour certaines classes de programmes numériques. Nous avons développé un cadre de limites inférieures appelé « robustsdp » mis en œuvre dans un logiciel appelé FPSDP. La figure ci-dessous compare notre méthode avec d'autres, en termes de performance (axe x) et de précision (axe y).

Nous avons développé un cadre de limites supérieures et deux logiciels appelés FPBern et FPKriSten. 

Un travail en cours vise à faire une comparaison numérique des performances moyennes obtenues lors de l'optimisation de fonctions fortement convexes à l'aide d'algorithmes de descente de gradient stochastique (SGD pour stochastic gradient descent) et de descente en miroir (MD pour mirror descent). Ces résultats numériques seront obtenus grâce à l'implémentation d'un logiciel pratique. En outre, nous proposons d'analyser la complexité moyenne des algorithmes SGD et MD. Une application intéressante est d'estimer l'efficacité de l'algorithme MD développé par Gaujal et Mertikopoulos pour traiter les SDP stochastiques. 

Sélection de publications

Victor Magron and Mountassir Farid. Certified Lower Bounds of Roundoff Errors using Semidefinite Programming, submitted to Transactions on Mathematical Software, 2016. preprint available at arxiv.org/abs/1611.01318.

Alexandre Rocca, Victor Magron, and Thao Dang. Certified Roundoff Error Bounds using Bernstein Expansions and Sparse Krivine-Stengle Representations, submitted to the 24th IEEE Symposium on Computer Arithmetic, 2017, preprint available at arxiv.org/abs/1610.07038.

Josu Doncel, Nicolas Gast, Bruno Gaujal. A Mean-Field Game Analysis of SIR Dynamics with Vaccination. Submitted to Operations Research Letters, 2016.