Semidefinite programming approaches and software tools for quadratic programs with linear complementarity constraints

Dans le domaine de la théorie des jeux, il est intéressant de créer un équilibre dynamique entre les agents afin qu'ils s'influencent de façon asymétrique. Le meneur affecte les règles du jeu, mais les choix subséquents du suiveur affectent la valeur de l'objectif du meneur. La dynamique meneur-suiveur est un outil puissant permettant de décrire un grand nombre de scénarios de jeux dans un contexte réel. Toutefois, les problèmes d'équilibre demeurent difficiles en pratique sauf pour quelques types de problèmes largement étudiés en théorie tel le problème linéaire bi-niveau. Cette thèse tente de déterminer si les relaxations sous la forme de problèmes semi-définis, problèmes quadratiques avec contraintes de complémentarité linéaires sont efficaces. Cette classe de problème est équivalente aux problèmes d'équilibre. Une fonction objectif quadratique est particulièrement intéressante car la littérature dans ce domaine n'est pas complète et les relaxations semi-définies sont souvent efficaces pour les problèmes avec des fonctions objectif et/ou des contraintes quadratiques non-convexes. Nous présentons une relaxation de base qui n'est pas coûteuse en temps de calcul puis nous discutons d'un grand nombre de contraintes qui permettent de resserrer la relaxation de façon significative. L'évaluation de l'efficacité de la relaxation, lorsque toutes ces contraintes sont utilisées, montre que cela mène à des difficultés d'implémentation numériques pour le solveur de points intérieurs qui résout le problème semi-défini. Nous discutons des raisons expliquant cela puis nous utilisons une autre approche afin d'éliminer cette difficulté. Cet algorithme démarre avec la relaxation de base renforcée avec une seule contrainte d'égalité agrégée puis ajoute de façon itérative des coupes resserrant la relaxation. Éventuellement, la relaxation est renforcée à son maximum alors que seule une fraction des coupes a été ajoutée. Les résultats numériques montrent que cette approche ne permet pas d'améliorer les bornes du problème semi-défini lorsque des coupes sont ajoutées. Ce n'est pas une faiblesse de la méthode mais cela démontre que le modèle de base est déjà une relaxation forte. Ainsi, l'aggrégation des contraintes en une seule contrainte d'égalité est très efficace pour renforcer la relaxation et ajoute peu de difficulté à son implémentation en pratique. Des recommandations sont émises concernant le choix des paramètres pour la méthode d'ajout de coupes de façon itérative. Les relaxations semi-définies sont surtout utilisées pour borner les problèmes quadratiques difficiles. Les relaxations SDP des problèmes QPLCC peuvent être utilisées de cette façon, pour borner les noeuds des arbres branch and bound, mais nous sommes intéressés à utiliser toute l'information contenue dans la matrice de solution X∗ du problème SDP. Lorsque cette matrice est de rang 1, elle peut être utilisée pour retrouver la solution globale dans l'espace d'état du problème original non-relaxé. Nous définissons un point candidat comme étant un point estimant la solution globale d'un problème et nous présentons 4 façons de retrouver une solution dans l'espace d'état original pour une matrice X∗ de rang arbitraire, X∗ étant la solution de la relaxation SDP. Ce point candidat n'est pas spécifique aux problèmes QPLCC et pourrait être appliqué à d'autres problèmes. Des résultats numériques sont effectués afin de montrer que les points candidats sont des estimateurs de la solution globale. Nous présentons aussi des procédures afin d'utiliser les capacités de "warmstart" des solveurs en utilisant ce point candidat et démontrons leur impact. En plus de contribuer à l'avancement des connaissances des problèmes QPLCC, nous avons aussi contribué à la communauté de recherche des logiciels traitant ces problèmes. Nous avons choisi Python comme langage de programmation puisque plusieurs librairies sont disponibles pour l'optimisation convexe, mais aussi pour sa capacité à interagir avec des solveurs externes codés dans d'autres langages de programmation. Nous avons créé des outils pour les problèmes QPLCC, par exemple en les formulant en langage AMPL et GAMS, nous avons résolu les QPLCC et/ou les problèmes SDP en utilisant des solveurs Pytyon, des solveurs installés localement ou la librairie NEOS. Tous les résultats numériques présentés dans cette thèse ont été effectués avec les librairies présentées dans cette thèse. Nous espérons que d'autres chercheurs dans le domaine QLPCC utiliserons nos librairies pour construire leurs propres méthodes de résolution et pour simplifier les comparaisons avec d'autres solveurs.