Augmented Lagrangian Method

The Augmented Lagrangian Method (ALM), also known as the method of multipliers, combines the advantages of penalty methods and Lagrangian methods to solve constrained optimization problems. It addresses the ill-conditioning issues of penalty methods while maintaining their computational advantages.

Mathematical Formulation

Consider a constrained optimization problem:

\begin{align} \min_{\theta} \quad & L(\theta) \ \text{subject to} \quad & h_j(\theta) = 0, \quad j = 1,2,\ldots,m \ & I_k(\theta) \geq 0, \quad k = 1,2,\ldots,n \end{align}

where:

• $\theta \in {\mathbb{R}}^D$ is the design vector
• $L(\theta )$ is the objective function to be minimized
• $h_j(\theta )$ are the equality constraint functions
• $I_k(\theta )$ are the inequality constraint functions

The Augmented Lagrangian function for this problem is:

${\mathcal{L}}_A(\theta ,\lambda ,\sigma ,\mu )=L(\theta )-{\sum }_{j=1}^m{\lambda }_j{h}_j(\theta )+\frac{\mu }{2}{\sum }_{j=1}^m{h}_j(\theta {)}^2-{\sum }_{k=1}^n{\sigma }_k{I}_k(\theta )+\frac{\mu }{2}{\sum }_{k=1}^n\max (0,-I_k(\theta )+\frac{{\sigma }_k}{\mu }{)}^2$

where:

• ${\lambda }_j$ are the Lagrange multipliers for equality constraints
• ${\sigma }_k$ are the Lagrange multipliers for inequality constraints
• $\mu >0$ is the penalty parameter

Solution Approach

1. Initialization:

   • Select an initial design point ${\theta }^{(0)}$
   • Choose initial Lagrange multiplier estimates ${\lambda }^{(0)}$ and ${\sigma }^{(0)}$
   • Set an initial penalty parameter ${\mu }^{(0)}>0$
   • Set iteration counter $i=0$

2. Iteration:

   • Solve the unconstrained subproblem: ${\theta }^{(i+1)}=\arg {\min }_{\theta }{\mathcal{L}}_A(\theta ,{\lambda }^{(i)},{\sigma }^{(i)},{\mu }^{(i)})$
   • Update the Lagrange multipliers: ${\lambda }_j^{(i+1)}={\lambda }_j^{(i)}-{\mu }^{(i)}{h}_j({\theta }^{(i+1)})$ ${\sigma }_k^{(i+1)}=\max (0,{\sigma }_k^{(i)}-{\mu }^{(i)}{I}_k({\theta }^{(i+1)}))$
   • Check convergence based on constraint violations and multiplier changes
   • If not converged, update penalty parameter: ${\mu }^{(i+1)}=\gamma {\mu }^{(i)}$ (if needed)
   • Increment $i$ and repeat

3. Convergence:

   • The method converges to a KKT point of the original problem

Key Properties

Advantages

1. Improved Conditioning: Avoids the severe ill-conditioning of pure penalty methods
2. Faster Convergence: Typically requires fewer iterations and lower penalty parameters than penalty methods
3. Exact Constraint Satisfaction: Can achieve precise constraint satisfaction with finite penalty parameters
4. Dual Information: Provides estimates of Lagrange multipliers throughout the optimization process

Disadvantages

1. Complexity: More complex than pure penalty or Lagrangian methods
2. Parameter Tuning: Requires careful selection of penalty update parameters
3. Subproblem Difficulty: Each unconstrained subproblem may be more challenging to solve
4. Non-Convexity: For non-convex problems, convergence to global optima is not guaranteed

Method Variations

Method of Multipliers (for Equality Constraints)

For problems with only equality constraints, the Augmented Lagrangian simplifies to:

${\mathcal{L}}_A(\theta ,\lambda ,\mu )=L(\theta )-{\sum }_{j=1}^m{\lambda }_j{h}_j(\theta )+\frac{\mu }{2}{\sum }_{j=1}^m{h}_j(\theta {)}^2$

The multiplier update becomes:

