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.

Abstract

The leader follower dynamic seen in bilevel programming and equilibrium problems has the potential to unlock new doors in economic modeling and enable the realistic modeling of many problems of keen interest. The leader's choices affect the rules of the game which is played by the follower, but the follower's subsequent choices also impact the objective value achieved by the leader. Conceptually, the leader-follower dynamic is a valuable tool for describing any number of competitive real-world scenarios. However, to date equilibrium problems remain difficult in practice except for a handful of well studied problem classes such as the linear linear bilevel program. This thesis is concerned with how effective semidefinite programming (SDP) relaxations can be constructed for quadratic programs with linear complementarity constraints (QPLCCs), a problem class which can equivalently model a class of equilibrium problems. The case of a general quadratic objective function is of particular interest since the literature in this area has not yet reached full maturity, and since semidefinite programming relaxations have often been effective for problems with nonconvex quadratic objective functions and constraints. We present a base relaxation which is relatively computationally inexpensive, and then we present and discuss a number of tightening constraints which can have a dramatic tightening effect. How- ever, in evaluating the effectiveness of the relaxation when all such constraints are used, we observe that blindly imposing all tightening constraints of the proposed types often leads to numerical difficulties for the interior point solver solving the semidefinite program. We discuss a possible reason for this, and finally we counteract it by developing an algorithm which begins with a middle ground model (the base relaxation strengthened with a single aggregated equality constraint) and iteratively adds tightening constraints to eventually obtain the tightness of the full relaxation while using a small fraction of the constraint pool in practice. In testing the iterative method with the middle ground model, we find that the SDP bound often doesn't improve over the course of the iterative method. This is not a flaw of the cut finding procedure, but instead demonstrates that the middle ground model is already as tight as the fully constrained model for these problems, establishing the aggregated equality constraint as an extremely effective strengthening measure which adds very little additional computational difficulty to the problem. Recommendations are made regarding parameter choice for the iterative method. Semidefinite relaxations are most commonly used to bound difficult quadratic problems. SDP relaxations of QPLCCs can certainly be used this way, to bound nodes of a branch and bound tree, but we are also interested in using the information contained in the SDP solution matrix X∗ to full advantage. SDP relaxations are commonly designed so that an SDP solution X∗ which is rank one can be mapped back to the space of the unrelaxed problem to give a global solution. We define the notion of a candidate point as a point which is intended to estimate a problem's global solution, and we present four ways a candidate point for an SDP relaxation solution X∗ of arbitrary rank can be mapped back to the space of the original problem. The candidate point concept and definitions are not specific to the QPLCC and could be applied to other problems. We perform computational tests to support discussion of the different candidate points' suitability as an estimate of the problem's global solution. We also present procedures for assisting local or global solvers by warmstarting with the candidate point, and demonstrate the impact in both cases. In addition to contributing to the state of knowledge for QPLCCs, it has also been our goal to contribute software to the research community working on these problems. We have chosen Python as our development language based on the existence of a number of good packages for numerical work generally and convex optimization specifically, and also based on its abilities to act as glue between other services such as external solvers in other languages. We have made tools for modeling QPLCCs, exporting them for other languages (AMPL, GAMS), formulating SDP relaxations, and solving QPLCCs and/or SDP problems using native Python solvers, locally installed languages/solvers, or the NEOS public server. All the computational work presented in this thesis has been executed using the packages presented in this paper. It is our hope that other researchers in the field of QPLCCs will use our packages to build their own solution methods and to simplify the process of testing against various solvers.