Traitement de la dégénérescence en optimisation non linéaire

This thesis is dedicated to solving two classes of degenerate nonlinear programming problems. In chapter 3 of the thesis, we propose an interior-point algorithm based on an elastic formulation of the ℓ1 penalty merit function to solve mathematical problems with complementarity constraints (MPCC). The salient feature of our method is that it requires no prior knowledge of which constraints, if any, are complementarity constraints. Remarkably, the method allows for a unified treatment of both general, unstructured, degenerate problems and structured degenerate problems, such as problems with complementarity constraints, with no changes to accommodate one class or the other. Our results refine those of Gould et al. (2010) by isolating the degeneracy due to the complementarity constraints. The method naturally converges to a strongly stationary point or delivers a relevant certificate of degeneracy without recourse to second-order intermediate solutions. Preliminary numerical results on a standard test set illustrate the flexibility of the approach. Another type of degeneracy of interest is the lack of strict complementarity for nonlinear problems. We show in chapter 4 that when the strict complementarity condition fails to hold at a local solution, an appropriate and cheap scaling of the Lagrange multipliers estimates allows to recover superlinear convergence in interior-point methods. Finally, in chapter 5 of the thesis, we collect a set of weakly-active problems and present a benchmark against others interior-point algorithms such as IPOPT2 (Fortran version )(Wächter et Biegler, 2006), KNITRO (Waltz et Plantenga, 2006) and LOQO (Vanderbei,2008). Our approach was implemented as a modification of IPOPT2.

Résumé

L'objet de cette thèse est l'etude de deux types de dégénérescence en optimisation non linéaire. Dans le chapitre 3 de la thèse, nous proposons un algorithme de points intérieurs et de région de confiance pour résoudre une reformulation élastique de la pénalisation exacte ℓ1 des problèmes mathématiques avec contraintes de complémentarité(MPCC). La nouveauté avec notre approche est qu'il n'est pas nécessaire de connaître à l'avance quelles contraintes sont de complémentarité. La force de notre approche est qu'elle traite de la même manière les problèmes dégénérés structurés que sont les MPCC et les problèmes dégénérés généraux. Notre approche adapte celle de Gould et al. (2010) aux MPCC en isolant la dégénérésence due aux contraintes de complémentarité. L'algorithme converge vers des points fortement stationnaires ou délivre le cas échéant un certificat de dégénérescence sans recourir à une condition du second ordre. Des résultats numériques préliminaires sur une collection de problèmes MPCC standard illustrent la flexibilité de l'approche. Un autre type de dégénérescence qui nous intéresse est le manque de la complémentarité stricte en optimisation non linéaire. Nous définissons au chapiter 4 une mise à jour appropriée et peu onéreuse des multiplicateurs de Lagrange associés à des contraintes faiblement actives afin de recouvrer la convergence superlinéaire des itérés pour des méthodes de points intérieurs. Enfin dans le chapitre 5, nous assemblons une collection de problèmes ayant des contraintes non strictement complémentaires. Un banc d'essais entre les solveurs de points intérieurs IPOPT2 (version en Fortran) (Wächter et Biegler, 2006), KNITRO (Waltz et Plantenga, 2006) et LOQO (Vanderbei, 2008) permet de comparer leur performance sur la collection de problèmes faiblement actifs. Notre approche de mise à jour duale est implémentée dans IPOPT2.