${\lambda }_j^{(i+1)}={\lambda }_j^{(i)}-{\mu }^{(i)}{h}_j({\theta }^{(i+1)})$

ADMM (Alternating Direction Method of Multipliers)

A specialized version of ALM for problems with separable objective functions and linear constraints:

\begin{align} \min_{\theta_1, \theta_2} \quad & L_1(\theta_1) + L_2(\theta_2) \ \text{subject to} \quad & A\theta_1 + B\theta_2 = c \end{align}

ADMM alternates between optimizing for ${\theta }_1$ and ${\theta }_2$ before updating multipliers.

Separable Augmented Lagrangian

For problems with block structure, the method can be adapted to update different blocks of variables sequentially:

${\mathcal{L}}_A({\theta }_1,{\theta }_2,\dots ,{\theta }_B,\lambda ,\mu )={\sum }_{b=1}^B{L}_b({\theta }_b)-{\lambda }^{T}h({\theta }_1,{\theta }_2,\dots ,{\theta }_B)+\frac{\mu }{2}|h({\theta }_1,{\theta }_2,\dots ,{\theta }_B){|}^2$

Implementation Considerations

Unconstrained Subproblem Solver

The choice of algorithm for solving the unconstrained subproblems affects performance:

• Quasi-Newton Methods: BFGS or L-BFGS for smooth problems
• Conjugate Gradient: For large-scale problems with good conditioning
• Hessian-Free Newton: When second derivatives are available

Multiplier Updates

Multiplier updates can be damped to improve stability:

${\lambda }_j^{(i+1)}={\lambda }_j^{(i)}-\alpha {\mu }^{(i)}{h}_j({\theta }^{(i+1)})$

where $\alpha \in (0,1]$ is a damping factor.

Penalty Parameter Updates

The penalty parameter is typically increased only when constraint violations don’t decrease sufficiently:

• If $|h({\theta }^{(i+1)})|>\beta |h({\theta }^{(i)})|$, where $\beta \in (0,1)$, then ${\mu }^{(i+1)}=\gamma {\mu }^{(i)}$
• Otherwise, keep ${\mu }^{(i+1)}={\mu }^{(i)}$

Convergence Criteria

Common stopping conditions include:

• Constraint violations below tolerance
• KKT conditions satisfied to desired accuracy
• Change in Lagrange multipliers below tolerance
• Maximum iterations reached

Theoretical Foundations

Connection to KKT Conditions

The fixed points of the ALM iteration satisfy the KKT conditions for the original constrained problem:

1. Stationarity: $\nabla L({\theta }^{\ast })-{\sum }_{j=1}^m{\lambda }_j^{\ast }\nabla h_j({\theta }^{\ast })-{\sum }_{k=1}^n{\sigma }_k^{\ast }\nabla I_k({\theta }^{\ast })=0$
2. Primal Feasibility: $h_j({\theta }^{\ast })=0$ and $I_k({\theta }^{\ast })\ge 0$
3. Dual Feasibility: ${\sigma }_k^{\ast }\ge 0$
4. Complementary Slackness: ${\sigma }_k^{\ast }{I}_k({\theta }^{\ast })=0$

Local vs. Global Convergence

• For convex problems, ALM converges to global optima
• For non-convex problems, ALM converges to local optima or stationary points
• The quality of the final solution depends on the initial point ${\theta }^{(0)}$

Example: Augmented Lagrangian Application

Consider the inequality-constrained problem:

\begin{align} \min_{\theta_1, \theta_2} \quad & \theta_1^2 + \theta_2^2 \ \text{subject to} \quad & \theta_1 + \theta_2 \geq 1 \end{align}

We rewrite the constraint as $I(\theta )={\theta }_1+{\theta }_2-1\ge 0$. The Augmented Lagrangian is:

${\mathcal{L}}_A(\theta ,\sigma ,\mu )={\theta }_1^2+{\theta }_2^2-\sigma ({\theta }_1+{\theta }_2-1)+\frac{\mu }{2}\max (0,-({\theta }_1+{\theta }_2-1)+\frac{\sigma }{\mu }{)}^2$

