ExampleConstruction: AI-generatedVerification: 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.

A scalar inexact Newton solve trades inner work for outer error

Example

Let $f (x) = x^{2} / 2$ , so $F (x) = f^{'} (x) = x$ and $F^{'} (x) = 1$ . At a nonzero iterate, solve the Newton equation approximately from $p^{(0)} = 0$ by

p^{(j + 1)} = p^{(j)} - (1 - ω) (p^{(j)} + x), 0 < ω < 1.

Stop at the first $j$ with $ω^{j} \leq η$ , where the forcing tolerance satisfies $0 < η \leq c_{2} < 1 / 2$ . With the exact strong Wolfe search from Finite-budget bracketing and zoom for a strong Wolfe step, the unit step is accepted. The number $j$ of inner iterations grows as $η$ is tightened, while the outer error contracts by a factor at most $η$ ; choosing $η_{k} = ∣ x_{k} ∣$ gives a quadratic outer error bound for $0 < ∣ x_{0} ∣ \leq c_{2}$ .

For each finite horizon $N \geq 1$ , let $j_{k}$ be the least integer with $ω^{j_{k}} \leq η_{k}$ on the first $N$ steps of the displayed recurrence, and choose the single inner budget $M_{N} \geq \max_{0 \leq k < N} j_{k}$ . Use $M = M_{N}$ , $\overset{ˉ}{η} = c_{2}$ , $σ = 1 / 2$ , $J = 0$ , $E, Z \geq 1$ , $γ = 2$ , and $λ_{0} = λ_{\max} = 1$ . The deterministic solver on the scalar operator $A = 1$ starts at zero and performs the displayed iteration until $∣ p + x ∣ \leq τ$ , where $τ$ is its absolute requested residual tolerance, or until $M$ iterations are used; it returns that scalar candidate and its iteration count. It returns no-candidate for other operators. For $b = - x \neq 0$ and any $m \geq 1$ , $K_{m} (1, b) = R$ , so every returned candidate meets the Krylov input contract (and $p^{(0)} = 0 \in K_{0}$ ). This realizes every finite prefix. The infinite recurrence and its rate claim do not assert realization by one fixed finite inner budget.

Facts & Assumptions

Given: The scalar objective, the fixed $ω \in (0, 1)$ , and Wolfe parameters $0 < c_{1} < c_{2} < 1 / 2$ .

[F1]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: for a scalar function the gradient is the vector of first partial derivatives.

[F2]

The Hessian matrix and critical points of a scalar field: the Hessian is the matrix of second partial derivatives.

[F3]

Finite-budget inexact Newton–Krylov with a descent safeguard: the unshifted solve is accepted only after recomputing $H (x) p + g (x)$ and checking its forcing residual and descent threshold; the next iterate uses the returned Wolfe step.

[F4]

Finite-budget bracketing and zoom for a strong Wolfe step: the search tests $t = 1$ first and returns it when both strong Wolfe inequalities hold.

[F5]

Forcing residuals determine local inexact-Newton rates: an unshifted full-step sequence with a relative residual bounded by $η_{k} ∥ F (x_{k}) ∥_{2}$ converges quadratically when $η_{k} = O (∥ F (x_{k}) ∥_{2})$ , under the stated local hypotheses.

[F6]

For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ : if $∣ r ∣ < 1$ , then $r^{k} \to 0$ .

[F7]

The Krylov subspace $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ : $K_{0} (A, b) = {0}$ and $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ for $m \geq 1$ .

Verification

Given: The objective and inner iteration of the Example, with $x \neq 0$ and $0 < η \leq c_{2}$ .

1.1givenF1F2inductionalgebra

The exact scalar identities are $F (x) = x$ , $J (x) = 1$ , and $g (x) = x$ by [F1]–[F2]. Induction on $j$ gives $p^{(j)} = - (1 - ω^{j}) x$ , so the linear residual is $r_{j} = J (x) p^{(j)} + F (x) = ω^{j} x$ .

1.2givenF6F7choosealgebra

Since $0 < ω < 1$ , [F6] gives $ω^{j} \to 0$ , so a least $j$ with $ω^{j} \leq η$ exists. As $η < 1$ , $j \geq 1$ and minimality gives $ω^{j} \leq η < ω^{j - 1}$ . If the requested tolerance is reduced, the set of eligible $j$ can only shrink, so the required inner iteration count cannot decrease. For any finite $N$ , all $j_{k}$ on its first $N$ nonzero iterates are finite, so their finite maximum defines $M_{N}$ . The specified solver therefore reaches its requested residual tolerance before its budget on that prefix, and [F7] verifies its scalar Krylov membership.

2.1givenF3step 1.1step 1.2algebra

At this $j$ , $∣ r_{j} ∣ = ω^{j} ∣ x ∣ \leq η ∣ x ∣$ , while $g (x) p^{(j)} = - (1 - ω^{j}) x^{2}$ and $∣ g (x) ∣ ∣ p^{(j)} ∣ = (1 - ω^{j}) x^{2}$ . Because $0 < σ < 1$ , the descent safeguard passes.

3.1givenF3F4step 2.1algebra

Let $q : = ω^{j} \leq η \leq c_{2}$ . The unit step gives $x_{+} = x + p^{(j)} = q x$ . Its objective satisfies $f (x_{+}) = q^{2} x^{2} / 2 \leq x^{2} (1 - 2 c_{1} (1 - q)) / 2 = f (x) + c_{1} g (x) p^{(j)}$ , because $1 + q \geq 1 > 2 c_{1}$ . Also $∣ ϕ^{'} (1) ∣ = q (1 - q) x^{2} \leq c_{2} (1 - q) x^{2} = c_{2} ∣ ϕ^{'} (0) ∣$ . Thus both strong Wolfe conditions hold, and [F4] accepts $t = 1$ .

4.1givenF5step 1.2step 3.1induction∎

For fixed $η$ , $q = ω^{j}$ is a constant in $(0, 1)$ and $x_{k + 1} = q x_{k}$ , so the outer sequence is linearly convergent. If $0 < ∣ x_{0} ∣ \leq c_{2}$ and $η_{k} = ∣ x_{k} ∣$ , then $η_{k} \leq c_{2}$ at every step and $∣ x_{k + 1} ∣ = ω^{j_{k}} ∣ x_{k} ∣ \leq ∣ x_{k} ∣^{2}$ . Here $η_{k} = ∣ F (x_{k}) ∣$ ; the local tube in [F5] may contain $[- c_{2}, c_{2}]$ because $F (x) = x$ and $J (x) = 1$ everywhere. Thus [F5] supplies the same local quadratic-rate conclusion.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

39 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.