TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pass

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.

FR and unrestarted PR+ match linear CG on SPD quadratics

Statement

Let $A \in R^{n \times n}$ be symmetric positive definite, $b \in R^{n}$ , and $f (x) = \frac{1}{2} x^{T} A x - b^{T} x, x \in R^{n} .$ In exact arithmetic, run the FR recurrence of Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients with exact line minimization. Its iterates, residuals $r_{k} = b - A x_{k}$ , and directions coincide with the linear conjugate-gradient recurrence of The conjugate-gradient recurrence until the common zero-residual exit. The unrestarted raw PR+ recurrence has the same exact-line-search sequence; the safeguarded PR+ implementation has this equivalence only on runs where its safeguard does not restart. No such equivalence is asserted for non-SPD quadratics, inexact line searches, or finite-precision arithmetic.

Facts & Assumptions

Given: The SPD quadratic, initial point, exact-arithmetic recurrence, and exact-line-search conditions in the Statement.

[F1]

Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients: the initial direction is $d_{0} = - g_{0}$ .

[F5]

Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients: later directions use $d_{k} = - g_{k} + β_{k - 1} d_{k - 1}$ ; FR uses $β_{k - 1} = ∥ g_{k} ∥_{2}^{2} / ∥ g_{k - 1} ∥_{2}^{2}$ and raw PR+ uses $\max {0, g_{k}^{T} (g_{k} - g_{k - 1}) / ∥ g_{k - 1} ∥_{2}^{2}}$ before any safeguard reset.

[F2]

The conjugate-gradient recurrence: linear CG uses $r_{0} = b - A x_{0}$ , $p_{0} = r_{0}$ , $α_{k} = (r_{k}^{T} r_{k}) / (p_{k}^{T} A p_{k})$ , $r_{k + 1} = r_{k} - α_{k} A p_{k}$ , $β_{k} = (r_{k + 1}^{T} r_{k + 1}) / (r_{k}^{T} r_{k})$ , and $p_{k + 1} = r_{k + 1} + β_{k} p_{k}$ .

[F3]

In exact arithmetic, CG residuals are mutually orthogonal and the search directions are $A$ -conjugate: in exact-arithmetic CG for Hermitian positive-definite $A$ , distinct residuals are orthogonal.

[F4]

Before convergence, every CG denominator $p_{k}^{*} A p_{k}$ is positive: if $r_{k} \neq 0$ , then $p_{k} \neq 0$ and $p_{k}^{T} A p_{k} > 0$ .

[F6]

Wolfe and strong Wolfe line-search conditions: strong Wolfe requires Armijo decrease and an absolute directional-derivative bound, with $0 < c_{1} < c_{2} < 1 / 2$ .

Proof

Given: The hypotheses and notation in the Statement.

1.1givenF1algebra

Differentiating the given quadratic gives $g_{k} = A x_{k} - b = - r_{k}$ . If $r_{0} = 0$ , both procedures are already at the common zero-residual exit. Otherwise, $d_{0} = - g_{0} = r_{0} = p_{0} \neq 0$ .

2.1giveninductionalgebra

Use joint induction at index $k$ : the iterates and residuals agree through $k$ , and the directions and accepted step lengths agree through $k - 1$ . At $k = 0$ , the initial points and residuals agree and step 1.1 supplies the common initial direction. For $k \geq 1$ , assume this invariant and that the run has not terminated. The preceding accepted step exactly minimizes the SPD quadratic along the common direction $d_{k - 1} = p_{k - 1}$ . The derivative of its restricted quadratic vanishes at that positive minimizer, so $g_{k}^{T} d_{k - 1} = 0$ and therefore $r_{k}^{T} d_{k - 1} = 0$ .

3.1F3F5step 2.1inductionalgebra

For the FR recurrence, $d_{k} = r_{k} + β_{k - 1} d_{k - 1}$ and $β_{k - 1} = ∥ r_{k} ∥_{2}^{2} / ∥ r_{k - 1} ∥_{2}^{2}$ . For the raw PR+ recurrence, [F3] gives $r_{k}^{T} r_{k - 1} = 0$ , so $β_{k - 1}^{P R +} = \max ⁣ {0, \frac{r_{k}^{T} (r_{k} - r_{k - 1})}{∥ r_{k - 1} ∥_{2}^{2}}} = \frac{∥ r_{k} ∥_{2}^{2}}{∥ r_{k - 1} ∥_{2}^{2}} = β_{k - 1}^{F R} .$ Thus either unrestarted direction equals $r_{k} + β_{k - 1} p_{k - 1}$ , the linear-CG direction at the current index. A safeguarded PR+ direction also agrees whenever its safeguard does not restart.

4.1givenF2F4F6step 1.1step 2.1step 3.1algebra

For $k = 0$ , step 1.1 gives $d_{k} = p_{k} \neq 0$ ; for $k \geq 1$ , step 3.1 gives the same equality. Then [F4] gives $p_{k}^{T} A p_{k} > 0$ . The restriction of $f$ to $x_{k} + t d_{k}$ is $f (x_{k} + t d_{k}) = f (x_{k}) + t g_{k}^{T} d_{k} + \frac{1}{2} t^{2} d_{k}^{T} A d_{k} .$ Its unique minimizer is $t_{k} = - g_{k}^{T} d_{k} / (d_{k}^{T} A d_{k}) > 0$ . For $k = 0$ , $r_{0}^{T} d_{0} = ∥ r_{0} ∥_{2}^{2}$ by step 1.1. For $k \geq 1$ , step 2.1 and the recurrence give $r_{k}^{T} d_{k} = ∥ r_{k} ∥_{2}^{2}$ . Therefore this is $t_{k} = \frac{r_{k}^{T} r_{k}}{p_{k}^{T} A p_{k}} = α_{k}$ from [F2]. At this minimizer, $ϕ^{'} (t_{k}) = g_{k}^{T} d_{k} + t_{k} d_{k}^{T} A d_{k} = 0$ , so the strong curvature test holds. Also $ϕ (t_{k}) = ϕ (0) + \frac{1}{2} t_{k} g_{k}^{T} d_{k} \leq ϕ (0) + c_{1} t_{k} g_{k}^{T} d_{k}$ because $t_{k} g_{k}^{T} d_{k} < 0$ and $c_{1} < 1 / 2$ . Thus [F6] and the exact-model branch accept this step; the same calculation applies at every preceding common minimizer invoked in step 2.1, starting with step 1.1, so the induction uses actual accepted steps. Hence the next iterates and residuals agree.

5.1F2F3F5step 1.1step 4.1induction∎

After the common step, $r_{k + 1} = b - A x_{k + 1}$ is the CG residual and $g_{k + 1} = - r_{k + 1}$ by step 1.1. If $r_{k + 1} = 0$ , both methods stop at the common exit. Otherwise the FR coefficient equals $∥ r_{k + 1} ∥_{2}^{2} / ∥ r_{k} ∥_{2}^{2}$ , and the raw PR+ coefficient again equals it by [F3] and [F5]. Thus the next direction also agrees; induction continues until zero residual.

Depends on

Used by

A two-dimensional SPD quadratic gives the same FR and linear-CG trace Example

Dependency tree · two levels

30 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)
Jean Charles Gilbert and Jorge Nocedal, Global Convergence Properties of Conjugate Gradient Methods for Optimization, SIAM Journal on Optimization 2(1), 21–42 (1992), DOI 10.1137/0802003 (standard reference, not scraped)