Augmented Lagrangian Methods

See also: Constrained Optimization Nonlinear Programming

Augmented Lagrangian method is one of the algorithms in a class of methods for constrained optimization that seeks a solution by replacing the original constrained problem by a sequence of unconstrained subproblems. Also known as the method of multipliers, the augmented Lagrangian method introduces explicit Lagrangian multiplier estimates at each step.

Augmented Lagrangian algorithms are based on successive minimization of the augmented Lagrangian \(\mathcal{L}_A\) with respect to \(x\), with updates of \(\lambda\) and possibly occurring between iterations. An augmented Lagrangian algorithm for the constrained optimization problem computes \(x_{k+1}\) as an approximate minimizer of the subproblem
\[\min \{ {\mathcal{L}_A(x, \lambda_k; \nu_k) : l \leq x \leq u} \},\] where
\[\mathcal{L}_A(x, \lambda; \nu) = f(x) + \sum_{i \in \mathcal{E}} \lambda_i c_i(x) + \frac{1}{2} \sum_{i \in \mathcal{E}} \nu_i c_i^2(x)\] includes only the equality constraints. Updating of the multipliers usually takes the form
\[\lambda_i \leftarrow \lambda_i + \nu_i c_i (x_k).\]

This approach is relatively easy to implement because the main computational operation at each iteration is minimization of the smooth function \(\mathcal{L}_A\) with respect to \(x\) subject only to bound constraints. A large-scale implementation of the augmented Lagrangian approach can be found in the LANCELOT package, which is available on the NEOS Server. LANCELOT solves the bound-constrained subproblem by using special data structures to exploit the (group partially separable) structure of the underlying problem. The OPTIMA and OPTPACK libraries also contain augmented Lagrangian codes.