Penalty and Augmented-Lagrangian Methods

Intuition Beginner

Suppose you must find the lowest point of a landscape, but you are only allowed to stand on a single marked path. One honest approach ignores the rule and instead charges a fine for stepping off the path: the farther off you stray, the bigger the fine. Add the fine to the height you are trying to minimize, and now you can roam the whole landscape freely. If the fine is steep enough, the cheapest place to stand is almost on the path, because straying costs too much. This is the penalty idea: replace a hard rule with a soft cost and solve an easier problem with no rules at all.

The catch is the size of the fine. A gentle fine lets you cheat — the best free point still sits a little off the path. To push it onto the path you must crank the fine higher and higher. But a giant fine makes the landscape a steep, narrow canyon: easy to fall into, miserable to find the bottom of precisely. The very thing that forces obedience also makes the problem numerically nasty, so you are caught between a fine too small to obey and a fine too large to solve.

The augmented-Lagrangian method escapes the trap with a smarter fine. Alongside the growing penalty it keeps a running estimate of the price of each rule — how hard the rule pushes back at the true answer, the same multiplier from constrained pricing. After each solve it updates that price estimate using how much you violated the rule. With the price doing the work of pulling you onto the path, the fine itself never has to grow without bound, so the problem stays well-behaved while the answer still lands exactly on the path.

Visual Beginner

Picture a valley (the cost) cut by a single straight path (the constraint). The free bottom of the valley lies off the path. The quadratic penalty adds a parabolic "fine" that grows with distance from the path; raising the fine pinches the combined surface tighter around the path, dragging its minimum toward — but never exactly onto — the path until the fine is enormous.

  cost valley bottom  *  (off the path)
        \         /
         \   *   /          path (constraint c(x)=0)
          \_____/      ======|=========================
                             |
   small fine:  combined min lands HERE  o   (still off path, sloppy)
   big fine:    combined min lands here   o  (closer, but canyon is steep)
   HUGE fine:   on the path . but the surface is a narrow ill-conditioned gorge

   augmented Lagrangian:
     keep a PRICE estimate  lambda  for the path
     after each solve:  lambda  <-  lambda  -  (fine)*(violation)
     the price pulls the minimum ONTO the path with the fine kept MODERATE

method	what is added to the cost	fine size	answer lands on path?
quadratic penalty	fine = (μ/2)(violation)²	must grow to infinity	only in the limit
exact ℓ1 penalty	fine = μ·(violation), absolute value	finite, above the true price	yes, but the fine has a kink
augmented Lagrangian	price·violation + (μ/2)(violation)²	stays bounded	yes, the price does the pulling

The takeaway: a penalty turns a constrained problem into a sequence of free ones, but a pure quadratic penalty must blow up to enforce the rule and so becomes ill-conditioned; carrying a price estimate keeps the fine moderate and still lands the answer on the path.

Worked example Beginner

Minimize the cost $f(x)=x^2$ subject to the single rule $x=1$. The free bottom is at $x=0$, which breaks the rule, so the answer must be pushed to $x=1$.

Step 1. Build the penalized cost. Charge a quadratic fine for missing $x=1$: with fine strength $\mu$, the combined cost is $Q(x)=x^2+\frac{\mu }{2}(x-1{)}^2$.

Step 2. Find the free minimum. Set the slope to zero: $2x+\mu (x-1)=0$, so $(2+\mu )x=\mu$, giving $x=\mu /(2+\mu )$.

Step 3. Watch the fine grow. With $\mu =1$, $x=1/3$ — far from the path. With $\mu =10$, $x=10/12\approx 0.833$. With $\mu =100$, $x=100/102\approx 0.980$. The minimizer creeps toward $1$ but reaches it only as $\mu \to \infty$.

Step 4. Try the augmented version. Carry a price $\lambda$ and minimize $L_A(x)=x^2-\lambda (x-1)+\frac{\mu }{2}(x-1{)}^2$, whose minimizer is $x=(\lambda +\mu )/(2+\mu )$. Start $\lambda =0$, $\mu =2$: $x=2/4=0.5$. Update the price by the violation, $\lambda \leftarrow \lambda -\mu (x-1)=0-2(0.5-1)=1$. Re-solve with $\mu$ still $2$: $x=3/4=0.75$. Update again, $\lambda \leftarrow 1.5$, then $x=0.875$, then $\lambda =1.75$, $x=0.9375$. The price climbs toward $2$ and $x$ toward $1$ with the fine fixed at $\mu =2$.

What this tells us. The pure penalty needs an ever-larger fine to reach $x=1$; the augmented version lands on $x=1$ with the fine held at $\mu =2$ because the price $\lambda$ converges to the true value $2$ and does the pulling. The price update, not a giant penalty, enforces the rule.

Check your understanding Beginner

Formal definition Intermediate+

Consider the equality-constrained nonlinear program over $x\in {\mathbb{R}}^n$,

$$\underset{x}{\min }f(x)\text{subject to}{c}_i(x)=0(i\in \mathcal{E}),$$