For a given ${\sigma }^{(i)}$ and ${\mu }^{(i)}$, we solve for ${\theta }^{(i+1)}$, then update:

${\sigma }^{(i+1)}=\max (0,{\sigma }^{(i)}-{\mu }^{(i)}({\theta }_1^{(i+1)}+{\theta }_2^{(i+1)}-1))$

As the method progresses, $\theta$ converges to $(0.5,0.5)$ and $\sigma$ to $1$.

Practical Applications

Structural Optimization

In structural design problems, ALM effectively handles:

• Stress constraints: $\sigma (\theta )\le {\sigma }_{\text{allowable}}$
• Displacement constraints: $u(\theta )\le u_{\text{max}}$
• Natural frequency constraints: ${\omega }_i(\theta )\ge {\omega }_{\text{min}}$

Optimal Control

For trajectory optimization with path constraints:

• Dynamic constraints: $\dot{x}(t)=f(x(t),u(t))$
• Control limits: $u_{\text{min}}\le u(t)\le u_{\text{max}}$
• State constraints: $g(x(t))\le 0$

Machine Learning

In constrained learning problems:

• Fairness constraints: $\text{bias}(\theta )\le ϵ$
• Sparsity constraints: $|\theta {|}_0\le k$
• Budget constraints: ${\sum }_{i=1}^n{c}_i{\theta }_i\le B$

Numerical Considerations

Scaling

Proper scaling of constraints improves numerical behavior:

• Normalize constraints to have similar magnitudes
• Scale objective function to be comparable to constraint penalty terms

Starting Point

The initial point affects convergence:

• Starting from a feasible point may accelerate convergence
• Multiple starting points can be used to find better local optima

Precision

Balancing precision requirements:

• Tighten subproblem tolerances as outer iterations progress
• Use adaptive precision based on constraint violation magnitudes

Software Implementations

Several optimization libraries implement Augmented Lagrangian methods:

• LANCELOT and ALGENCAN for large-scale constrained optimization
• IPOPT with augmented Lagrangian preconditioners
• SciPy’s scipy.optimize.minimize with method=‘trust-constr’
• MATLAB’s Optimization Toolbox with fmincon algorithm=‘sqp’

Related Pages

• Penalty Method
• Lagrange Multipliers
• KKT Conditions
• Constrained Optimization
• Equality Constraints
• Inequality Constraints

Augmented Lagrangian Method

The Augmented Lagrangian Method (ALM), also known as the method of multipliers, combines the Lagrange multipliers approach with penalty terms.

Mathematical Formulation

For the constrained optimization problem:

${\min }_{\theta \in {\mathbb{R}}^D}L(\theta )\text{ subject to }\{\begin{array}{l}{E}_j(\theta )=0,j=1,\dots ,m{I}_k(\theta )\ge 0,k=1,\dots ,n\end{array}$

The Augmented Lagrangian function is:

${\mathcal{L}}_A(\theta ;\lambda ,\mu )=L(\theta )-{\sum }_{j=1}^m{\lambda }_j{E}_j(\theta )+\mu {\sum }_{j=1}^m{E}_j^2(\theta )-{\sum }_{k=1}^n{\lambda }_{m+k}{I}_k(\theta )+\mu {\sum }_{k=1}^n\max (0,-I_k(\theta ){)}^2$

Method of Operation

Instead of solving for optimal ${\lambda }^{\ast }$ directly, it is updated in an “outer” iterative loop:

${\lambda }_j^{(t+1)}={\lambda }_j^{(t)}-\mu /2E_j({\theta }^{(t+1)}),j=1,\dots ,m$

${\lambda }_{m+k}^{(t+1)}={\lambda }_{m+k}^{(t)}+\mu /2\max (0,-I_k({\theta }^{(t+1)})),k=1,\dots ,n$

Advantages

• Combines benefits of both Lagrange multipliers and penalty methods
• Improves convergence properties compared to simple penalty methods

Disadvantages

• More complex to implement due to two nested loops