AUGMENTED LAGRANGIAN

Augmented Lagrangian - The Lagrangian augmented by a term that retains the stationary properties of a solution to the original mathematical program but alters the hessian in the subspace defined by the active set of constraints. The added term is sometimes called a penalty term, as it decreases the value of the augmented Lagrangian for x off the surface defined by the active constraints. For example, the penalty term could be proportional to the squared norm of the active constraints:

where p is a parameter (negative for maximization), G(x) is the vector of active constraints (at x), and L is the usual Lagrangian. In this case, suppose x* is a Kuhn-Tucker point with multiplier y*. Then, L_a(x*, y*) = L(x*, y*) (since G(x*)=0). Further, the gradient of the penalty term with respect to x is 0 at x*, and the hessian of the penalty term is simply p A(x*)'A(x*), where A(x*) is the matrix whose rows are the gradients of the active constraints. Since A(x*)'A(x*) is positive semi-definite , the penalty term has the effect of increasing the eigenvalues (decreasing them if maximizing).