with $f,c_i$ twice continuously differentiable; write $c(x)=(c_i(x){)}_{i\in \mathcal{E}}\in {\mathbb{R}}^m$ and let $A(x)=Dc(x)\in {\mathbb{R}}^{m\times n}$ be the constraint Jacobian. Inequality constraints $c_i(x)\ge 0$ are folded in below. The KKT conditions of 44.02.02 read $\nabla f(x^{\star })-A(x^{\star }{)}^{\top }{\lambda }^{\star }=0$ and $c(x^{\star })=0$, with ${\lambda }^{\star }$ the multipliers. The penalty parameter is a scalar $\mu >0$ that scales the violation cost; the sign convention used throughout writes the Lagrangian as $L(x,\lambda )=f(x)-{\lambda }^{\top }c(x)$.

Definition (quadratic penalty function). The quadratic penalty function is

$$Q(x;\mu )=f(x)+\frac{\mu }{2}\sum _{i\in \mathcal{E}}{c}_i(x{)}^2=f(x)+\frac{\mu }{2}\Vert c(x){\Vert }_2^2.$$

The quadratic-penalty method minimizes $x\mapsto Q(x;{\mu }_k)$ approximately for an increasing sequence ${\mu }_k\to \infty$, warm-starting each subproblem at the previous minimizer. The function is smooth, so any unconstrained solver applies.

Definition (nonsmooth exact ${\ell }_1$ penalty). For the program with equalities $c_i(x)=0$ ($i\in \mathcal{E}$) and inequalities $c_i(x)\ge 0$ ($i\in \mathcal{I}$), the ${\ell }_1$ penalty function is

$${\varphi }_1(x;\mu )=f(x)+\mu \sum _{i\in \mathcal{E}}|c_i(x)|+\mu \sum _{i\in \mathcal{I}}[c_i(x){]}^{-},[a{]}^{-}=\max (0,-a),$$

a nonsmooth function (kinks where a constraint becomes active) that is exact: for $\mu$ above a finite threshold its local minimizers coincide with those of the constrained problem, with no parameter blow-up. The new symbols $\mu$ (penalty parameter), $[a{]}^{-}=\max (0,-a)$ (negative part), and $L_A$ (augmented Lagrangian, below) are introduced here with these definitions.

Definition (augmented Lagrangian / Hestenes-Powell function). The augmented Lagrangian for the equality-constrained problem is

$$L_A(x,\lambda ;\mu )=f(x)-{\lambda }^{\top }c(x)+\frac{\mu }{2}\Vert c(x){\Vert }_2^2=L(x,\lambda )+\frac{\mu }{2}\Vert c(x){\Vert }_2^2,$$

the Lagrangian shifted by a quadratic penalty. The method of multipliers alternates an approximate primal minimization $x_k\approx \arg {\min }_x{L}_A(x,{\lambda }_k;{\mu }_k)$ with the first-order multiplier update

$${\lambda }_{k+1}={\lambda }_k-{\mu }_{k}c(x_k),$$

optionally increasing ${\mu }_k$ only if feasibility is not improving. For inequalities $c_i(x)\ge 0$ the shifted (Rockafellar) form replaces each inequality term by $-\frac{1}{2\mu }([{\lambda }_i-\mu c_i(x){]}^{+}{}^2-{\lambda }_i^2)$, recovering a smooth augmented function whose multiplier update is the projection ${\lambda }_{i,k+1}=[{\lambda }_{i,k}-{\mu }_k{c}_i(x_k){]}^{+}$.

Counterexamples to common slips

• The quadratic penalty is not exact for finite $\mu$. Its minimizer $x_k$ satisfies $\nabla f(x_k)+{\mu }_{k}A(x_k{)}^{\top }c(x_k)=0$, so ${\mu }_k{c}_i(x_k)\to {\lambda }_i^{\star }$ forces $c(x_k)\to 0$ only as ${\mu }_k\to \infty$. Stopping at a moderate $\mu$ leaves a residual infeasibility of order $1/\mu$.
• The augmented Lagrangian is exact at finite $\mu$ only because of the multiplier, not the penalty. With ${\lambda }_k={\lambda }^{\star }$, the point $x^{\star }$ is a stationary point of $L_A(\cdot ,{\lambda }^{\star };\mu )$ for every $\mu \ge 0$; the penalty merely makes that stationary point a strict local minimizer once $\mu$ exceeds a threshold set by the reduced Hessian, not infinity.
• The ${\ell }_1$ penalty's exactness does not make it easy to minimize. Its nonsmoothness produces the Maratos effect: arbitrarily close to a solution, the full step that a Newton/SQP method wants to take can increase ${\varphi }_1$, so a naive line search rejects good steps and destroys fast convergence unless a second-order correction is added.

Key theorem with proof Intermediate+

The signature result pairs the convergence of the quadratic-penalty method to a KKT point with the diagnosis of why it is ill-conditioned, then states what the augmented-Lagrangian multiplier update buys: a bounded penalty parameter. The two are one story — the penalty Hessian's growing condition number and the recovery of the multiplier from $\mu c(x)$ are the same fact read two ways.

