Workshop MAC

Friday 22 January 2021, LAAS-CNRS, Toulouse

Scope

The workshop, organized by Didier Henrion, Mateusz Skomra and Sophie Tarbouriech, aims at introducing research topics at the crossroads between control, optimization, games and computer algebra.

Date and venue

The workshop takes place on Friday 22 January 2021, in Salle du Conseil of LAAS-CNRS, 7 avenue du colonel Roche, 31400 Toulouse.

Schedule

  • 9:30-10:15 - Marianne Akian, INRIA and Ecole Polytechnique, Palaiseau

    Tropical methods for solving stochastic control problems

    Monotone discretizations of Hamilton-Jacobi-Bellman equations lead to the dynamic programming equation of a multi-stage stochastic optimization problem. We develop several lower complexity numerical algorithms for solving such equations by combining tropical or max-plus method, numerical probabilistic approach, and stochastic dual dynamic programming method. This talk is based on joint works with Jean-Philippe Chancelier, Benoit Tran and Eric Fodjo. See in particular arXiv:1709.09049, arXiv:1810.12870, arXiv:2010.10619.

  • 10:30-11:15 - Nathanaël Fijalkow, LaBRI-CNRS, Univ. Bordeaux

    Population protocols and probabilistic automata as linear dynamical systems

    In this talk I will discuss two a priori different problems related to linear dynamical systems. The first is a well-known model for distributed systems and the second an important notion in program verification. I will show an unexpected connection between the two models, and present our current understanding for these problems, and conclude with a conjecture tying the two problems together.

  • 11:30-12:15 - Simone Naldi, Univ. Limoges

    On the complexity of semidefinite and hyperbolic programming

    Semidefinite programming (SDP) can be seen as a special case of a more general conic optimization problem called hyperbolic programming (HP). Although by construction HP is less explicit than SDP, the question whether there is a difference between these two classes is still an open problem in the theory of hyperbolic polynomials (and it is conjectured that this is not the case). I will make an overview of some known results, mostly concerning complexity questions around SDP and HP and concerning the problem of computing determinantal representations.