Algorithme du lagrangien augmenté

Les algorithmes du lagrangien augmenté sont une certaine classe d'algorithmes pour résoudre des problèmes d'optimisation sous contraintes. Elles présentent des similitudes avec les méthodes de pénalité dans le sens où elles remplacent un problème d'optimisation sous contraintes par une série de problèmes sans contrainte et ajoutent un terme de pénalité à l'objectif ; la différence est qu'une méthode du lagrangien augmenté ajoute encore un autre terme, conçu pour agir comme un multiplicateur de Lagrange. Le Lagrangien augmenté est apparenté, mais non identique à la méthode des multiplicateurs de Lagrange. Vu différemment, l'objectif sans contrainte est le lagrangien du problème contraint, avec un terme de pénalité supplémentaire (l'augmentation). La méthode était à l'origine connue sous le nom de méthode des multiplicateurs et a été beaucoup étudiée dans les années 1970 et 1980 comme une bonne alternative aux méthodes de pénalité. Il a été discuté pour la première fois par Magnus Hestenes et par Michael J. D. Powell en 1969. La méthode a été étudiée par R. Tyrrell Rockafellar en relation avec la , en particulier en relation avec les méthodes des points proximaux, la régularisation Moreau-Yosida et les opérateurs monotones maximaux : ces méthodes ont été utilisées en optimisation structurelle. La méthode a également été étudiée par Dimitri Bertsekas, notamment dans son livre de 1982, ainsi que des extensions impliquant des fonctions de régularisation non quadratiques, telles que la régularisation entropique, qui donne naissance à la « méthode exponentielle des multiplicateurs », une méthode qui gère les contraintes d'inégalité avec une fonction lagrangienne augmentée deux fois dérivable. Depuis les années 1970, la programmation quadratique séquentielle (PQS) et les méthodes de points intérieurs (MPI) ont suscité une attention croissante, en partie parce qu'elles utilisent plus facilement des sous-programmes de matrice creuse à partir de bibliothèques de logiciels numériques, et en partie parce que les MPI ont prouvé des résultats de complexité via la théorie de .