TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Wolfe steps imply the Zoutendijk summability condition

Statement

Let $D \subseteq R^{n}$ be open, let $f : D \to R$ be $C^{1}$ and let $x_{0} \in D$ . Define its initial sublevel set $L_{0} : = {x \in D : f (x) \leq f (x_{0})}$ , and suppose $f$ is bounded below on $L_{0}$ . Let $N \subseteq D$ contain every segment $x_{k} + [0, t_{k}] p_{k}$ in a sequence $(x_{k})_{k \geq 0} \subset D$ . Suppose there is $L > 0$ such that

∥ \nabla f (u) - \nabla f (v) ∥_{2} \leq L ∥ u - v ∥_{2} (u, v \in N) .

For every $k \geq 0$ , assume $x_{k + 1} = x_{k} + t_{k} p_{k}$ , $p_{k} \neq 0$ is a descent direction at $x_{k}$ , and $t_{k} > 0$ is a Wolfe step for $f, x_{k}, p_{k}$ under Wolfe and strong Wolfe line-search conditions. Define $\cos θ_{k} : = - \frac{⟨ \nabla f (x_{k}), p_{k} ⟩}{∥ \nabla f (x_{k}) ∥_{2} ∥ p_{k} ∥_{2}} .$ Then

\sum_{k = 0}^{\infty} \cos^{2} θ_{k} ∥ \nabla f (x_{k}) ∥_{2}^{2} < \infty .

Facts & Assumptions

Given: $D, f, x_{0}, L_{0}, N, L, (x_{k}), (p_{k}), (t_{k})$ and the hypotheses in the Statement.

[F1]

Wolfe and strong Wolfe line-search conditions: a Wolfe step satisfies $f (x_{k} + t_{k} p_{k}) \leq f (x_{k}) + c_{1} t_{k} ⟨ \nabla f (x_{k}), p_{k} ⟩$ and $⟨ \nabla f (x_{k} + t_{k} p_{k}), p_{k} ⟩ \geq c_{2} ⟨ \nabla f (x_{k}), p_{k} ⟩$ , with $0 < c_{1} < c_{2} < 1 / 2$ .

[F2]

A Wolfe step has a lower bound from its descent angle: on a segment where $\nabla f$ is $L$ -Lipschitz, a Wolfe step satisfies $t_{k} \geq \frac{1 - c_{2}}{L} \frac{\cos θ_{k} ∥ \nabla f (x_{k}) ∥_{2}}{∥ p_{k} ∥_{2}}$ .

Proof

Given: The hypotheses and notation in the Statement.

1.1givenalgebra

Put $g_{k} : = \nabla f (x_{k})$ . Since $g_{k}^{T} p_{k} < 0$ and $p_{k} \neq 0$ , $g_{k} \neq 0$ and $0 < \cos θ_{k} \leq 1$ .

2.1givenF2step 1.1algebra

By [F2], $t_{k} ∥ p_{k} ∥_{2} \geq \frac{1 - c_{2}}{L} \cos θ_{k} ∥ g_{k} ∥_{2}$ . Multiplying by $c_{1} \cos θ_{k} ∥ g_{k} ∥_{2} > 0$ gives $c_{1} t_{k} (- g_{k}^{T} p_{k}) = c_{1} t_{k} \cos θ_{k} ∥ g_{k} ∥_{2} ∥ p_{k} ∥_{2} \geq \frac{c_{1} (1 - c_{2})}{L} \cos^{2} θ_{k} ∥ g_{k} ∥_{2}^{2}$ .

3.1givenF1step 2.1algebrainduction

The Armijo inequality in [F1] and step 2.1 give $f (x_{k}) - f (x_{k + 1}) \geq \frac{c_{1} (1 - c_{2})}{L} \cos^{2} θ_{k} ∥ g_{k} ∥_{2}^{2}$ . Summing from $k = 0$ to $m$ telescopes to $f (x_{0}) - f (x_{m + 1})$ ; Armijo also gives $f (x_{k + 1}) \leq f (x_{k})$ , so induction from $x_{0} \in L_{0}$ keeps every iterate in $L_{0}$ .

4.1givenstep 3.1algebra∎

Let $m_{f}$ be a lower bound for $f$ on $L_{0}$ . Step 3.1 gives $\frac{c_{1} (1 - c_{2})}{L} \sum_{k = 0}^{m} \cos^{2} θ_{k} ∥ g_{k} ∥_{2}^{2} \leq f (x_{0}) - f (x_{m + 1}) \leq f (x_{0}) - m_{f}$ . The partial sums are nondecreasing and bounded above independently of $m$ ; hence they converge to a finite limit.

Depends on

Used by

Dependency tree · two levels

24 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)