Treatment of Degeneracy in Linear and Quadratic Programming

Dans cette thèse, nous considérons la résolution de problèmes d'optimisation quadratique dégénérés sur base de techniques initialement développées pour l'optimisation linéaire, ca-pables de tirer avantage de la dégénérescence. Nous commençons par améliorer l'efficacité de la règle de pivotage positive edge en fournissant une implémentation basée sur le logiciel libre CLP. Nous proposons ensuite le logiciel de haut niveau CyLP permettant de définir et d'expérimenter facilement avec de nouvelles règles de pivotage pour la méthode du Simplexe. CyLP offre de plus des services de modélisation puissants réduisant l'effort nécessaire à la modélisation de problèmes linéaires, en variables entières et quadratiques. À l'aide de CyLP, nous appliquons la règle positive edge à la variante du Simplexe suggérée par Wolfe pour résoudre les problèmes quadratiques. Nous incorporons également positive edge dans une méthode de gradient réduit. Nos tests démontrent l'efficacité de positive edge sur les problèmes quadratiques pour lesquels le terme linéaire est dominant. Chaque méthode est capable de fournir des niveaux substantiels d'accélération sur un certain sous-ensemble de problèmes lorsqu'elle est équipée de positive edge. Nous suggérons des pistes de recherche pour la conception de nouvelles méthodes qui incorporent positive edge et accélèrent la résolution sur une plus large gamme de problèmes.

Abstract

We consider solving degenerate quadratic programs (QPs) by means of degeneracy-benefiting techniques designed for linear programs (LPs). Specifically, we use a Simplex pivot method, called positive edge, that is able to take advantage of degeneracy in LPs. First, we improve the efficiency of the positive edge method by providing an internal implementation of it using CLP—an open-source LP solver. In the next stage, we develop a software, called CyLP, which allows easy definition of, and experimentation with, Simplex pivot rules. In addition, CyLP has a powerful modeling facility that reduces the effort of modeling LPs, mixed-integer programs (MIPs), and QPs. Using CyLP, we apply the positive edge rule to Wolfe's method—a Simplex-like method for QPs. We also incorporate positive edge into a reduced-gradient method. Our experiments demonstrate the effectiveness of positive edge on QPs with relatively large linear terms. Each method is able to yield substantial improvements on a subset of test problems. We provide research leads to devise novel methods that incorporate the positive edge rule and are more generally applicable.