Theorem (quadratic-penalty convergence and conditioning). Let $x_k$ be a stationary point of $Q(\cdot ;{\mu }_k)$ with $\Vert {\nabla }_{x}Q(x_k;{\mu }_k)\Vert \le {\tau }_k$, ${\tau }_k\to 0$, ${\mu }_k\to \infty$. If $x_k\to x^{\star }$ and the constraint gradients $\{\nabla c_i(x^{\star })\}$ are linearly independent (LICQ), then $x^{\star }$ is a KKT point of the constrained problem, the quantities ${\lambda }_k:=-{\mu }_{k}c(x_k)$ converge to the KKT multipliers ${\lambda }^{\star }$, and the Hessian ${\nabla }_{xx}^{2}Q(x_k;{\mu }_k)$ has condition number growing without bound, $\kappa ({\nabla }_{xx}^{2}Q)=\Theta ({\mu }_k)$.

Proof. Stationarity of $Q$ reads ${\nabla }_{x}Q(x_k;{\mu }_k)=\nabla f(x_k)+{\mu }_k{\sum }_i{c}_i(x_k)\nabla c_i(x_k)=\nabla f(x_k)+A(x_k{)}^{\top }{\lambda }_k=r_k$ with ${\lambda }_k={\mu }_{k}c(x_k)$ (sign absorbed) and $\Vert r_k\Vert \le {\tau }_k$. Under LICQ at $x^{\star }$, $A(x^{\star })$ has full row rank, so $A(x^{\star })A(x^{\star }{)}^{\top }$ is nonsingular; from $A(x_k{)}^{\top }{\lambda }_k=r_k-\nabla f(x_k)$ and continuity, ${\lambda }_k=(A(x_k)A(x_k{)}^{\top }{)}^{-1}A(x_k)(r_k-\nabla f(x_k))\to {\lambda }^{\star }:=-(A^{\star }{A}^{\star \top }{)}^{-1}{A}^{\star }\nabla f(x^{\star })$, a finite limit. Since ${\lambda }_k={\mu }_{k}c(x_k)$ stays bounded while ${\mu }_k\to \infty$, necessarily $c(x_k)\to 0$, so $x^{\star }$ is feasible; passing to the limit in the stationarity identity gives $\nabla f(x^{\star })+A(x^{\star }{)}^{\top }{\lambda }^{\star }=0$. With feasibility and stationarity, $x^{\star }$ is a KKT point and ${\lambda }^{\star }$ its multiplier.

For conditioning, differentiate again:

$${\nabla }_{xx}^{2}Q(x;\mu )={\nabla }^{2}f(x)+\mu \sum _i{c}_i(x){\nabla }^2{c}_i(x)+\mu A(x{)}^{\top }A(x).$$

Near $x^{\star }$ the term $\mu {\sum }_i{c}_i{\nabla }^2{c}_i$ stays bounded (since $\mu c_i\to {\lambda }_i^{\star }$), but $\mu A^{\top }A$ grows linearly in $\mu$ on the $m$-dimensional range of $A^{\top }$. Let $Z$ be an orthonormal basis of $\ker A(x^{\star })$ and $Y$ a basis of its orthogonal complement (the row space of $A$). On $\mathrm{range}{A}^{\top }$ the Hessian acts like $\mu A^{\top }A$, with eigenvalues $\Theta (\mu )$; on $\ker A$ it acts like the bounded reduced Hessian $Z^{\top }({\nabla }_{xx}^{2}L)Z$, with eigenvalues $\Theta (1)$. The ratio of the largest to smallest eigenvalue is therefore $\Theta (\mu )$, so $\kappa ({\nabla }_{xx}^{2}Q(x_k;{\mu }_k))\to \infty$ at rate ${\mu }_k$. $\square$

Bridge. This theorem builds toward the augmented-Lagrangian method, whose whole purpose is to stop $\mu$ from exploding, and it appears again in every interior-point and penalty-barrier analysis where a parameter driving feasibility scales one curvature direction. This is exactly the obstruction the method of multipliers removes: the quadratic penalty recovers the multiplier only as the limit $\mu c(x_k)\to {\lambda }^{\star }$, paying for it with an $\Theta (\mu )$ condition number, whereas the augmented Lagrangian carries the multiplier ${\lambda }_k$ explicitly and updates it by ${\lambda }_{k+1}={\lambda }_k-\mu c(x_k)$, so $\mu$ never has to grow. The foundational reason the conditioning blows up is that the penalty supplies feasibility through a single large curvature on $\mathrm{range}{A}^{\top }$ while leaving the reduced Hessian on $\ker A$ untouched — the same null-space / range-space split of the KKT system from 44.02.02. Putting these together, the augmented-Lagrangian update is dual to this primal penalty: shifting $f$ by $-{\lambda }_k^{\top }c$ pre-cancels the gradient that the penalty would otherwise have to generate by brute force, so a bounded $\mu$ above the reduced-Hessian threshold suffices — the bridge from an ill-conditioned limit to a well-conditioned fixed-parameter iteration.

Exercises Intermediate+

Advanced results Master

Quadratic penalty, its limit multiplier, and the conditioning obstruction

