These four constrained optimization methods looks similarly when first seen:
- Lagrange Multipliers
- Penalty Methods
- Augmented Lagrangian Methods
- Merit Methods
Here is a comprehensive explaination towards these four methods written by Brian Borchers.
No, they’re not all the same and it’s important to understand the differences between them.
Start with a simple optimization problem
where we can assume for simplicity that and are smooth (at least twice continously differentiable.)
The Lagrangian function is
Note that is a function of and . The first order necessary condition for a point to be a minimizer is that there is a such that is a stationary point of . In the method of multipliers, we try to solve the nonlinear system of equations
This is typically done by alternately minimizing with respect to and updating . Given a Lagrange multiplier estimate , we minimize to get . Then we update with
Where is a step size parameter that can be set in various ways.
An penalty function for our problem is a function that is if and greater than when . A commonly used penalty function is the quadratic penalty function
In the penalty function method, we solve an unconstrained problem of the form
where is a penalty parameter that is increased until the solution of the penalized problem is close to satisfying . Note that is not a Lagrange multiplier in this case.
For problems with inequality constraints a commonly used penalty function is
An augmented Lagrangian function combines the penalty function idea with the Lagrangian:
Augmented Lagrangian methods minimize with respect to , update the Lagrange multiplier estimate and then (if necessary) update the penalty parameter in each iteration. In practice, augmented Lagrangian methods outperform simple penalty methods and the method of multipliers.
Merit functions are used in a variety of nonlinear programming algorithms. You’ll most commonly see them used in sequential quadratic programming methods. In these methods, a search direction, , is computed at each iteration. The step is from to
where the step size parameter is determined by minimizing a merit function
The merit function is typically something like a penalized objective function or an augmented Lagrangian, but there’s a great deal of freedom in the form of the merit function.
These functions and the associated methods are described in many textbooks on nonlinear optimization. A good discussion can be found in Numerical Optimization by Nocedal and Wright.