Augmented Lagrangian method

Augmented Lagrangian methods are a certain class of <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> for solving <a href="/facts/Constraint_(mathematics)/QLFIFlFX">constrained</a> <a href="/facts/Optimization_(mathematics)/oRn8Iv5I">optimization</a> problems. They have similarities to <a href="/facts/Penalty_method/IVXJnaIz">penalty methods</a> in that they replace a constrained optimization problem by a series of unconstrained problems and add a penalty term to the <a href="/facts/Objective_function/xv5ozuhl">objective</a>, but the augmented Lagrangian method adds yet another term designed to mimic a <a href="/facts/Lagrange_multiplier/U5mSI5YP">Lagrange multiplier</a>. The augmented Lagrangian is related to, but not identical with, the <a href="/facts/Lagrange_multiplier/U5mSI5YP">method of Lagrange multipliers</a>.
Viewed differently, the unconstrained objective is the <a href="/facts/Lagrange_multipliers/U5mSI5YP">Lagrangian</a> of the constrained problem, with an additional penalty term (the augmentation).
The method was originally known as the method of multipliers and was studied in the 1970s and 1980s as a potential alternative to penalty methods. It was first discussed by <a href="/facts/Magnus_Hestenes/nGb00KG2">Magnus Hestenes</a> and then by <a href="/facts/Michael_J._D._Powell/rcNKU74P">Michael Powell</a> in 1969. The method was studied by <a href="/facts/R._Tyrrell_Rockafellar/Jzj3n73g">R. Tyrrell Rockafellar</a> in relation to <a href="/facts/Fenchel_duality/GFjnfVnD">Fenchel duality</a>, particularly in relation to proximal-point methods, Moreau–Yosida regularization, and <a href="/facts/Monotone_operator/MjQK0YL2">maximal monotone operators</a>; these methods were used in <a href="/facts/Structural_engineering/Wj1vpoGh">structural optimization</a>. The method was also studied by <a href="/facts/Dimitri_Bertsekas/uLJEULS4">Dimitri Bertsekas</a>, notably in his 1982 book, together with extensions involving non-quadratic regularization functions (e.g., <a href="/facts/Bregman_divergence/wREwF8qo">entropic regularization</a>). This combined study gives rise to the "exponential method of multipliers" which handles inequality constraints with a twice-differentiable augmented Lagrangian function.
Since the 1970s, <a href="/facts/Sequential_quadratic_programming/3QUzYBps">sequential quadratic programming</a> (SQP) and <a href="/facts/Interior_point_method/prIIrceN">interior point methods</a> (IPM) have been given more attention, in part because they more easily use <a href="/facts/Sparse_matrix/FFtN0XjR">sparse matrix</a> <a href="/facts/Subroutine/9vFJrg0A">subroutines</a> from <a href="/facts/Numerical_linear_algebra/jnS6Tteb">numerical</a> <a href="/facts/Numerical_software/QT9cYa9z">software libraries</a>, and in part because IPMs possess proven complexity results via the theory of <a href="/facts/Self-concordant_function/MrQvoXd5">self-concordant functions</a>. The augmented Lagrangian method was rejuvenated by the optimization systems <a href="/facts/Galahad_library/wQunIYB0">LANCELOT</a>, ALGENCAN and <a href="/facts/AMPL/pzceW9mH">AMPL</a>, which allowed sparse matrix techniques to be used on seemingly dense but "partially-separable" problems. The method is still useful for some problems.
Around 2007, there was a resurgence of augmented Lagrangian methods in fields such as <a href="/facts/Total_variation_denoising/rKa5n2wI">total variation denoising</a> and <a href="/facts/Compressed_sensing/aR5DQm3n">compressed sensing</a>. In particular, a variant of the standard augmented Lagrangian method that uses partial updates (similar to the <a href="/facts/Gauss%25E2%2580%2593Seidel_method/eK94QeFt">Gauss–Seidel method</a> for solving linear equations) known as the alternating direction method of multipliers or ADMM gained some attention.

Augmented Lagrangian method open-in-new

Augmented Lagrangian method