Augmented Lagrangian method

Augmented Lagrangian methods are a certain class of algorithms for solving constrained optimization problems. They have similarities to penalty methods in that they replace a constrained optimization problem by a series of unconstrained problems; the difference is that the augmented Lagrangian method adds an additional term to the unconstrained objective. This additional term is designed to mimic a Lagrange multiplier. The augmented Lagrangian is not the same as the method of Lagrange multipliers.

Viewed differently, the unconstrained objective is the Lagrangian of the constrained problem, with an additional penalty term (the augmentation).

The method was originally know as the Method of Multipliers, and was studied much in the 1970 and 1980s as a good alternative to penalty methods. It was first discussed in Hestenes in 1969 and by Powell in 1969 The method was also covered extensively by Dimitri Bertsekas and his 1982 book is a good reference.

With the advent of sequential quadratic programming and later interior point methods, the augmented Lagrangian method has seen less active research in the past twenty years. The method is still useful in some contexts, and it is still discussed in modern optimization textbooks.

General method

Let us say we are solving the following constrained problem:

$\min f({\mathbf {x}})$

subject to

$c_{i}({\mathbf {x}})=0~\forall i\in I.$

This problem can be solved as a series of unconstrained minimization problems. For reference, we first list the penalty method approach:

$\min \Phi _{k}({\mathbf {x}})=f({\mathbf {x}})+\mu _{k}~\sum _{i\in I}~c_{i}({\mathbf {x}})^{2}$

The penalty method solves this problem, then at the next iteration it re-solves the problem using a larger vale of $\mu _{k}$ (and using the old solution as a the initial guess or "warm-start").

The augmented Lagrangian method uses the following unconstrained objective:

$\min \Phi _{k}({\mathbf {x}})=f({\mathbf {x}})+\mu _{k}~\sum _{i\in I}~c_{i}({\mathbf {x}})^{2}-\sum _{i\in I}~\lambda _{i}c_{i}({\mathbf {x}})^{2}$

and after each iteration, in addition to updating $\mu _{k}$, the variable $\lambda$ is also updated according to the rule

$\lambda _{i}\leftarrow \lambda _{i}-\mu _{k}c_{i}({\mathbf {x}}_{k})$

where ${\mathbf {x}}_{k}$ is the solution to the unconstrained problem at the kth step, i.e. ${\mathbf {x} }_{k}={\text{argmin}}\Phi _{k}({\mathbf {x} })$

The variable $\lambda$ is an estimate of the Lagrange multiplier, and the accuracy of this estimate improves at every step.

The major advantage of the method is that unlike the penalty method,

it is not necessary to take $\mu \rightarrow \infty$ in order to solve the original constrained problem. Instead, because of the presence of the Lagrange multiplier term, $\mu$ can stay much smaller.

The method can be extended to handle inequality constraints. For a discussion of practical improvements, see .

Comparison with penalty methods

From , it is suggested that the augmented Lagrangian method is generally preferred to the quadratic penalty method since there is little extra computational cost and the parameter $\mu$ need not go to infinity, thus avoiding ill-conditioning.

Software

Some well-known software packages that use the augmented Lagrangian method are MINOS, LANCELOT, and PENNON

See also

• Penalty methods
• Barrier method
• Lagrange multiplier

Bibliography

• Nocedal, Jorge; Wright, Stephen J. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-30303-1