1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

Start with a simple optimization problem

$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.