CorollaryStatement: AI-generatedProof: AI-adaptedPipeline-generatedprecheck pending

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The augmented-Lagrangian multiplier procedure preserves its domain and returns within its caps

Statement

On the admitted inputs of Finite-budget augmented-Lagrangian multiplier method, with finite positive integer caps $K, M$ , and with its supplied inner procedure satisfying its stated finite-iteration/report contract, the procedure terminates with one of inner-budget-exhausted, inner-failure, kkt-tolerance-reached, or outer-budget-exhausted. It performs at most $K M$ inner iterations and at most $K$ outer KKT residual tests. Every multiplier iterate satisfies $λ_{k} \geq 0$ , and every point used for a multiplier update or KKT test lies in the program domain $U$ .

A kkt-tolerance-reached return reports a KKT residual at most $τ$ at the returned primal point and updated multipliers, together with the achieved inner residual at most its declared $ϵ_{k}$ . An outer-budget-exhausted return includes the last reported inner and KKT residuals. An inner-budget-exhausted return retains the current outer state and the inner procedure's last point and residual; an inner-failure return preserves its declared failure data. None of these conclusions asserts that a tolerance will be reached, that an inner call will succeed within its cap, or that the finite procedure converges.

Facts & Assumptions

Given: The admitted $C^{2}$ program, finite positive integer caps $K, M$ , tolerances, initial state $x_{0} \in U$ , initial multipliers $ν_{0} \in R^{p}$ , $λ_{0} \in R_{+}^{m}$ , and the supplied finite inner-procedure contract.

[F1]

Finite-budget augmented-Lagrangian multiplier method calls the inner procedure at most once per outer index $k = 0, \dots, K - 1$ . A success supplies $x_{k}^{+} \in U$ and its achieved inner residual, and the algorithm rejects a purported success reporting residual above $ϵ_{k}$ . Inner budget or failure returns terminate the outer procedure immediately with their stated data.

[F2]

Equality and inequality augmented Lagrangians and multiplier updates defines $ν^{+} = ν + ρ h (x^{+})$ and $λ^{+} = [λ + ρ g (x^{+})]_{+}$ , where projection is componentwise maximum with zero.

[F3]

Scaled KKT residual and convex normal cone defines a finite sum of stationarity, primal feasibility, dual feasibility and complementarity residual norms at domain points and finite multipliers; zero-dimensional norms are zero.

[A1]

Every inner call performs at most $M$ inner iterations, each iteration and report computation is finite, and the call returns the residual or failure data prescribed by [F1]. The smooth program evaluations and finite-dimensional arithmetic used for each outer update and test are the admitted exact evaluations of that procedure.

Proof

1.1givenF1F2A1inductionalgebra

Initially $x_{0} \in U$ and $λ_{0} \geq 0$ . An inner failure or budget return stops before an update. Otherwise [F1] supplies $x_{k}^{+} \in U$ and checks its reported inner residual against $ϵ_{k}$ . The multiplier update in [F2] is therefore defined, and each component of $λ_{k + 1}$ is nonnegative. If the procedure continues, it sets $x_{k + 1} = x_{k}^{+} \in U$ . Induction proves the domain and multiplier assertions at every reached index, including when the equality or inequality multiplier space has dimension zero.

2.1givenF1F2F3A1step 1.1algebra

At each reached outer index, [A1] gives at most $M$ inner iterations and finite return/report work. Either the inner status or a failed success-residual check terminates the procedure, or one finite multiplier update and one finite KKT test [F3] follow. Thus every outer iteration is finite. There are only $K$ possible outer indices, so total inner iterations are at most $K M$ and total KKT tests are at most $K$ . If none of the earlier returns occurs, the procedure reaches its explicitly prescribed outer-budget-exhausted return.

3.1givenF1F3step 1.1step 2.1algebra∎

A passing KKT test is exactly $r_{k} \leq τ$ , and its reported point and updated multipliers are those used to evaluate $r_{k}$ ; the preceding success check ensures the reported inner residual is at most $ϵ_{k}$ . If the outer cap is reached, $K \geq 1$ ensures the last successful call and test exist, so $x_{K}$ , $(ν_{K}, λ_{K})$ , $r_{K - 1}$ and ${\hat{ϵ}}_{K - 1}$ are defined and returned. The two inner terminal statuses return exactly the state/data specified by [F1]. These are all branches, and none requires that any KKT or inner tolerance eventually be met.

Depends on

Used by

Nothing in the library uses this result yet.

Cited to discharge well-definedness by Finite-budget augmented-Lagrangian multiplier method.

Dependency tree · two levels

5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed. (standard reference, not scraped)
Dimitri P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods (standard reference, not scraped)