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.

Abstract

This thesis explores various aspects of optimization and its applications in solving complex problems in operations research and machine learning. By blending moment-based methods with combinatorial optimization techniques from machine learning, we uncover fresh theoretical insights and develop improved algorithms. The work is organized around three key contributions, each addressing a significant challenge in the field and offering practical, mathematically grounded solutions. The first contribution examines alternative formulations of the maximum independent set problem as a polynomial optimization problem. This well-known NP-hard problem in graph theory has important applications in network design, scheduling, and resource allocation. The central challenge is to identify the largest subset of non-adjacent vertices in a graph; a task that becomes increasingly difficult as the graph grows. Since the problem can be expressed in several equivalent polynomial forms, each formulation can be tackled using the Lasserre hierarchy of semidefinite relaxations. Our study systematically investigates how the choice of formulation influences the quality of the resulting bounds. Extensive experiments reveal that certain formulations yield much stronger bounds than others. We also provide theoretical insights into how the structure of a given polynomial formulation affects the efficiency of the relaxation process, offering valuable guidance for selecting better formulations for combinatorial problems. This study resulted in the publication of the article ”A Note on the Lasserre Hierarchy for Different Formulations of the Maximum Independent Set Problem” in Optimization Letters, 2021. The second contribution is focused on enhancing the interpretability of boosted tree ensemble models, which are widely used in machine learning for structured data in domains such as finance, healthcare, and risk assessment. These models, which aggregate multiple weak learners (typically decision trees), are celebrated for their high accuracy and robustness. However, their complexity can make them hard to interpret, which is a serious drawback in situations where understanding the decision-making process is crucial. To tackle this issue, we introduce an optimization-based pruning technique designed to reduce model size while preserving predictive performance. By formulating pruning as an exact optimization problem and employing an iterative adversarial strategy, we are able to significantly reduce the complexity of these models without sacrificing accuracy. Our experiments demonstrate that this method can greatly simplify the model, making it far easier for practitioners to interpret the results without losing any predictive power. This work has been accepted for publication in the AAAI Conference on Artificial Intelligence, 2025, under the title ”Free Lunch in the Forest: Functionally Identical Pruning of Tree Ensembles”. The final contribution presents an improved version of the primal simplex algorithm, a fundamental tool in linear programming used to solve optimization problems efficiently. Although the improved primal simplex method mitigates some degeneracy issues inherent in the classical algorithm, it can still underperform in non-degenerate cases, resulting in inefficiencies for large-scale problems. To address this, we propose a refined formulation of the auxiliary subproblem that guarantees substantial improvements in the objective function at every iteration until an �-approximate optimal solution is reached. Our theoretical analysis confirms that the number of descent directions remains polynomial, making our approach significantly more scalable than the classical improved primal simplex method. This more robust and efficient strategy has the potential to boost the performance of linear programming solvers in both research and industrial applications. This work is currently under review for publication in the Journal of Optimization Theory and Applications, 2025.