Stéphane Gaubert – Mathematics and Decision

$\begin{quote} \begin{center} \textbf{Nonnegative tensors, games of entropy, and geometric programming} \end{center} \medskip We show that the logarithm of the spectral radius of a nonnegative tensor can be represented as the value of a stochastic control problem, in which one player maximizes a relative entropy. This is related to generalizations of inequalities of Donsker-Varadhan, Friedland-Karlin, and Karlin-Ost. Then, computing the spectral radius of a nonnegative tensor turns out to be a special case of a general geometric programming problem, consisting in minimizing the maximum of finitely many log-Laplace transforms of nonnegative measures with finite supports. We show that an approximate solution of this problem can be obtained in polynomial time in the bit-model of computation, the complexity being controlled by a condition number depending on the geometry of the support sets. This entails the polynomial-time approximability of the spectral radius. We also discuss another application, to the class of entropy games, in which two players wish to maximize or minimize a topological entropy. The results on geometric programming and nonnegative tensors are from a joint work with Shmuel Friedland. The application to entropy games is from a joint work with Marianne Akian, Julien Grand-Clément and Jérémie Guillaud. \end{quote}$