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. 
 A: 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.
