Merit function vs Largrange Functions vs Penalty Funcitons

I've been reading up on constraint optimization. I've come across the three terms:

• Merit Function
• Lagrange Function
• Penalty Function

I'm pretty sure all these three things are the same. That is, they quantify how much an iterate satisfies both the objective and the constraint. However, I would like a second opinion to clarify.

No, they're not all the same and it's important to understand the differences between them.

$\min f(x)$

subject to

$g(x) = 0$

where we can assume for simplicity that $f$ and $g$ are smooth (at least twice continously differentiable.)

The Lagrangian function is

$L(x,\lambda)=f(x)+\lambda g(x)$

Note that $L$ is a function of $x$ and $\lambda$. The first order necessary condition for a point $x^{*}$ to be a minimizer is that there is a $\lambda^{*}$ such that $(x^{*},\lambda^{*})$ is a stationary point of $L$. In the method of multipliers, we try to solve the nonlinear system of equations

$\nabla_{x,\lambda} L(x,y)=0$

This is typically done by alternately minimizing with respect to $x$ and updating $\lambda$. Given a Lagrange multiplier estimate $\lambda^{(k)}$, we minimize $L(x,\lambda^{k})$ to get $x^{(k)}$. Then we update $\lambda$ with

$\lambda^{(k+1)}=\lambda^{(k)} +\alpha_{k} g(x^{(k)})$

Where $\alpha_{k}$ is a step size parameter that can be set in various ways.

An penalty function for our problem is a function that is $0$ if $g(x)=0$ and greater than $0$ when $g(x) \neq 0$. A commonly used penalty function is the quadratic penalty function

$\phi(g(x))=g(x)^{2}$

In the penalty function method, we solve an unconstrained problem of the form

$\min_{x} f(x)+\rho \phi(g(x))$

where $\rho$ is a penalty parameter that is increased until the solution of the penalized problem is close to satisfying $g(x)=0$. Note that $\rho$ is not a Lagrange multiplier in this case.

For problems with inequality constraints a commonly used penalty function is

$\phi(g(x))=\max(g(x),0)^{2}$.

An augmented Lagrangian function combines the penalty function idea with the Lagrangian:

$\hat{L}(x,\lambda; \rho)=f(x)+\lambda g(x) + \rho \phi(g(x))$

Augmented Lagrangian methods minimize $\hat{L}$ with respect to $x$, update the Lagrange multiplier estimate $\lambda$ and then (if necessary) update the penalty parameter $\rho$ 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, $d^{(k)}$, is computed at each iteration. The step is from $x^{(k})$ to

$x^{(k+1)}=x^{(k)}+\alpha_{k} d^{(k)}$

where the step size parameter $\alpha_{k}$ is determined by minimizing a merit function

$\min_{\alpha} M(x^{(k)}+\alpha d^{(k)})$

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.

• Thanks for the comprehensive response Brian! – echo Dec 30 '17 at 21:21