Why an inequality needs a different penalty
An equality residual should tend to zero. An inequality residual need only become nonpositive: strictly negative values represent permissible slack. Squaring the entire residual treats slack as an error and can change the optimization problem. A multiplier for an inequality must also remain nonnegative under our convention . Copying the equality update without enforcing its sign can destroy the lower-bound meaning of the dual problem.
The positive-part augmented Lagrangian respects both distinctions. Its multiplier update is a Euclidean projection onto the nonnegative orthant. We will derive the formula, prove that exact minimization implements a proximal step on the constrained dual problem, and establish convergence in a finite smooth convex model. The theorem includes attainment and qualification hypotheses; it is not an assertion about arbitrary nonconvex problems or approximate inner solvers.
The model and the standing assumptions
Consider
Assume are finite, continuously differentiable convex functions on ; the finite primal minimum is attained; and a strictly feasible point exists with every . The Slater theorem, proved in the unit on separation, subgradients and strong duality, then supplies at least one attained dual maximizer with . Equivalently, the convergence proof below may start from primal and dual attainment with zero gap; strict feasibility is a sufficient route to those facts. It is not used to assert existence of the inner minimizers.
Fix , take , and additionally assume that every inner problem used below attains its minimum. This is automatic, for example, if is coercive: the augmented objective is bounded below by , is continuous, and therefore has bounded sublevel sets and attains its infimum. A bounded sequence of selected primal minimizers will be an extra hypothesis only when we discuss their accumulation and distance to the solution set.
Definition 11.2.1
(Positive-part augmented Lagrangian and the exact outer iteration)
For a vector , write for componentwise . For and , define
An exact outer iteration chooses any
The fixed parameter need not grow to infinity in the theorem. Each iteration still requires an exact attained minimizer; computational convenience does not replace that assumption.
Deriving the positive part from a maximization
For fixed , complete a square in :
Over the unique maximizer is , the projection of onto the orthant. Coordinatewise substitution gives
Indeed, if , its contribution is ; otherwise the maximum is . The two values and their first derivatives agree at . Consequently is continuously differentiable in with gradient . It is convex and nondecreasing in each coordinate of . Alternatively, the displayed maximum makes the pointwise supremum of convex functions minus constants. Thus is convex, and its gradient is
At an exact inner minimizer this gradient vanishes. Defining by the projected update makes a stationary point of the ordinary convex Lagrangian , so it is its global minimizer. In particular,
This is the bridge from primal minimization to the dual function. Merely computing the projection without minimizing the inner objective would not establish this equality.
Concept lensStructural
Projection is the sign constraint's optimality condition
For and any , Euclidean projection gives
This is the inequality replacing the equality-residual identity of the equality-constrained method in the unit on exact penalties and augmented Lagrangians. If , the update has . If , the constraint can be strictly slack and that equality need not hold. The projection inequality remains valid in both cases and supplies the sign needed in the convergence proof.
The exact proximal-dual identity
Theorem 11.2.2
(An exact inner solve gives a unique proximal dual step)
Let minimize under the convex differentiable assumptions above, with and . Then is the unique maximizer of
All choices of exact primal minimizer therefore produce the same next multiplier, although their primal coordinates may differ.
Proof
(Combine the definition of the dual function with the projection inequality)
For any , the definition of and exact stationarity give
Subtract and expand the square. The result is the stronger bound
Thus maximizes the proximal expression, and any other point has strictly smaller value unless it equals . If , the inequality is immediate. There is no unproved exchange of an infimum and a maximum: the proof constructs a primal-dual pair and verifies its global inequalities directly.
Exact convergence and its scope
Theorem 11.2.3
(Fixed-parameter inequality augmented-Lagrangian convergence)
Under the standing assumptions and exact attained inner minimization, converges to a dual maximizer, , and . Also for every . Every accumulation point of the selected primal sequence is primal optimal. If this sequence is bounded, accumulation points exist and its distance to the primal solution set tends to zero. If that set is a singleton, the bounded primal sequence converges to its element.
The proof has two parts: the multipliers are handled first, and the primal conclusions are then read off from them.
A distance inequality for the dual iterates
Proof
(Part one: the multipliers converge to a dual maximizer)
Put , and . Apply the inequality before completing the square with and . It gives
The squared-distance identity then gives
The squared increment is nonnegative, and the dual gap is nonnegative by weak duality. Distances to any dual optimum are nonincreasing, so the multipliers are bounded. Summing from to gives
Consequently and the dual gaps tend to zero. In finite dimensions a bounded multiplier sequence has a convergent subsequence. The dual function is upper semicontinuous because it is the infimum of affine continuous functions of its argument. Its value at the subsequential limit is therefore at least , and weak duality makes that limit dual optimal. The same distance inequality applies with this particular limit as . Those distances are nonincreasing and have a subsequence tending to zero, so the whole multiplier sequence converges to that limit.
Recovering feasibility, complementarity and the objective
Proof
(Part two: feasibility, complementarity and primal limits)
The full vector need not tend to zero. Instead, if , the current nonnegative multiplier makes , so
This proves vanishing positive-part violation. Moreover, when we have , and when both products below are zero. Thus the exact identity
holds in every coordinate. Bounded multipliers and give componentwise asymptotic complementarity and . Since , objective convergence follows. This proof avoids trying to bound the negative slack itself.
If a primal subsequence converges to , continuity gives and . Under boundedness, if distances to the closed solution set did not tend to zero, a subsequence staying at distance at least some would have a convergent further subsequence with an optimal limit, a contradiction. Uniqueness then forces primal convergence. Without boundedness, none of these compactness steps manufactures an accumulation point.
Proof X-ray
Where exactness, the sign constraint and compactness enter
Exact inner stationarity identifies with the Lagrangian value at the selected primal point; this enables the proximal and distance inequalities. The sign constraint enters only through the projection inequality, which is an inequality rather than the equality of the equality-constrained case; it still points the right way to give . The distance inequality then does all the dual work: monotone distances bound the multipliers, and the telescoped sums force and the dual gaps to zero. Every primal conclusion is read off from through the two coordinate identities and , so no control of the negative slack is ever needed. Finite-dimensional compactness is used first on bounded multipliers to obtain an optimal limit. It is used separately on primal points only if they are bounded. An objective limit and vanishing constraint violation do not control arbitrary motion along directions that leave both unchanged.
The last sentence of the X-ray is not a technicality, as an example with a flat direction shows.
Worked example 11.2.4
(Optimal values along an unbounded primal sequence)
Let and . Strict feasibility holds everywhere and the primal solutions are all . Start . At multiplier zero, , so the augmented objective is , independent of , and every is an exact inner minimizer. Select at step . The projected multiplier stays , the objective is the optimal value , and there is no violation, yet the primal sequence is unbounded and has no accumulation point. This satisfies the theorem, whose primal conclusions are conditional on boundedness, and illustrates why that separate condition appears.
Worked examples and failure checks
Worked example 11.2.5
(An active inequality and a fixed penalty parameter)
Minimize subject to . The solution is , , and the optimal multiplier is one. Inner stationarity gives , while . For , , the consistent branch is
Hence . With and , the first two pairs are and . Early inner solutions are infeasible, but violation tends to zero and objective tends to . A finite fixed suffices because the multiplier changes.
Worked example 11.2.6
(An inactive constraint makes a multiplier decrease)
Minimize subject to , with and . Inner stationarity is . At the first step the positive branch gives and ; it is consistent since . At the second step and , exactly at the branch transition. Thereafter . The residual stays strictly negative, as it should: the constraint is inactive at the optimum. Complementarity holds because its multiplier vanishes.
Counterexample mode
Squaring slack solves a different problem
For the inactive example, replacing the inequality by the equality-style quadratic penalty at , minimizes at , instead of the original optimum . If one also uses the unrestricted equality multiplier update, then and . Starting at zero gives , an illegal inequality multiplier, and , the equality-constrained solution with objective . The original inequality optimum has objective zero. The positive-part formula and projection repair both mistakes.
Strict feasibility cannot simply be dropped while retaining the theorem's attained-dual premise. Minimize subject to . The primal value zero is attained, but for , , while . The dual supremum is zero and is not attained at any finite multiplier. There is no to anchor the distance argument. This is a failure of its hypotheses, not a contradiction of the theorem.
Honest stopping criteria for inner solves
At a proposed inner point , form . The computable stationarity residual is
The exact proof used . Two tempting stopping rules do not supply it.
Common mistake
(Stopping on zero violation and zero multiplier change)
Primal violation and multiplier change alone do not imply . In the inactive scalar example with , repeatedly choosing gives zero violation and zero multiplier change forever, but objective rather than zero and .
Common mistake
(Treating a fixed inner tolerance as exact minimization)
Even a fixed small positive gradient tolerance does not imply exact asymptotic optimization. For any , repeatedly choose with . This is strictly feasible and its projected next multiplier is zero; its inner gradient is , below tolerance . The constant objective gap is nevertheless . Declaring exact convergence from this stopping rule would be false.
A valid bounded inner certificate is possible with additional information. If is known to be -strongly convex, , then for its exact minimizer the supporting quadratic inequality gives
To see this, lower-bound by and minimize the right side over . This is an inner objective-error certificate, not a proof that an outer method with arbitrary errors converges. A full inexact theorem must specify how errors decrease or accumulate and how they perturb the dual inequalities. Such a theorem is outside the exact method proved here.
Exercises
Quick check
(For , and , compute and directly and from the maximization formula.)
Evaluate both expressions and compare.
Solution
, so . The positive-part formula gives . In the maximization expression, and , so the value is ; coordinatewise projection proves it is the maximum.
Quick check
(In the active scalar example, take and . Find and check that a feasible inner point can have positive multiplier.)
Use the consistent positive branch derived in that example.
Solution
, , then , . Both primal points satisfy the inequality strictly although the multipliers are positive. Complementary slackness is a condition at the limiting optimum, not a requirement at each intermediate inner solution. Indeed .
Quick check
(If , use the distance inequality to bound the smallest squared positive-part violation among the first primal points. Is this a last-iterate rate?)
Combine the summed increments with .
Solution
Summability gives . Since , the smallest squared violation is at most . This is a best-iterate bound. The proof establishes convergence of the full violations, but this averaging argument does not establish a last-iterate bound.
Quick check
(If a -strongly convex inner objective has gradient residual norm at most , what objective-error bound follows? Does a fixed such bound prove exact outer convergence?)
Use the strong-convexity certificate.
Solution
The gap is at most . This bounds one inner solve's objective error. Repeating a fixed tolerance does not establish exact outer convergence, as the scalar counterexample shows; an inexact outer theorem needs explicit additional error conditions.
Quick check
(In the inactive scalar example with , start from . Find and .)
Try the positive branch first and check whether it is consistent.
Solution
Inner stationarity is . The positive branch gives , but then , so the branch is inconsistent. The zero branch gives , so , and indeed ; hence . One exact step reaches the optimal pair : the zero branch is consistent whenever , so any starting multiplier on this inactive constraint is discarded in one step.