 # 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 $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: $LaTeX: 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).