Contributions méthodologiques en optimisation pour le calcul de mesures d'ensembles, réduction d'arbres décisionnels et programmation linéaire

Cette thèse explore divers aspects de l’optimisation et ses applications à la résolution de problèmes complexes en recherche opérationnelle et en apprentissage automatique. En combinant des méthodes basées sur les moments avec des techniques d’optimisation combinatoire issues de l’apprentissage automatique, nous mettons en lumière de nouveaux résultats théoriques et développons des algorithmes améliorés. Le travail est structuré autour de trois contributions principales, chacune abordant un défi important du domaine et proposant des solutions concrètes, rigoureusement fondées sur des principes mathématiques. La première contribution étudie des formulations polynomiales alternatives du problème du plus grand sous-ensemble stable d’un graphe comme un problème d’optimisation polynomiale. Ce problème classique de la théorie des graphes, connu pour sa complexité NP-difficile, a des applications importantes en conception de réseaux, en ordonnancement et en allocation de ressources. Le défi consiste à identifier le plus grand sous-ensemble de sommets non adjacents dans un graphe, tâche qui devient de plus en plus difficile à mesure que la taille du graphe augmente. Étant donné que le problème peut être exprimé sous différentes formes polynomiales équivalentes, chaque formulation peut être traitée à l’aide de la hiérarchie de Lasserre des relaxations semi-définies. Notre étude examine systématiquement comment le choix de la formulation influence la qualité des bornes obtenues. Des expériences approfondies révèlent que certaines formulations produisent des bornes nettement plus serrées que d’autres. Nous apportons également un éclairage théorique sur la manière dont la structure d’une formulation polynomiale donnée affecte l’efficacité du processus de relaxation, offrant ainsi des indications précieuses pour choisir les meilleures formulations dans les problèmes combinatoires. Cette étude a donné lieu à la publication de l’article « A Note on the Lasserre Hierarchy for Different Formulations of the Maximum Independent Set Problem » dans Optimization Letters, 2021. La deuxième contribution se concentre sur l’amélioration de l’interprétabilité des modèles d’ensemble d’arbres boostés, largement utilisés en apprentissage automatique sur des données structurées dans des domaines tels que la finance, la santé et l’évaluation des risques. Ces modèles, qui agrègent plusieurs apprenants faibles (généralement des arbres de décision), sont réputés pour leur grande précision et leur robustesse. Toutefois, leur complexité rend leur interprétation difficile, ce qui constitue un inconvénient majeur dans les contextes où la compréhension du processus décisionnel est essentielle. Pour remédier à cela, nous introduisons une technique de réduction de modèle (pruning) fondée sur l’optimisation, visant à réduire la taille des modèles tout en maintenant leurs performances prédictives. En formulant cette tâche comme un problème d’optimisation exacte et en appliquant une stratégie itérative et adverse, nous parvenons à réduire considérablement la complexité des modèles sans perte de précision. Nos expériences démontrent que cette méthode permet de simplifier fortement le modèle, facilitant ainsi son interprétation sans compromettre sa performance. Ce travail a été accepté pour publication à la Conférence AAAI sur l’intelligence artificielle, 2025, sous le titre « Free Lunch in the Forest : Functionally Identical Pruning of Tree Ensembles ». La dernière contribution présente une version améliorée de l’algorithme du simplexe primal, un outil fondamental en programmation linéaire pour résoudre efficacement des problèmes d’optimisation. Bien que cette version atténue certains problèmes de dégénérescence inhérents à l’algorithme classique, elle peut encore sous-performer dans les cas non dégénérés, ce qui engendre des inefficacités sur des problèmes de grande taille. Pour y remédier, nous proposons une formulation affinée du sous-problème auxiliaire qui garantit des améliorations substantielles de la fonction objectif à chaque itération, jusqu’à l’obtention d’une solution �-optimale. Notre analyse théorique confirme que le nombre de directions de descente reste polynomial, ce qui rend notre approche bien plus évolutive que l’algorithme classique du simplexe primal amélioré. Cette stratégie plus robuste et efficace a le potentiel d’accroître la performance des solveurs de programmation linéaire, aussi bien dans la recherche que dans les applications industrielles. Ce travail est actuellement en révision pour publication dans le Journal of Optimization Theory and Applications, 2025.