The quadratic-penalty method minimizes $Q(x;\mu )=f(x)+\frac{\mu }{2}\Vert c(x){\Vert }^2$ over ${\mu }_k\to \infty$. Its stationary points satisfy $\nabla f(x_k)+{\mu }_{k}A(x_k{)}^{\top }c(x_k)=0$, so the scaled residual ${\mu }_{k}c(x_k)$ is the embedded multiplier estimate, converging to ${\lambda }^{\star }$ under LICQ while $c(x_k)=O(1/{\mu }_k)\to 0$ ^{[Nocedal & Wright §17.1]}. The cost is structural: ${\nabla }_{xx}^{2}Q={\nabla }_{xx}^{2}L+\mu A^{\top }A$ to leading order, a sum of a bounded reduced Hessian on $\ker A$ and an $\Theta (\mu )$ curvature on $\mathrm{range}{A}^{\top }$, so $\kappa ({\nabla }_{xx}^{2}Q)=\Theta (\mu )$. The split is exactly the null-space / range-space decomposition of the KKT system of 44.02.02: the penalty enforces feasibility by inflating curvature only in the directions the constraint Jacobian sees, and the price is a Hessian whose spectrum spans $\Theta (1)$ to $\Theta (\mu )$. A direct Newton solve on $Q$ at large $\mu$ loses digits proportional to $\log \mu$, which is why the pure penalty method is a pedagogical baseline rather than a production algorithm.

The augmented Lagrangian and the bounded-penalty guarantee

The Hestenes-Powell augmented Lagrangian $L_A(x,\lambda ;\mu )=f(x)-{\lambda }^{\top }c(x)+\frac{\mu }{2}\Vert c(x){\Vert }^2$ removes the obstruction by carrying the multiplier explicitly. Completing the square exhibits it as a penalty with a shifted target, $L_A(x,\lambda ;\mu )=f(x)+\frac{\mu }{2}\Vert c(x)-\lambda /\mu {\Vert }^2-\frac{1}{2\mu }\Vert \lambda {\Vert }^2$, so when $\lambda ={\lambda }^{\star }$ the shift ${\lambda }^{\star }/\mu$ aligns the penalty's preferred residual with the feasible point and $x^{\star }$ becomes a strict local minimizer for every $\mu$ above a finite threshold $\bar{\mu }$ fixed by the reduced Hessian and the smallest singular value of $A^{\star }$ ^{[Bertsekas Ch. 2]}. The Hessian at the solution is ${\nabla }_{xx}^{2}L+\mu A^{\star \top }{A}^{\star }$, positive definite for $\mu >\bar{\mu }$ — a bounded $\mu$, so the subproblems stay well-conditioned. The first-order multiplier update ${\lambda }_{k+1}={\lambda }_k-{\mu }_{k}c(x_k)$ is gradient ascent on the augmented dual $d_{\mu }(\lambda )={\min }_x{L}_A(x,\lambda ;\mu )$ with $\nabla d_{\mu }=-c(x(\lambda ))$, and its contraction factor $\Vert I-\mu A{H}_{\mu }^{-1}{A}^{\top }\Vert =O(1/\mu )$ governs the linear rate; increasing $\mu$ (up to a practical ceiling) accelerates the dual without the primal ever needing $\mu \to \infty$.

Inequalities, the proximal-point reading, and the dual functional

Inequalities $c_i(x)\ge 0$ enter through Rockafellar's shifted penalty, whose augmented term $-\frac{1}{2\mu }([{\lambda }_i-\mu c_i(x){]}^{+}{}^2-{\lambda }_i^2)$ is once-continuously-differentiable and whose multiplier update is the projection ${\lambda }_{i,k+1}=[{\lambda }_{i,k}-{\mu }_k{c}_i(x_k){]}^{+}$, keeping $\lambda ⪰0$ automatically. The deepest structural identity is the proximal-point interpretation: the method of multipliers on the primal is exactly the proximal-point algorithm applied to the (concave) dual functional $g(\lambda )={\min }_{x}L(x,\lambda )$ of 44.02.01. Each multiplier update solves ${\lambda }_{k+1}=\arg {\max }_{\lambda }\{g(\lambda )-\frac{1}{2\mu }\Vert \lambda -{\lambda }_k{\Vert }^2\}$, the proximal step on $-g$ with parameter $1/\mu$, so the penalty parameter is the inverse of the proximal regularization weight ^{[Bertsekas Ch. 3]}. Convergence of the dual iteration is then the standard proximal-point convergence on a concave function: monotone in dual value, globally convergent for convex programs, and locally linearly convergent at a rate set by the curvature of $g$ near ${\lambda }^{\star }$ — which under the second-order sufficient conditions is precisely $-A^{\star }({\nabla }_{xx}^{2}L{)}^{-1}{A}^{\star \top }$ on the relevant subspace, the dual Hessian whose conditioning the proximal term tames.

LANCELOT and the splitting variant ADMM

The production form is the bound-constrained augmented-Lagrangian framework of LANCELOT: introduce slacks to turn general constraints into equalities plus simple bounds, minimize the augmented Lagrangian subject only to the bounds by a gradient-projection / trust-region inner solver, then perform the multiplier update and, only if the feasibility residual fails to shrink by a prescribed factor, increase $\mu$ ^{[Nocedal & Wright §17.4]}. Inner solves are inexact — terminated when the projected-gradient norm falls below a tolerance ${\tau }_k\to 0$ — and the outer loop's global convergence holds under MFCQ with the multiplier sequence bounded. The same augmented function admits an operator-splitting variant when the problem is separable, $\min f(x)+g(z)$ subject to $Ax+Bz=c$: minimizing $L_A$ jointly over $(x,z)$ is replaced by alternating minimizations over $x$ and then $z$, followed by the multiplier update — the alternating direction method of multipliers, which trades the exact joint primal solve for two cheaper subproblems while keeping the bounded-penalty multiplier logic intact.

