Augmented Lagrangian methods

Consider smooth equalities h(x)=0 and use the sign convention L=f+λ-transpose-h. The augmented Lagrangian adds half rho times the squared Euclidean constraint norm, where rho is positive. For a fixed multiplier and penalty, the inner problem is unconstrained unless the original formulation also has simple bounds. Its gradient contains both the estimated multiplier force and a correction proportional to the current violation. A raw small objective gradient is no longer the appropriate stopping diagnostic.

After an inner approximate minimization, update the multiplier by adding rho times the new residual. With an exact inner stationary point, the original Lagrangian gradient evaluated at this updated multiplier is zero. This identity explains the update sign and the link between inner stationarity and an original KKT residual. It does not make the primal residual zero. If the inner solve stops early, its nonzero gradient transfers directly to the corresponding stationarity residual and must be accounted for in an outer tolerance policy.

At a feasible KKT point, the augmented Hessian equals the Lagrangian Hessian plus rho times the constraint Jacobian Gram matrix. The second term adds curvature in directions that change the constraints, while a second-order sufficient condition supplies positive curvature on tangent directions. With full-row-rank equality Jacobian and suitable smoothness, a sufficiently large finite rho makes the augmented Hessian positive definite near that solution. This is a local curvature mechanism, not a proof that every inner problem has a unique global minimum.

A pure quadratic penalty has no adjustable linear multiplier term, so its residual must generate the missing constraint force by itself. Achieving a finite nonzero force while reducing that residual often drives rho upward. In a multiplier method the stored estimate can approach the correct force while rho stays fixed in favorable local circumstances. Raising rho is still useful when feasibility improvement stalls, but an infinite automatic escalation can destroy the numerical advantage and conceal an inaccurate inner solve.

A practical outer stopping rule combines the constraint norm and the Lagrangian gradient norm, with multiplier and variable scales recorded. The inner tolerance is often loose initially and tightened as the outer iteration advances. Solving every early inner problem to extreme accuracy can waste computation, while never tightening can prevent a meaningful final KKT residual. Precise convergence theorems specify the accuracy schedule, penalty updates, regularity, and the local or global subproblem properties; the update formula alone is insufficient.

Inequality constraints require additional structure. One approach introduces nonnegative slacks and treats the resulting equalities together with bounds; another uses a projected multiplier formula derived for inequalities. Simply applying an unrestricted equality multiplier update to an inequality and ignoring sign and complementarity is wrong. For nonconvex objectives, even an excellent feasible stationary result may be only locally optimal. Repeating initializations can supply empirical comparisons but cannot turn those observations into a general global certificate.