Augmented Lagrangian

From Glossary

Jump to: navigation, search

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 LaTeX: 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:

L_a (x, y) = L(x, y) + p G(x)^T G(x),

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

Personal tools