Synthesis. The penalty principle is exactly the conversion of a constrained program into a sequence of unconstrained ones, and the central insight of this unit is that the naive quadratic penalty pays for feasibility with an $\Theta (\mu )$ condition number — a single inflated curvature on $\mathrm{range}{A}^{\top }$ in the null-space / range-space split of the KKT system from 44.02.02 — so the parameter that forces obedience is the same parameter that wrecks the conditioning. The foundational reason the augmented Lagrangian escapes this is that it carries the multiplier explicitly and updates it by ${\lambda }_{k+1}={\lambda }_k-\mu c(x_k)$, which is dual to the primal penalty: the multiplier shift pre-cancels the gradient the penalty would otherwise generate by brute force, so a bounded $\mu$ above the reduced-Hessian threshold makes $x^{\star }$ a strict minimizer and keeps every subproblem well-scaled. Putting these together, the multiplier iteration generalises the dual function of 44.02.01 into a convergent algorithm: it is the proximal-point method on that dual, with $1/\mu$ the proximal weight, and its contraction factor $O(1/\mu )$ is governed by the second-order sufficient conditions of 44.02.02. This is exactly the engine that appears again in LANCELOT's bound-constrained outer loop, in SQP globalization where the augmented Lagrangian and the exact ${\ell }_1$ penalty serve as merit functions (with the Maratos effect as the nonsmooth obstruction a second-order correction repairs), and in the operator-splitting ADMM of 44.06.04, where the same augmented function and multiplier update are minimized blockwise rather than jointly.

Full proof set Master

Proposition 1 (quadratic-penalty convergence to a KKT point). Let $x_k$ approximately minimize $Q(\cdot ;{\mu }_k)$ with $\Vert {\nabla }_{x}Q(x_k;{\mu }_k)\Vert \le {\tau }_k\to 0$ and ${\mu }_k\to \infty$, and let $x_k\to x^{\star }$ with LICQ at $x^{\star }$. Then $x^{\star }$ is feasible and KKT, with ${\lambda }^{\star }={\lim }_k{\mu }_{k}c(x_k)$.

Proof. From ${\nabla }_{x}Q(x_k;{\mu }_k)=\nabla f(x_k)+A(x_k{)}^{\top }({\mu }_{k}c(x_k))=r_k$, $\Vert r_k\Vert \le {\tau }_k$, write ${\ell }_k:={\mu }_{k}c(x_k)$. LICQ gives $A(x^{\star })$ full row rank, so $A(x_k)A(x_k{)}^{\top }$ is nonsingular for large $k$; left-multiplying $A(x_k{)}^{\top }{\ell }_k=r_k-\nabla f(x_k)$ by $A(x_k)$ and inverting, ${\ell }_k=(A(x_k)A(x_k{)}^{\top }{)}^{-1}A(x_k)(r_k-\nabla f(x_k))$. The right side converges (continuity, $r_k\to 0$) to ${\lambda }^{\star }:=-(A^{\star }{A}^{\star \top }{)}^{-1}{A}^{\star }\nabla f(x^{\star })$, finite. Since ${\ell }_k={\mu }_{k}c(x_k)$ is bounded and ${\mu }_k\to \infty$, $c(x_k)={\ell }_k/{\mu }_k\to 0$, so $c(x^{\star })=0$ (feasibility). Taking $k\to \infty$ in $\nabla f(x_k)+A(x_k{)}^{\top }{\ell }_k=r_k$ gives $\nabla f(x^{\star })+A(x^{\star }{)}^{\top }{\lambda }^{\star }=0$ (stationarity). Feasibility plus stationarity with these multipliers is the KKT system of 44.02.02. $\square$

Proposition 2 (penalty-Hessian conditioning). Near $x^{\star }$ with LICQ, $\kappa ({\nabla }_{xx}^{2}Q(x_k;{\mu }_k))=\Theta ({\mu }_k)$.

