[Proposition de thèse 2023] Convexité combinatoire, ses généralisations et applications à l’optimisation

Convexité combinatoire, ses généralisations et applications à l’optimisation  [ PDF]

Encadrant : 
Xavier Goaoc 

Equipe : 
Gamble, laboratoire LORIA et centre INRIA Nancy Grand Est.

Contexte : 

L’objectif général de cette thèse est de contribuer au développement de la convexité combinatoire, de ses généralisations topologiques et de ses applications à l’optimisation (convexe ou pas).
Les théorèmes de Carathéodory, Helly et Radon ont ouvert le champs à une théorie combinatoire de la convexité, parfois appelée convexité combinatoire, qui explore les motifs d’intersections des familles de convexes, avec une attention particulière pour les systèmes d’enveloppes convexes de sous-ensemble d’un ensemble fini de points. Parmi les résultats remarquables de ce thème, citons le théorème de Helly fractionnaire de Kalai et le théorème (p,q) d’Alon et Kleitman. Voir par exemple les livres de cours [Mat02, Bár21] ou l’introduction [BGJ+20 BGJ+20, §5].
Une manière classique d’étendre la convexité combinatoire consiste à relaxer l’hypothèse de convexité en une condition plus topologique. On peut pour cela identifier une propriété topologique des ensembles convexes (par exemple le fait qu’ils forment une good cover). Une alternative consiste à interpréter les systèmes d’enveloppes convexes comme l’image d’un complexe simplicial par l’application linéaire envoyant les sommets sur un ensemble de points donné; autoriser l’application à n’être que continue permet alors d’élargir le champs. Ces deux points de vue relient naturellement la convexité combinatoire à des résultats classiques de topologie algébrique (théorèmes du nerf ou de Borsuk-Ulam par exemple). Un développement récent dans cette axe est l’utilisation de la notion de mineurs homologiques pour étudier les systèmes d’ensembles de complexité topologique bornée [GHP21, GPP+17 GPP+17, Pat20].
L’optimisation convexe offre des applications naturelles à la convexité combinatoire, qui permet d’analyser, expliquer, unifier ou généraliser divers algorithmes ou problèmes. Par exemple, les principes de pivot dans les algorithmes du simplexe (pour la programmation linéaire) et de Lemke-Howson (pour les problèmes de complémentarité linéaire) découlent tous deux du théorème de Carathéodory. Un autre exemple est la borne sur la taille des bases en programmation linéaire et en chance constrained optimization, que l’on peut relier au théorème de Helly, donnant lieu à la classe de problèmes de type LP. Ces exemples, et d’autres, sont détaillés dans l’article de synthèse [DLGMM19].

Travail prévu :

Les résultats les plus avancés de convexité combinatoire, par exemple le théorème de Helly fractionnaire ou le théorème (p,q), ont pour l’instant peu d’applications en optimisation. Une première tâche consistera à rechercher de telles applications. Une piste concrète est donnée par les problèmes de k-adaptabilité, qui demandent par exemple, étant donné un programme linéaire paramétré, de déterminer k solutions de sorte 1que pour toutes valeurs des paramètres au moins l’une de ces solutions est faisable (voire optimale). Est-ce que la convexité combinatoire peut garantir ou aider à déterminer l’existence d’une solution? Le thème de l’optimisation robuste, et notamment le chance constrained optimization, est ouvre lui aussi de nombreuses questions intéressantes. Étudier ces problème aidera à identifier des questions algorithmiques pertinentes en convexité combinatoire; par exemple, avec quelle efficacité peut-on déterminer si une famille de convexes donnée satisfait l’hypothèse du théorème (p,q)– parmi tous p convexes, il y en a q qui se coupent? L’utilisation conjointe de mineurs homologiques et de théorie de Ramsey a permis d’établir qu’une grande partie de la convexité combinatoire se généralise aux familles d’ensemble de complexité topologique bornée (au sens où l’intersection de toute sous-famille a des nombres de Betti bornés). Ces résultats majorent généralement les paramètres (par exemple les nombres de Helly et de Radon) par des constantes “galactiques” du fait de l’utilisation de théorie de Ramsey. Il sera aussi intéressant de revisiter cet ensemble de travaux afin d’obtenir des bornes raisonnables. Cela requiert d’identifier les questions combinatoires initialement écrasées à coups de théorie de Ramsey et de les analyser plus précisément. Une autre tâche importante est l’étude de familles d’ensembles de complexité topologique croissant au plus polynomialement; l’idée qu’une partie de la convexité combinatoire puisse s’étendre à de telles familles a été proposée il y a une vingtaine d’anné par Kalai et Meshulam [Kal04] dans une série de conjectures qui esquissent une théory de la dimension de Vapnik-Chervonenkis homologique. Ces deux tâches conduisent naturellement à une troisième consistant à généraliser les méthodes d’optimisation à des familles d’ensembles qui ne sont pas convexes, mais satisfont des conditions topologiques. Un exemple naturel de telles familles est données par les transversales géométriques.

Pré-requis

— Master en informatique ou en mathématiques. Aisance en Français ou en Anglais.
— Unintérêt pour l’articulation entre informatique et mathématiques.
— Des connaissances solides dans un domaine tel que la géométrie algorithmique et combinatoire, l’algorithmique, la théorie de la complexité, la topologie, l’algèbre, … sont un plus.

Références

[Bár21] Imre Bárány. Combinatorial convexity, volume 77. American Mathematical Soc., 2021.
[BGJ+20] Marthe Bonamy, Xavier Goaoc, Fredrik Johansson, Jérôme Leroux, Marni Mishna, Irena Penev, and Sylvain Schmitz. Informatique Mathématique Une photographie en 2020. 2020. https://www.gdr-im.fr/wp-content/uploads/2020/07/2020livre_im.pdf.
[DLGMM19]  Jesús De Loera, Xavier Goaoc, Frédéric Meunier, and Nabil Mustafa. The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg. Bulletin of the American Mathematical Society, 56(3) :415–511, 2019.
[GHP21]  Xavier Goaoc, Andreas F. Holmsen, and Zuzana Patáková. A Stepping-Up Lemma for Topological Set Systems. In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40 :1–40 :17, 2021.
[GPP+17] Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Bounding Helly numbers via Betti numbers. A Journey Through Discrete Mathematics : A Tribute to Jiří Matoušek, pages 407447, 2017.
[Kal04] G. Kalai. Combinatorial expectations from commutative algebra. In I. Peeva and V. Welker, editors, Combinatorial Commutative Algebra, volume 1(3), pages 1729–1734. Oberwolfach Reports, 2004.
[Mat02] Jiri Matousek. Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2002.
[Pat20]    Zuzana Patáková. Bounding Radon Number via Betti Numbers. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61 :1–61 :13, 2020. 2