AEPS

Abstract

Many technical applications (wireless telecommunications, circularity error analysis) require solving optimization problems involving some degree of uncertainty, whether deterministic or stochastic. The goal of this project is to address such problems by developing, analyzing, and applying optimization frameworks based on relaxations of semidefinite programming (SDP).

Coordinators

Bruno Gaujal (Inria/LIG)

Victor Magron (Verimag)

Results

A long-standing problem associated with the implementation of floating-point numerical programs is providing an efficient yet accurate analysis of output errors when solving deterministic optimization problems with uncertainty. We have developed a framework based on semidefinite programming relaxations to compute lower or upper bounds on absolute roundoff errors for certain classes of numerical programs. We have developed a lower bound framework called “robustsdp” implemented in software called FPSDP. The figure below compares our method with others in terms of performance (x-axis) and accuracy (y-axis).

We have developed a framework for upper bounds and two software programs called FPBern and FPKriSten. 

Ongoing work aims to conduct a numerical comparison of the average performance achieved when optimizing strongly convex functions using stochastic gradient descent(SGD) and mirror descent(MD) algorithms. These numerical results will be obtained through the implementation of practical software. In addition, we propose to analyze the average complexity of the SGD and MD algorithms. An interesting application is to estimate the efficiency of the MD algorithm developed by Gaujal and Mertikopoulos for solving stochastic SDPs. 

Selected 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.