Proof. ${\nabla }_{xx}^{2}Q={\nabla }^{2}f(x)+\mu {\sum }_i{c}_i(x){\nabla }^2{c}_i(x)+\mu A(x{)}^{\top }A(x)$. As ${\mu }_k{c}_i(x_k)\to {\lambda }_i^{\star }$, the middle term is bounded; abbreviate $W={\nabla }^{2}f+\mu {\sum }_i{c}_i{\nabla }^2{c}_i\to {\nabla }_{xx}^{2}L(x^{\star },{\lambda }^{\star })$ (bounded, symmetric). Let $A=A(x^{\star })$ have singular values ${\sigma }_1\ge \cdots \ge {\sigma }_m>0$ (LICQ) and let $Z$ be an orthonormal basis of $\ker A$. For $z=Zw\in \ker A$: $z^{\top }{\nabla }_{xx}^{2}Qz=z^{\top }Wz=\Theta (\Vert z{\Vert }^2)$ since $Z^{\top }WZ\to Z^{\top }{\nabla }_{xx}^{2}LZ$, bounded with bounded inverse on the relevant cone. For $y\in \mathrm{range}{A}^{\top }$ with $\Vert y\Vert =1$: $y^{\top }{\nabla }_{xx}^{2}Qy=y^{\top }Wy+\mu \Vert Ay{\Vert }^2\ge \mu {\sigma }_m^2-\Vert W\Vert =\Theta (\mu )$, and $\le \Vert W\Vert +\mu {\sigma }_1^2=\Theta (\mu )$. By the min-max characterization the largest eigenvalue of ${\nabla }_{xx}^{2}Q$ is $\Theta (\mu )$ and the smallest is $\Theta (1)$, so $\kappa =\Theta (\mu )$. $\square$

Proposition 3 (${\ell }_1$ exactness). Let $x^{\star }$ be a KKT point with multipliers ${\lambda }^{\star }$ satisfying the second-order sufficient conditions. For every $\mu >\Vert {\lambda }^{\star }{\Vert }_{\infty }$, $x^{\star }$ is a strict local minimizer of ${\varphi }_1(x;\mu )=f(x)+\mu \Vert c(x){\Vert }_1$.

Proof. Write $x=x^{\star }+d$. Stationarity gives $\nabla f(x^{\star })=A^{\star \top }{\lambda }^{\star }$, so $f(x)-f(x^{\star })={\lambda }^{\star \top }c(x)+\frac{1}{2}{d}^{\top }{\nabla }_{xx}^{2}L(x^{\star },{\lambda }^{\star })d+o(\Vert d{\Vert }^2)$ (Taylor, with $c(x^{\star })=0$ absorbing the gradient via the Lagrangian). Then

$${\varphi }_1(x;\mu )-{\varphi }_1(x^{\star };\mu )=\mu \Vert c(x){\Vert }_1+{\lambda }^{\star \top }c(x)+\frac{1}{2}{d}^{\top }{\nabla }_{xx}^{2}Ld+o(\Vert d{\Vert }^2).$$

Since $|{\lambda }^{\star \top }c(x)|\le \Vert {\lambda }^{\star }{\Vert }_{\infty }\Vert c(x){\Vert }_1$, the first two terms are $\ge (\mu -\Vert {\lambda }^{\star }{\Vert }_{\infty })\Vert c(x){\Vert }_1\ge 0$. Decompose $d=d_T+d_N$ with $d_T\in \ker A^{\star }$, $d_N\in \mathrm{range}{A}^{\star \top }$. If $d_N=0$ then $c(x)=O(\Vert d{\Vert }^2)$, the constraint terms are $O(\Vert d{\Vert }^2)$, and $\frac{1}{2}{d}^{\top }{\nabla }_{xx}^{2}Ld\ge \frac{c_0}{2}\Vert d{\Vert }^2$ by second-order sufficiency on $\ker A^{\star }$, so the total is $\ge (\frac{c_0}{2}-o(1))\Vert d{\Vert }^2>0$. If $d_N\ne 0$ then $\Vert c(x){\Vert }_1\ge \frac{{\sigma }_m}{2}\Vert d_N\Vert$ for small $d$, and $(\mu -\Vert {\lambda }^{\star }{\Vert }_{\infty })\Vert c(x){\Vert }_1=\Theta (\Vert d_N\Vert )$ dominates the $O(\Vert d{\Vert }^2)$ curvature remainder. In both cases ${\varphi }_1(x;\mu )>{\varphi }_1(x^{\star };\mu )$ for $0<\Vert d\Vert$ small. $\square$

Proposition 4 (strict minimizer of $L_A$ at finite $\mu$). Let $(x^{\star },{\lambda }^{\star })$ be a KKT point with $A^{\star }=A(x^{\star })$ full row rank and reduced-Hessian positive definiteness $Z^{\top }{\nabla }_{xx}^{2}LZ\succ 0$. There is $\bar{\mu }<\infty$ such that for all $\mu >\bar{\mu }$, $x^{\star }$ is a strict local minimizer of $x\mapsto L_A(x,{\lambda }^{\star };\mu )$.

