Séminaires 2018-2019

A+ A- Aa
Partager cette page :
Le séminaire du Laboratoire du LAMPS a lieu le Jeudi à 11h15 (en moyenne tous les 15 jours)
généralement en salle de réunion (bât. B2)

Pour toutes informations ou inscriptions : Robert Brouzet

Mardi 12 mars 2019 à 14h00
EXCEPTIONNELLEMENT Bât E - SALLE E1
Jean-Noël Corvellec
LAMPS, Université de Perpignan Via Domitia, France
Titre : Une contribution à la conjecture de Reich (en collaboration avec Dominique Azé)

Résumé : Soit (X,d) un espace métrique complet et T X x X  une application multivoque à valeurs non vides,
telle que pour x ≠y :
dH (Tx, Ty) ≤ κ(d(x, y)) d(x, y),

où κ : ]0, +[⟶ [0; 1[ satisfait :

lim sup κ(t) < 1   pour tout s > 0.

                         t s+


En 1969, Boyd et Wong ont montré que dans le cas univoque, T possède un point fixe, un résultat étendu en 1972 par Reich au cas où est T à valeurs compactes. En 1974, Reich a demandé : qu'en est-il, dans le cas où T est à valeurs fermées, bornées ? C'est la "Conjecture de Reich" qui a donné lieu à diverses réponses partielles, sous des hypothèses supplémentaires sur κ. En utilisant des arguments variationnels simples et directs, nous donnons une telle réponse partielle, qui contient tous les résultats antérieurs, dans le cas où près de 0, κ est  décroissante et 1/(1 κ) est sommable.

Jeudi 28 mars 2019 à 11h15
Stéphane Gaubert
CMAP, Ecole Polytechnique, Palaiseau, France
Titre : Nonarchimedean Convex Programming and Its Relation to Mean-Payoff Games

Résumé : Linear programming, and more generally convex semialgebraic programming, makes sense over any ordered nonarchimedean field, like a field of real Puiseux series. Nonarchimedean instances encode classical parametric instances of convex programs with a suitably large parameter. Tropical geometry allows one to study such instances by combinatorial means. In particular, it reveals that, under a genericity condition, solving a nonarchimedean feasibility problem is equivalent to deciding who the winner is in a mean payoff game. Indeed, nonarchimedean linear programs correspond to deterministic mean payoff games, whereas nonarchimedean semidefinite programs correspond to perfect information stochastic mean payoff games. In this way, one can apply methods from convex programming to mean payoff games, and vice versa. We will present here the main ideas and tools from tropical geometry developed in this approach, and illustrate them by two results: a counter example, with a family of linear programs, with large coefficients, for which log-barrier interior point methods have a non strongly polynomial behavior (they make a number of iterations exponential in the number of constraints and variables); a theorem transferring complexity results concerning pivoting methods in linear programming to mean payoff games.
This is based on a series of works with Allamigeon, Benchimol and Joswig, concerning the tropicalization of the central path and of pivoting methods, and with Allamigeon and Skomra, for the tropicalization of semidefinite programming.

Partager cette page :

Mise à jour le 9 mars 2019