LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generated

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.

Safeguarded inexact Newton has a finite checked-return bound

Statement

Under the inputs of Finite-budget inexact Newton–Krylov with a descent safeguard, assume every call of the supplied Krylov procedure terminates within its budget of $M$ inner iterations, all requested in-domain function, gradient and Hessian-action evaluations terminate with real values, and the prescribed comparisons are exact. The algorithm terminates with its specified status, retaining the underlying search failure cause when applicable. Every iterate belongs to $U$ . There are at most $N$ accepted updates, $N (J + 1)$ Krylov calls, $N (J + 1) M$ inner iterations, $N$ line-search calls, and $N (E + Z)$ evaluated line-search trial points. Separately, at most $N + 1$ outer-iterate gradient evaluations and $N (J + 1)$ recomputed candidate residuals occur. Each residual uses one Hessian action outside the Krylov solver. These counts do not bound the number of Hessian actions used internally by an arbitrary supplied solver, total arithmetic work, or convergence. In exact arithmetic the no-descent-direction branch is unreachable under the stated inputs.

Facts & Assumptions

Given: The hypotheses and budgets of the Statement.

[F1]

Finite-budget inexact Newton–Krylov with a descent safeguard: the outer loop ranges from $0$ through $N$ ; it returns at a stationary iterate or at $k = N$ before solving, and otherwise makes at most $J + 1$ solver attempts, recomputes each candidate residual, checks descent or the fallback, and calls the bounded line search once before an update.

[F2]

Bracketing and zoom terminate with a checked step or a failure: each line-search call terminates, uses at most $E + Z$ evaluated trial points, and returns only a positive feasible checked strong Wolfe step or a failure status.

Proof

Given: The hypotheses of the Statement.

1.1givenF1algebra

Initially $x_{0} \in U$ . At any nonstationary iteration the supplied solver calls and candidate residual evaluations terminate by assumption; the loop has at most $J + 1$ attempts. Every accepted candidate satisfies $g_{k}^{T} p < - σ ∥ g_{k} ∥_{2} ∥ p ∥_{2} < 0$ , since a candidate with $p = 0$ cannot pass. If none passes, $p = - g_{k}$ gives $g_{k}^{T} p = - ∥ g_{k} ∥_{2}^{2} < - σ ∥ g_{k} ∥_{2}^{2}$ because $g_{k} \neq 0$ and $0 < σ < 1$ . Thus a strict descent direction is always available and the fallback failure cannot occur in exact arithmetic.

2.1F1F2step 1.1induction

By [F2] the ensuing search terminates. On failure the algorithm returns its last valid iterate, its line-search-failure status and the search cause. On success feasibility of the checked step gives $x_{k + 1} \in U$ . Induction proves feasibility of every iterate.

3.1givenF1F2step 2.1algebra

A solve or update can occur only for $k < N$ . Thus at most $N$ updates and searches and $N (J + 1)$ solver calls occur; each uses at most $M$ inner iterations. At most one candidate residual is recomputed per call, each by one Hessian action plus the displayed shift and vector arithmetic. By [F2] there are at most $N (E + Z)$ evaluated search trials. The outer loop computes its gradient once per visited index, at most $N + 1$ times, separately from line-search gradient evaluations.

4.1givenF1step 1.1step 2.1step 3.1∎

Every inner call and search terminates and every loop has its finite stated bound. Hence the algorithm reaches a specified return no later than its $k = N$ check. Steps 1.1–3.1 prove the asserted statuses, feasibility and counts; they do not specify the internal Hessian-action count of the arbitrary solver or a convergence theorem.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 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, second edition (standard reference, not scraped)