Proof. ${\nabla }_x{L}_A(x^{\star },{\lambda }^{\star };\mu )=\nabla f(x^{\star })-A^{\star \top }{\lambda }^{\star }+\mu A^{\star \top }c(x^{\star })=0$ (KKT stationarity, $c(x^{\star })=0$). The Hessian is $M(\mu )={\nabla }_{xx}^{2}L(x^{\star },{\lambda }^{\star })+\mu A^{\star \top }{A}^{\star }$ (the $\mu \sum c_i{\nabla }^2{c}_i$ term vanishes since $c(x^{\star })=0$). Claim: $M(\mu )\succ 0$ for $\mu$ large. Suppose not for a sequence ${\mu }_j\to \infty$: there are $\Vert v_j\Vert =1$ with $v_j^{\top }M({\mu }_j)v_j\le 0$, i.e. $v_j^{\top }{\nabla }_{xx}^{2}L{v}_j+{\mu }_j\Vert A^{\star }{v}_j{\Vert }^2\le 0$. The first term is bounded, so $\Vert A^{\star }{v}_j{\Vert }^2\le -v_j^{\top }{\nabla }_{xx}^{2}L{v}_j/{\mu }_j\to 0$; passing to a subsequence $v_j\to v$, $\Vert v\Vert =1$, $A^{\star }v=0$, so $v\in \ker A^{\star }$. But then $v^{\top }{\nabla }_{xx}^{2}Lv=\lim v_j^{\top }{\nabla }_{xx}^{2}L{v}_j\le 0$ contradicts $Z^{\top }{\nabla }_{xx}^{2}LZ\succ 0$. Hence $M(\mu )\succ 0$ for $\mu >\bar{\mu }$, and with ${\nabla }_x{L}_A=0$ the point $x^{\star }$ is a strict local minimizer. $\square$

Proposition 5 (method-of-multipliers local linear convergence, bounded $\mu$). Under the hypotheses of Proposition 4 with exact inner minimization, the multiplier iteration ${\lambda }_{k+1}={\lambda }_k-\mu c(x({\lambda }_k))$ converges to ${\lambda }^{\star }$ linearly with factor $O(1/\mu )$ for every fixed $\mu >\bar{\mu }$.

Proof. For $\lambda$ near ${\lambda }^{\star }$ and $\mu >\bar{\mu }$, $x(\lambda )=\arg {\min }_x{L}_A(x,\lambda ;\mu )$ is well-defined and $C^1$ by the implicit function theorem applied to ${\nabla }_x{L}_A(x,\lambda ;\mu )=0$, whose Jacobian $H_{\mu }={\nabla }_{xx}^{2}L+\mu A^{\top }A=M(\mu )$ is nonsingular. Implicit differentiation gives $H_{\mu }{x}^{\prime }(\lambda )=A^{\top }$ (differentiating $\nabla f-A^{\top }\lambda +\mu A^{\top }c=0$ in $\lambda$, to leading order at $x^{\star }$), so $x^{\prime }(\lambda )=H_{\mu }^{-1}{A}^{\top }$ and $\frac{d}{d\lambda }c(x(\lambda ))=A{x}^{\prime }(\lambda )=A{H}_{\mu }^{-1}{A}^{\top }$. The update map $T(\lambda )=\lambda -\mu c(x(\lambda ))$ has Jacobian $T^{\prime }({\lambda }^{\star })=I-\mu A{H}_{\mu }^{-1}{A}^{\top }$. With $H_{\mu }={\nabla }_{xx}^{2}L+\mu A^{\top }A$, the matrix-inversion lemma gives $\mu A{H}_{\mu }^{-1}{A}^{\top }=I-(I+\mu A({\nabla }_{xx}^{2}L{)}^{-1}{A}^{\top }{)}^{-1}$ on the range of $A$ (where ${\nabla }_{xx}^{2}L$ is invertible on the relevant subspace), so $T^{\prime }({\lambda }^{\star })=(I+\mu A({\nabla }_{xx}^{2}L{)}^{-1}{A}^{\top }{)}^{-1}$, whose spectral radius is $O(1/\mu )$ as $\mu \to \infty$ and is $<1$ for $\mu >\bar{\mu }$. Hence $T$ is a local contraction and ${\lambda }_k\to {\lambda }^{\star }$ linearly with factor $\Vert T^{\prime }({\lambda }^{\star })\Vert =O(1/\mu )$. $\square$

Connections Master

• The KKT optimality theory of 44.02.02 is the direct parent: the quadratic penalty recovers the KKT multiplier only in the limit $\mu c(x_k)\to {\lambda }^{\star }$, the augmented Lagrangian carries that multiplier explicitly and its update is exactly KKT stationarity at the current iterate, and the second-order sufficient conditions of that unit are the precise hypotheses under which $x^{\star }$ is a strict minimizer of $L_A$ at finite $\mu$ and the multiplier iteration is locally linearly convergent. The null-space / range-space split of the KKT system there is what localizes the $\Theta (\mu )$ ill-conditioning of the penalty Hessian to $\mathrm{range}{A}^{\top }$.

• The Lagrangian-duality theory of 44.02.01 supplies the dual reading: the method of multipliers is the proximal-point algorithm on the concave dual function $g(\lambda )={\min }_{x}L(x,\lambda )$, with the penalty parameter $\mu$ the inverse of the proximal regularization weight, so each multiplier update maximizes $g(\lambda )-\frac{1}{2\mu }\Vert \lambda -{\lambda }_k{\Vert }^2$. The bounded-penalty guarantee and the global convergence for convex programs are exactly the proximal-point convergence theory applied to that dual, and the optimal multipliers are the sensitivities established in that unit.

• The alternating direction method of multipliers 44.06.04 is the operator-splitting variant: for a separable objective $f(x)+g(z)$ with coupling $Ax+Bz=c$, ADMM replaces the joint primal minimization of the augmented Lagrangian by alternating minimizations over $x$ and $z$, then performs the same multiplier update ${\lambda }_{k+1}={\lambda }_k-\mu (A{x}_{k+1}+B{z}_{k+1}-c)$. The augmented function, the bounded penalty parameter, and the dual-ascent interpretation developed here are precisely what ADMM inherits; ADMM trades exactness of the joint solve for two cheaper subproblems, gaining decomposability at the cost of a slower (but still robust) convergence rate.

