Soutenance mémoire
Méthode de lagrangien augmenté
La méthode de lagrangien augmenté, encore connue sous le nom de la méthode des multiplicateurs, a été proposée en 1969 indépendamment par Hestenes [82] et Powell [103] pour faire face aux difficultés dues au mauvais conditionnement associé à la méthode de pénalisation quadratique. La méthode de lagrangien augmenté consiste à résoudre, exactement ou approximativement, une suite de problèmes de minimisation sans contrainte de la forme min x∈Rn ψλ,σ(x). (1.1.4) Après chaque minimisation, le paramètre de pénalisation et le multiplicateur de Lagrange sont mis à jour en fonction de la réalisabilité des contraintes. Si la violation des contraintes est inférieure à une valeur cible, alors σ est maintenu fixe et une nouvelle valeur du multiplicateur de Lagrange λ+ est calculée par la formule suivante λ+ = λ + g(x) σ , où x est la solution de (1.1.4). Sinon, σ est diminué suffisamment et λ+ est maintenu constant afin d’éviter une mauvaise estimation du multiplicateur de Lagrange. Une autre méthode de mise à jour du multiplicateur de Lagrange consiste à le traiter comme une fonction en x plutôt que comme une variable séparée. Les propriétés théoriques et pratiques de cette approche ont été analysées par Bertsekas [21], Boggs et Tolle [25], Di Pillo et Grippo [49], Fletcher [58] et Glad et Polak [72]. Les principaux inconvénients de cette approche sont le coût de résolution de (1.1.5) et le fait que λ(x) n’est pas unique lorsque ∇g(x) n’est pas de plein rang. L’avantage de la méthode de lagrangien augmenté par rapport à celle de pénalisation quadratique est que le processus de minimisation sans contrainte (1.1.4) converge sans la nécessité de conduire le paramètre de pénalisation vers zéro. En effet, si x ∗ est un minimum local du problème initial (PE) et λ ∗ est le multiplicateur de Lagrange associé, alors x ∗ est un minimum local strict de x 7→ ψλ∗,σ(·) pour tout σ suffisamment petit (voir par exemple [99, Théorème 17.5]). Par conséquent, le mauvais conditionnement associé aux méthodes de pénalisation quadratique est évité. La méthode de lagrangien augmenté a été proposée à la fin des années 60 essentiellement pour résoudre les problèmes d’optimisation avec contraintes d’égalité. Au début des années 70, Rockafellar [105, 106] et Buys [30] ont étendu le lagrangien augmenté de Powell-Hestenes au cas des problèmes d’optimisation avec contraintes d’inégalité. Rockafellar a établi la convergence globale dans le cas convexe tandis que Buys a démontré la convergence locale dans le cas non convexe. En 1982, Di Pillo et Grippo [50] ont étendu leur travail [49] concernant les problèmes avec contraintes d’égalité pour résoudre ceux avec contraintes d’inégalité. Des résultats supplémentaires peuvent être trouvés dans [19, 20, 56]. Les propriétés de convergence locale des méthodes de lagrangien augmenté ont été discutées dans [21, 22, 24, 30, 73, 101]. Sous l’hypothèse que la valeur initiale du multiplicateur de Lagrange soit suffisamment proche du multiplicateur optimal, Buys [30] a montré la convergence linéaire de la méthode de lagrangien augmenté sans donner une estimation de ce taux de convergence linéaire. Bertsekas [22] a montré que ce dernier est inversement proportionnel au paramètre de pénalisation avec l’hypothèse que la suite des multiplicateurs de Lagrange générés par l’algorithme est bornée. Il a encore démontré que le taux de convergence devient superlinéaire lorsque le paramètre de pénalisation tend vers zéro. Il convient de noter que les résultats précédents sont basés sur l’hypothèse que le problème (1.1.4) est résolu exactement. Dans le cas où il est résolu approximativement, Bertsekas [18] a donné un exemple d’un critère d’arrêt pour lequel le taux de convergence linéaire ne peut pas être obtenu et afin de garantir la convergence globale, il est nécessaire que le paramètre de pénalisation converge vers zéro. Récemment, Polyak [102] a démontré la convergence quadratique locale d’une méthode de lagrangien augmenté primale-duale sous l’hypothèse des conditions d’optimalité de second ordre standards. Notons que cette analyse a été réalisée sans aucune stratégie de globalisation.
Itération interne
Lorsque le progrès dans la résolution des conditions (3.1.2) est insuffisant, une suite d’itérations internes est appliquée. Au cours de ces itérations, l’estimation du multiplicateur de Lagrange λ est fixée, le paramètre de pénalisation est autorisé à augmenter et une méthode de type Newton globalisée par une technique de recherche linéaire est appliquée au système (3.1.2) pour trouver wk+1 et σk+1 vérifiant (3.2.4). À chaque itération de cet algorithme, un système linéaire dont la structure est analogue à celle du (3.1.3) est résolu nous proposons d’augmenter la valeur du paramètre de pénalisation au cours des itérations internes. Cette procédure a été proposée dans le chapitre précédent et les tests numériques ont montré son efficacité. Elle peut être facilement étendue à ce cadre d’étude. Pour éviter que la suite des paramètres de pénalisation devienne non bornée, une valeur maximale admissible σ¯ ≤ sk est définie au début de chaque itération interne. Soit k l’indice de l’itération externe au cours de laquelle l’algorithme des itérations internes est appelé. Nous donnons maintenant un résultat concernant la décroissance de la fonction de mérite qui sera utile pour analyser la convergence globale des itérations internes. Ce résultat se démontre de la même manière que [11, Proposition 2].
Comparaison avec SPDOPT-QP
Notre motivation principale pour proposer une nouvelle méthode était d’améliorer celle présentée dans le chapitre précédent. C’est pourquoi, nous commençons par examiner les performances de SPDOPT-AL par rapport à SPDOPT-QP. Ce dernier a été appliqué en utilisant la règle de mise à jour (2.0.9) pour le paramètre de pénalisation. Pour mettre en evidence les avantages du taux de convergence quadratique, nous avons considéré deux choix des paramètres κ1 et κ2. Le premier choix est κ1 = 0.1 et κ2 = 1.8 et sera appelé SPDOPT-QP-1 (utilisé dans le chapitre 2). Le deuxième choix est κ1 = 0.2 et κ2 = 1.5 et sera appelé SPDOPT-QP-2. Comme prévu, SPDOPT-AL semble être plus efficace que SPDOPT-QP. Ceci revient au fait que SPDOPT-AL jouit d’une convergence quadratique alors que celle de SPDOPT-QP est au plus superlinéaire. Cet écart d’efficacité est plus remarquable en considérant le temps CPU. En effet, le taux d’efficacité de SPDOPT-AL est de l’ordre de 70% alors que celui des deux versions de SPDOPT-QP ne dépasse pas 25%. Il faut noter que ce profil a été obtenu en considérant seulement 38 problèmes. En fait, nous avons éliminé les problèmes pour lesquels le temps CPU du solveur le plus rapide est inférieur à 0.05 secondes car une petite différence au niveau des performances du système peut aboutir à une comparaison non objective. Pour justifier ce gain, nous avons comparé le nombre de factorisations 6 effectuées par le solveur . Le profil de performance correspondant au nombre de factorisations (et encore le nombre d’évaluation linéaire MA57 pour SPDOPT-AL et SPDOPT-QP pour résoudre les 38 problèmes. En effet, la factorisation de la matrice du système est la tâche la plus coûteuse en terme de temps CPU. Nous avons obtenu un profil de performance similaire à celui correspondant au temps CPU ce qui justifie la rapidité de SPDOPT-AL. Enfin, SPDOPT-AL semble être un peu plus robuste que SPDOPT-QP-2 et moins robuste que SPDOPT-QP-1. Ce dernier est capable de résoudre 105 problèmes. Alors que SPDOPT-AL et SPDOPT-QP-2 sont capables de résoudre respectivement 104 et 103 problèmes de la collection considérée. Le seul échec de SPDOPT-AL concerne le problème dixchlng. Cet échec est dû à une mauvaise estimation du multiplicateur de Lagrange associé aux contraintes d’égalité. La norme infinie de ce dernier dépasse. En re-exécutant SPDOPT-AL en autorisant la procédure de mise à l’échelle, ce problème est résolu après seulement 10 itérations et 12 évaluations de fonctions et de gradients. Parmi les 104 problèmes résolus avec succès, SPDOPT-AL a besoin de 1671 itérations, dont 1210 sont des itérations externes. Au cours de 76% de ces dernières, la condition (3.2.1) est satisfaite et par conséquent l’étape 2 a été exécutée et la mise à jour λk+1 = yk a été utilisée.
Conclusions
Dans cette thèse, nous avons proposé SPDOPT, un nouveau solveur basé sur les méthodes fortement primales-duales pour la résolution des problèmes d’optimisation non linéaire avec contraintes. SPDOPT est écrit en C, possède une interface à AMPL [63] et CUTEst [81] et utilise soit MA57 [53], soit MUMPS [3] pour la résolution du système linéaire. Notons que les meilleures performances sont obtenues avec le solveur linéaire MA. La première caractéristique de ce solveur par rapport à ceux déjà existants est que le contrôle des itérés s’effectue dans l’espace primal-dual tout au long du processus de la minimisation, d’où l’appellation méthodes fortement primales-duales. En particulier, la globalisation des algorithmes implémentés dans SPDOPT est effectuée par une méthode de recherche linéaire qui utilise une fonction de mérite primale-duale. La deuxième caractéristique est que SPDOPT introduit une régularisation naturelle du système linéaire utilisé à chaque itération pour calculer une direction de recherche ce qui permet à notre code de bien se comporter pour résoudre les problèmes dégénérés. Pour la résolution des problèmes d’optimisation avec contraintes d’égalité, SPDOPT offre la possibilité d’utiliser deux algorithmes primaux-duaux. Le premier algorithme, étudié dans le chapitre 2, consiste à appliquer une méthode de type Newton à une suite de systèmes d’optimalité perturbés qui découle naturellement de l’approche de pénalisation quadratique. Une caractéristique importante de l’algorithme est que le paramètre de pénalisation est autorisé à augmenter au cours des itérations internes ce qui permet d’éviter le mauvais conditionnement associé aux méthodes de pénalisation quadratique. La convergence globale des itérés vers la solution a été établie. Un résultat de convergence superlinéaire asymptotique a été démontré. Nous avons réalisé des expériences numériques sur un ensemble de 109 problèmes provenant des librairies COPS et CUTEr. Les résultats obtenus montrent que SPDOPT est aussi efficace que IPOPT pour la résolution des problèmes d’optimisation réguliers et beaucoup plus robuste pour la résolution des problèmes dégénérés. Suite à quelques observations liées au comportement du terme de perturbation des contraintes d’égalité et dans le but d’améliorer le taux de convergence de la méthode, nous avons proposé dans le chapitre 3 un nouvel algorithme de lagrangien augmenté dans le contexte primal-dual. Un aspect important de cette approche est qu’avec un bon choix des règles de mise à jour des paramètres, l’algorithme se réduit asymptotiquement à une méthode de Newton régularisée appliquée aux conditions d’optimalité du problème initial. Par conséquent, un taux de convergence quadratique a été démontré. Afin d’évaluer les performances de cet algorithme, nous l’avons comparé à la méthode développée dans le chapitre 2. Les résultats obtenus confirment les résultats théoriques établis et montrent que la méthode proposée a de meilleures performances. Nous avons aussi comparé cette méthode à deux solveurs bien établis basés sur la méthode de lagrangien augmenté, ALGENCAN et LANCELOT-A. Cette comparison montre que l’algorithme proposé est très efficace et robuste. Dans le chapitre 4, nous avons considéré une extension de la méthode du chapitre 3 pour résoudre les problèmes avec contraintes d’égalité et d’inégalité. La méthode proposée est basée sur une méthode Newtonienne appliquée à une suite de systèmes de conditions d’optimalité perturbées. Ces systèmes découlent d’une reformulation du problème initial sous la forme d’une suite de problèmes de pénalisation, en introduisant un lagrangien augmenté pour traiter les contraintes d’égalité et une fonction barrière logarithmique classique pour les inégalités. Notons que notre algorithme introduit une perturbation des contraintes d’égalité ainsi que les conditions de complémentarité. La convergence globale et asymptotique de la méthode proposée a été démontrée sous des hypothèses standards. En particulier, nous avons montré que le taux de convergence de la suite des itérés primaux-duaux vers la solution est superlinéaire et que les itérés sont asymptotiquement tangents au chemin central. Nous avons effectué une étude numérique détaillée de l’algorithme proposé. Dans cette étude, nous avons présenté en premier temps l’impact du choix du paramètre barrière et du point de départ des itérations internes sur les performances de SPDOPT. Ceci nous a permis de fixer les choix par défaut adoptés par SPDOPT pour ces paramètres. Nous avons ensuite présenté le comportement du code sur l’exemple de Wächter Biegler. Les expériences numériques incluent aussi des comparaisons de SPDOPT avec des solveurs bien établis qui sont IPOPT, ALGENCAN, LANCELOT-A et LANCELOT-B sur une large collection de problèmes dont la dimension est 976. Les résultats numériques montrent que SPDOPT a un comportement très compétitif à IPOPT en teme d’efficacité et robustesse sur les problèmes de petites tailles provenant de la collection Hock et Schittkowski. Pour les 509 problèmes de CUTEst, les performances de SPDOPT en terme d’efficacité sont globalement meilleures que celles de ALGENCAN et LANCELOT-B et moins bonnes que celle de IPOPT. Ces résultats mettent l’accent sur un “mauvais” traitement des contraintes d’inégalité au cours des itérations internes pour un pourcentage important des problèmes ce qui aboutit à une perte en robustesse. Des pistes de recherches pour améliorer la robustesse de SPDOPT sont décrites ci-dessous. Une dernière comparaison montre que SPDOPT se compare très bien aux trois codes sur deux collections de problèmes dégénérés.
|
Table des matières
1 Introduction
1.1 État de l’art
1.1.1 Méthode de pénalisation quadratique
1.1.2 Méthode de lagrangien augmenté
1.1.3 Méthodes de points intérieurs
1.1.4 Méthode de programmation quadratique successive
1.2 Objectifs et contenu de la thèse
1.3 Notations, définitions et résultats utiles
2 Une méthode de pénalisation quadratique primale-duale pour l’optimisation avec contraintes d’égalité
3 Une méthode de lagrangien augmenté primale-duale pour l’optimisation avec contraintes d’égalité
3.1 Introduction et motivation
3.2 Description de l’algorithme
3.2.1 Itération externe
3.2.2 Itération interne
3.3 Analyse de convergence globale
3.3.1 Itérations internes
3.3.2 Itérations externes
3.4 Convergence asymptotique
3.5 Détails de l’implémentation
3.6 Résultats numériques
3.6.1 Comparaison avec SPDOPT-QP
3.6.2 Comparaison avec d’autres méthodes de lagrangien augmenté
3.7 Conclusion
4 Une méthode de lagrangien augmenté et de points intérieurs primale duale pour l’optimisation non linéaire
4.1 Introduction
4.1.1 Schéma général de l’algorithme
4.2 Description de l’algorithme
4.2.1 Itération externe
4.2.2 Itération interne
4.3 Analyse de convergence globale
4.3.1 Itérations internes
4.3.2 Itérations externes
4.4 Convergence asymptotique
4.4.1 Hypothèses et résultats préliminaires
4.4.2 Résultats asymptotiques
4.5 Implémentation
4.6 Résultats numériques
4.6.1 Stratégies de réduction de µ
4.6.2 Points de départ des itérations internes
4.6.3 Exemple de Wächter et Biegler
4.6.4 Collection de Hock et Schittkowski
4.6.5 Collection de CUTEst
4.6.6 Collection de problèmes dégénérés
4.7 Conclusion
5 Conclusions et perspectives
A Liste des problèmes testés
B Résultats numériques de SPDOPT
C Résultats numériques de IPOPT
D Résultats numériques de ALGENCAN
E Résultats numériques de LANCELOT
Bibliographie
Télécharger le rapport complet
