Motivation
Constraints can be enforced by rejecting infeasible points, but this is not the only strategy. A penalty charges for violating a constraint and lets an unconstrained solver explore infeasible points. A quadratic penalty becomes increasingly severe as its parameter grows, yet a finite parameter may leave a nonzero violation. An exact nonsmooth penalty can instead reproduce the constrained solution at a finite parameter, provided the penalty dominates an optimal multiplier.
The augmented Lagrangian combines a multiplier with a quadratic penalty. Its multiplier update is not an arbitrary correction: in a convex equality-constrained problem it is a proximal step on the dual objective. We derive this identity and prove convergence for exact, attained subproblem solutions. Approximate solves are important in practice, but the proof below does not silently extend to unspecified errors or stopping tolerances.
Definitions
Consider the equality-constrained problem
where is convex and continuously differentiable and . Write . Its Lagrange dual function is
Throughout the main results suppose a primal minimizer and a dual maximizer exist, their common value is finite, so there is no duality gap. Weak duality holds in general. These assumptions are explicit; convexity alone does not ensure attainment.
Definition 11.1.1
(Augmented Lagrangian, exact penalty and the method of multipliers)
For and , define the augmented Lagrangian and exact-penalty objective
Given , the exact method of multipliers chooses a global minimizer of and sets
Write . We assume every such subproblem has a minimizer. It need not be unique. The formula uses the residual of the chosen minimizer and a fixed ; it does not require taking to infinity. The order matters: first minimize using the old multiplier, then calculate the residual and update the multiplier. Reversing those operations or using a different residual defines a different iteration, for which the following stationarity identity must be established again.
Theorem/Proposition
Theorem 11.1.2
(An exact penalty from a dual optimum)
Under the stated primal and dual attainment and zero-gap assumptions, if , every global minimizer of is primal feasible and optimal, and every primal minimizer is a global minimizer of . At equality of the two constants, infeasible penalty minimizers may exist.
Theorem 11.1.3
(Exact augmented-Lagrangian convergence)
Under the same assumptions and assuming every augmented subproblem is solved exactly with an attained minimizer, the method of multipliers has for some dual optimum, , and . Every accumulation point of the primal sequence is feasible and primal optimal. The theorem does not assert that the primal sequence is bounded or converges when minimizers are nonunique.
Proof sketch or proof idea
Why the absolute penalty can be exact
Proof
(Weak duality and Hölder's inequality)
Dual optimality means for every . Hölder's inequality therefore gives
At any primal minimizer the residual is zero and . When the coefficient is strictly positive, every infeasible point has penalty value strictly above , so all penalty minimizers are feasible and optimal. The inequality also proves existence of a penalty minimizer because a primal minimizer is already given. This is a global statement about the exact objective; a local minimizer of the penalty may require a separate analysis, as may an approximate numerical minimizer.
For the augmented-Lagrangian theorem, the proof first identifies the multiplier update and then studies the multipliers alone.
The multiplier update is a dual proximal step
Proof
(Part one: exact stationarity makes the update a proximal step)
At an exact subproblem minimizer, differentiability and convexity give
Consequently globally minimizes the ordinary Lagrangian at , and . For every , taking the infimum at the same point gives the supergradient inequality
Since , completing the square shows that uniquely maximizes
Indeed the supergradient inequality bounds the difference from the value at by . To see the cancellation explicitly, set and . The supergradient term contributes , while expanding the quadratic penalty contributes . Their cross terms cancel. This proves the proximal interpretation directly, including uniqueness of the next multiplier even when the primal subproblem has several minimizers.
Fejér inequality and convergence
Proof
(Part two: Fejér monotonicity and convergence)
Apply the supergradient inequality with and use . Expanding squared distances yields
Both terms on the right are nonnegative by weak duality. Summing shows the multiplier sequence is bounded, the squared multiplier increments are summable, and the nonnegative dual gaps are summable. Therefore , so , and .
In finite dimensions, bounded multipliers have a convergent subsequence. The dual function is upper semicontinuous because it is the infimum of continuous affine functions of . Thus the subsequential limit is dual optimal: its value is at least the limit superior and at most by weak duality. The same distance inequality holds with this limit in place of ; distances to it are nonincreasing and a subsequence tends to zero, so the entire sequence tends to that dual optimum.
Finally, because multipliers are bounded and residuals vanish. If a primal subsequence converges, continuity of and makes its limit feasible with value . The proof does not produce a primal accumulation point; without a boundedness or coercivity assumption there may be none.
Proof X-ray
One identity, then multipliers only
The proof turns on a single identity. Exact stationarity of the inner problem at the old multiplier is rewritten as stationarity of the ordinary Lagrangian at the new multiplier ; this is where exactness and the order “minimize, then update” are used. Convexity enters once, to promote that stationary point to a global minimizer, which yields the supergradient inequality with supergradient . The update rule converts into the increment , and inserting gives Fejér monotonicity; the zero-gap assumption is what makes the gap term nonnegative. From there the argument concerns multipliers alone: boundedness, summable increments and hence vanishing residuals, and compactness with upper semicontinuity to identify the limit. Primal information returns only through . No step bounds the primal points, which is why their convergence is not claimed.
What inexactness changes
The exact stationarity equation is the bridge to the supergradient and proximal identities. A subproblem solved only to a fixed objective tolerance need not satisfy it, so the proof cannot simply omit the error. One may analyze inexact proximal steps with specified summable errors and suitable residual criteria, but the correct condition depends on how accuracy is measured. This section proves the exact method only; it does not assert that a fixed or unspecified inner tolerance inherits its convergence.
Why the multiplier changes the quadratic penalty
Concept lensStructural
The role of the multiplier
By the definition of and the zero-gap assumption , every satisfies the following inequality for the augmented objective:
A primal optimum attains equality. Thus every minimizer of is feasible and primal optimal, even with a fixed finite . This statement assumes that the correct multiplier is already known. The iteration is designed to approach a dual optimum without assuming that knowledge, and its proof above shows exactly what can be concluded along the way.
The scalar example makes the distinction concrete. With multiplier zero, the inner solution is the infeasible pure-penalty point . With multiplier one, the same fixed- subproblem is minimized at zero. The change comes from the linear multiplier term canceling the objective's first-order incentive to violate the equality. It is not that a finite quadratic term alone suddenly became exact.
Increasing the penalty and numerical conditioning
Making large can reduce a pure penalty's constraint violation, but it can also make the inner optimization more anisotropic. Consider and the equality . Its quadratic-penalty Hessian is , whose spectral condition number is . A solver that is sensitive to conditioning may require more work as grows. The multiplier method provides a different tradeoff: it can keep fixed while updating the linear term, although it still requires solving each subproblem to the accuracy demanded by the chosen convergence theorem.
Scaling the constraints changes the apparent numerical parameters. Replacing by with invertible preserves the feasible set, but a Euclidean quadratic penalty becomes , which weights residual directions differently. Multipliers transform accordingly: if multiplies the scaled residual, the original multiplier is . Penalty thresholds and conditioning should therefore be interpreted together with the chosen constraint normalization.
A computable check and its limitation
The update gives the identity , so the multiplier change directly measures equality violation. A small residual alone does not certify near-optimality: a feasible point can have arbitrarily high objective value. The exact inner stationarity equation adds a second check, . Under the assumptions of the theorem these properties accompany objective convergence; for an approximate implementation, the sizes and accumulation of both errors must be included in a separate analysis.
What the distance inequality quantifies
The Fejér inequality also gives finite-iteration bounds. Let . Summing its first instances and discarding the final squared distance gives
Thus at least one of the first residuals has squared norm at most , and at least one dual gap is at most . These may occur at different indices. These calculations establish bounds on the best iterate in each list; they do not establish a last-iterate rate. The stronger limit statements in the theorem follow from summability and finite-dimensional compactness, as shown above.
The proximal derivation also explains why the next multiplier is independent of which exact primal minimizer is chosen. Each such choice yields a candidate satisfying the same global quadratic upper bound on the proximal objective. Two different candidates would each have to be its unique maximizer, a contradiction. Their primal coordinates may nevertheless differ by nullspace directions, as the exercise below on exact subproblem minimizers illustrates.
Worked examples
Worked example 11.1.4
(A finite exact penalty and a sharp threshold)
Minimize subject to . The unique primal point has value zero and at (it is otherwise). For , is positive at every nonzero , so its unique minimum is zero. At the objective is zero for every ; infeasible minimizers exist. Thus strict inequality in the theorem matters.
Worked example 11.1.5
(A quadratic penalty is not generally exact)
Minimize subject to . The quadratic penalty has minimizer , nonzero for every finite . Increasing reduces the violation, but does not produce exact feasibility at a finite parameter. The original multiplier is .
Worked example 11.1.6
(Multiplier updates for a scalar equality)
For the same and , minimizing gives and . Hence , so the multiplier converges geometrically to one and the residual tends to zero for every . Unlike the pure quadratic penalty, the fixed- multiplier iteration approaches exact feasibility.
Common mistakes
The optimal multiplier controls a sufficient penalty threshold; an arbitrary multiplier does not give the same proof, and equality at the threshold can allow infeasible minimizers, as the first worked example shows.
Counterexample mode
A penalty threshold from a multiplier estimate
Claim: once the method of multipliers has produced an estimate , any makes the penalty exact. Take the scalar problem , , with and , so that , and choose . For the penalty has derivative , which vanishes at , where . The penalty minimizer is therefore infeasible. The repaired statement uses an optimal multiplier: here , and for the slopes on and on make the unique minimizer.
Two further mistakes concern the convergence theorem rather than the penalty.
Common mistake
(Treating a small residual as the convergence certificate)
The augmented subproblem must attain its minimum for the update as stated, and the convergence proof uses exact minimization, not merely a small residual. A feasible point can have an arbitrarily high objective value; the second check is what links the residual to optimality.
Common mistake
(Concluding that the primal iterates converge)
Dual convergence and feasibility do not by themselves imply convergence of a nonunique or unbounded primal sequence. When has a nontrivial nullspace on which is constant, exact inner minimizers can drift along it, as the exercise below on exact subproblem minimizers shows.
Summary
Weak duality turns an optimal multiplier into an exact penalty bound. Quadratic penalties alone need not be exact. In the convex equality setting, exact augmented-Lagrangian minimization produces a proximal dual step; its distance inequality gives multiplier convergence, feasibility and objective convergence. The assumptions include primal and dual attainment, zero gap, and exact attained inner solves.
Exercises
Quick check
(For and , describe all minimizers of when and when .)
Compare the slopes of on each side of zero.
Solution · Answer
At , is zero on and positive for , so every minimizes it. When , both slopes away from zero yield positive values and zero is the unique minimizer.
Quick check
(For , and , start . Compute .)
Use the recurrence from the scalar worked example.
Solution · Answer
The recurrence gives , , and . Each inner minimization uses the current multiplier, then updates it with .
Quick check
(Why does summability of imply feasibility in this algorithm but not necessarily convergence of the primal points?)
Relate the increment to the residual.
Solution
The update gives , so increments tending to zero force the residual to zero. This controls only , not motion in the nullspace of ; nonunique inner minimizers can move there.
Quick check
(Let and constrain . Explain why exact subproblem minimizers can be chosen to form an unbounded sequence even though residuals and objectives converge.)
Ask which coordinate the augmented objective depends on.
Solution
The augmented objective depends only on , so choose any minimizing and take . With , the exact minimizing first coordinate and all residuals are zero, as are the objective values, while the primal sequence is unbounded.