• Sequential quadratic programming 44.04.03 is the principal consumer of the penalty machinery as a merit function: SQP computes a step from a QP subproblem and must decide whether to accept it, using either the nonsmooth exact ${\ell }_1$ penalty or the augmented Lagrangian as the merit function whose decrease certifies progress. The Maratos effect identified here — a good step rejected because it increases the merit function near the solution — is the obstruction SQP globalization must defeat with a second-order correction, watchdog, or augmented-Lagrangian merit, to preserve the fast local rate that the QP step would otherwise deliver.

Historical & philosophical context Master

The penalty idea is old, going back to Courant's 1943 suggestion of replacing constraints by quadratic violation terms, but the modern theory of penalty and augmented-Lagrangian methods crystallized in the late 1960s. The decisive step was taken independently by Magnus Hestenes and Michael J. D. Powell in 1969. Hestenes, working in the calculus-of-variations tradition at UCLA, introduced the multiplier-and-penalty function and the multiplier update in Multiplier and Gradient Methods ^{[Hestenes 1969]} (Journal of Optimization Theory and Applications 4, 303-320); Powell, at Harwell, gave the same construction with a numerical emphasis in A Method for Nonlinear Constraints in Minimization Problems ^{[Powell 1969]} (in Optimization, ed. Fletcher). The shared insight — augment the Lagrangian with a quadratic penalty and update the multipliers from the constraint residual so the penalty parameter need not diverge — gave the method its alternative name, the method of multipliers.

The theory was unified and extended through the 1970s, principally by R. Tyrrell Rockafellar, who recognized the multiplier iteration as the proximal-point algorithm applied to the dual and handled inequality constraints by the shifted-penalty form, and by Dimitri Bertsekas, whose 1982 monograph Constrained Optimization and Lagrange Multiplier Methods ^{[Bertsekas 1982]} became the standard reference for the convergence theory under second-order sufficiency and the dual rate analysis. The nonsmooth exact ${\ell }_1$ penalty and the diagnosis of the Maratos effect (N. Maratos's 1978 thesis) belong to the same period and shaped the merit-function design of sequential quadratic programming. The production realization is the LANCELOT package of Andrew Conn, Nicholas Gould, and Philippe Toint, which built the bound-constrained augmented-Lagrangian framework into large-scale software, and the operator-splitting descendant ADMM, traced to Glowinski-Marrocco and Gabay-Mercier in the mid-1970s, re-emerged as a workhorse of large-scale and distributed convex optimization.

Bibliography Master

@book{nocedalwright2006penalty,
  author    = {Nocedal, Jorge and Wright, Stephen J.},
  title     = {Numerical Optimization},
  edition   = {2},
  series    = {Springer Series in Operations Research and Financial Engineering},
  publisher = {Springer},
  year      = {2006}
}

@book{bertsekas1982constrained,
  author    = {Bertsekas, Dimitri P.},
  title     = {Constrained Optimization and Lagrange Multiplier Methods},
  publisher = {Academic Press},
  address   = {New York},
  year      = {1982},
  note      = {Reprinted by Athena Scientific, 1996}
}

@article{hestenes1969multiplier,
  author  = {Hestenes, Magnus R.},
  title   = {Multiplier and Gradient Methods},
  journal = {Journal of Optimization Theory and Applications},
  volume  = {4},
  number  = {5},
  pages   = {303--320},
  year    = {1969}
}

@incollection{powell1969method,
  author    = {Powell, Michael J. D.},
  title     = {A Method for Nonlinear Constraints in Minimization Problems},
  booktitle = {Optimization},
  editor    = {Fletcher, Roger},
  pages     = {283--298},
  publisher = {Academic Press},
  address   = {London},
  year      = {1969}
}

@article{rockafellar1973multiplier,
  author  = {Rockafellar, R. Tyrrell},
  title   = {A Dual Approach to Solving Nonlinear Programming Problems by Unconstrained Optimization},
  journal = {Mathematical Programming},
  volume  = {5},
  number  = {1},
  pages   = {354--373},
  year    = {1973}
}

@article{rockafellar1976augmented,
  author  = {Rockafellar, R. Tyrrell},
  title   = {Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming},
  journal = {Mathematics of Operations Research},
  volume  = {1},
  number  = {2},
  pages   = {97--116},
  year    = {1976}
}

@article{conn1991lancelot,
  author  = {Conn, Andrew R. and Gould, Nicholas I. M. and Toint, Philippe L.},
  title   = {A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds},
  journal = {SIAM Journal on Numerical Analysis},
  volume  = {28},
  number  = {2},
  pages   = {545--572},
  year    = {1991}
}

@article{gabay1976dual,
  author  = {Gabay, Daniel and Mercier, Bertrand},
  title   = {A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation},
  journal = {Computers \& Mathematics with Applications},
  volume  = {2},
  number  = {1},
  pages   = {17--40},
  year    = {1976}
}