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

✓ 3 results · all verified · 1 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Nonlinear conjugate gradient methods — Examples

1 · Prerequisites

2 · Summary

The examples verify one accepted Rosenbrock step for both FR and PR+, exhibit an exact strong-Wolfe step after which the raw PR+ candidate ascends and the safeguard restores steepest descent, and trace exact-line FR/linear-CG agreement on a two-dimensional SPD quadratic.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

One accepted Rosenbrock step gives different FR and PR+ coefficients

Example

For the Rosenbrock function $f (x, y) = (1 - x)^{2} + 100 (y - x^{2})^{2}$ , take $x_{0} = (- 6 / 5, 1)$ and $d_{0} = - g_{0}$ . With $c_{1} = 1 / 1000$ , $c_{2} = 49 / 100$ , bounded search budgets $E \geq 1$ , $Z \geq 10$ , and outer budget $K \geq 2$ , the first accepted step is $t_{0} = 1 / 1024$ . Its FR and PR+ coefficients differ. The PR+ candidate ascends, so the safeguarded method restarts; for definiteness take $σ = 1 / 2$ and $C = 2$ .

Facts & Assumptions

Given: The function, start and parameters in the Example, with exact arithmetic.

[F1]

Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients: $d_{0} = - g_{0}$ ; FR uses $β_{0}^{F R} = ∥ g_{1} ∥_{2}^{2} / ∥ g_{0} ∥_{2}^{2}$ , whereas the PR+ candidate uses $β_{0}^{P R +} = \max {0, g_{1}^{T} (g_{1} - g_{0}) / ∥ g_{0} ∥_{2}^{2}}$ ; a failed descent or norm test resets it to $- g_{1}$ .

[F2]

Wolfe and strong Wolfe line-search conditions: strong Wolfe requires Armijo decrease and $∣ ϕ^{'} (t) ∣ \leq c_{2} ∣ ϕ^{'} (0) ∣$ .

[F3]

Finite-budget bracketing and zoom for a strong Wolfe step: the first expansion trial is $1$ ; an Armijo failure calls zoom with endpoints $(0, 1)$ , whose midpoint trials halve the positive endpoint while the same failure persists.

Verification

Given: The objective, initial point and budgets of the Example.

1.1givenF1algebra

Differentiation gives $g_{0} = (- 1078 / 5, - 88)$ , $d_{0} = (1078 / 5, 88)$ , $f (x_{0}) = 121 / 5$ , and $ϕ^{'} (0) = - G_{0}$ with $G_{0} = 1,355,684 / 25 = 54,227.36$ . At a parameter $t$ , write $u = - 6 / 5 + (1078 / 5) t$ , $v = 1 + 88 t$ , and $r = v - u^{2}$ . Then $ϕ (t) = (1 - u)^{2} + 100 r^{2}$ and $ϕ^{'} (t) = (- 400 u r + 2 (u - 1)) (1078 / 5) + 200 r (88)$ .

2.1givenF3step 1.1algebra

Exact substitution into step 1.1 gives integer lower bounds for $ϕ (2^{- j})$ , in order $j = 0, \dots, 9$ : $210482437168$ , $12810991198$ , $758614013$ , $42388850$ , $2078788$ , $72456$ , $543$ , $211$ , $149$ , and $35$ . Each lower bound exceeds $121 / 5$ , whereas every positive-trial Armijo right side is below $121 / 5$ . Thus the initial trial fails Armijo and the first nine zoom trials fail it as well. By [F3], $a = 0$ remains fixed and the tenth zoom trial is $t_{0} = 2^{- 10} = 1 / 1024$ .

3.1givenF2F3step 1.1step 2.1algebra

At this trial, $x_{1} = (- 2533 / 2560, 139 / 128)$ and $r = 700711 / 6553600$ . Exactly, $f (x_{1}) = \frac{438182241277}{85899345920} < \frac{511}{100}, g_{1} = (\frac{1608013539}{41943040}, \frac{700711}{32768}), h : = g_{1}^{T} d_{0} = \frac{1064039515121}{104857600} .$ The Armijo right side is $121 / 5 - G_{0} / (1000 \cdot 1024) > 24$ , so Armijo holds. Also $0 < h < 10148 < 26571 < (49 / 100) G_{0} = 26571.4064$ , so strong curvature holds. The search therefore returns this tenth midpoint.

4.1givenF1step 3.1algebra

Put $G_{1} = ∥ g_{1} ∥_{2}^{2} = 3390155233212910921 / 1759218604441600$ . Because $g_{0} = - d_{0}$ and $h > 0$ , the coefficients are $β_{0}^{F R} = G_{1} / G_{0}$ and $β_{0}^{P R +} = (G_{1} + h) / G_{0} > β_{0}^{F R}$ . The FR direction is $- g_{1} + (G_{1} / G_{0}) d_{0}$ ; the PR+ candidate is $d_{1}^{c a n d} = - g_{1} + ((G_{1} + h) / G_{0}) d_{0}$ . Exact values in step 3.1 give $1927 < G_{1} < 1928$ , $10147 < h < 10148$ , and $54227 < G_{0} < 54228$ . Hence $g_{1}^{T} d_{1}^{c a n d} = - G_{1} + \frac{(G_{1} + h) h}{G_{0}} > - 1928 + \frac{(1927 + 10147) 10147}{54228} > 331 > 0.$ It fails the descent safeguard for every $σ > 0$ . Thus the actual selected PR+ direction is $d_{1} = - g_{1}$ and its restart flag is true; the ascending candidate is not the selected direction.

5.1givenF1F2step 1.1algebra∎

For comparison, the originally displayed trial $\hat{t} = 1 / 1000$ is also a mathematically valid strong Wolfe step, but is not an output of this dyadic search. It gives $\hat{x} = (- 2461 / 2500, 136 / 125)$ , $\hat{r} = 743479 / 6250000$ , $f (\hat{x}) = 5.35291158000896$ , $\hat{g} = (42.8715665664, 23.791328)$ , and $\hat{h} = {\hat{g}}^{T} d_{0} = 11336.74661571584$ . Its Armijo bound is $24.14577264$ and $∣ \hat{h} ∣ < 11400 < 26571.4064$ , verifying both inequalities directly. With $\hat{G} = ∥ \hat{g} ∥_{2}^{2}$ , its distinct coefficients are $\hat{G} / G_{0}$ and $(\hat{G} + \hat{h}) / G_{0}$ ; these describe the hypothetical accepted update at $\hat{t}$ , rather than the actual bounded-search trace above.

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

A strong Wolfe step can leave PR+ ascending; the safeguard restarts

Statement refuted

After every strong Wolfe step with a nonzero new gradient, the raw PR+ candidate direction is a descent direction.

Facts & Assumptions

Given: The raw PR+ coefficient and safeguard in Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients and the strong Wolfe conditions of Wolfe and strong Wolfe line-search conditions.

[F1]

Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients: $β^{P R +} = \max {0, g_{1}^{T} (g_{1} - g_{0}) / ∥ g_{0} ∥_{2}^{2}}$ and $d_{1}^{c a n d} = - g_{1} + β^{P R +} d_{0}$ .

[F3]

Fletcher–Reeves and safeguarded Polak–Ribière nonlinear conjugate gradients: if the descent or norm safeguard test fails, the procedure resets to $d_{1} = - g_{1}$ .

[F2]

Wolfe and strong Wolfe line-search conditions: a strong Wolfe step satisfies $ϕ (t) \leq ϕ (0) + c_{1} t ϕ^{'} (0)$ and $∣ ϕ^{'} (t) ∣ \leq c_{2} ∣ ϕ^{'} (0) ∣$ .

Counterexample

Let $H = (\begin{array}{cc} 7 / 5 & - 1 / 10 \\ - 1 / 10 & 1 \end{array}), f (x) = \frac{1}{2} x^{T} H x + x_{1} .$ Start at $x_{0} = (0, 0)$ with $c_{1} = 1 / 100$ and $c_{2} = 49 / 100$ .

1.1givenalgebra

For every $u \neq 0$ , $u^{T} H u = \frac{7}{5} {(u_{1} - \frac{1}{14} u_{2})}^{2} + \frac{139}{140} u_{2}^{2} > 0.$ Thus $H$ is positive definite. Also $g_{0} = (1, 0)$ and $d_{0} = - g_{0} = (- 1, 0)$ .

2.1givenF2step 1.1algebra

Take $t_{0} = 1$ . Then $x_{1} = (- 1, 0)$ , $f (x_{0}) = 0$ , $f (x_{1}) = - 3 / 10$ , and $g_{1} = H x_{1} + (1, 0) = (- 2 / 5, 1 / 10)$ . The initial directional derivative is $ϕ^{'} (0) = - 1$ and the new one is $g_{1}^{T} d_{0} = 2 / 5$ . Hence $f (x_{1}) = - 3 / 10 \leq - 1 / 100 = f (x_{0}) + c_{1} t_{0} ϕ^{'} (0), ∣ g_{1}^{T} d_{0} ∣ = 2 / 5 \leq 49 / 100.$ This is a strong Wolfe step.

3.1F1step 2.1algebra

Since $g_{1} - g_{0} = (- 7 / 5, 1 / 10)$ , $β^{P R +} = \frac{g_{1}^{T} (g_{1} - g_{0})}{∥ g_{0} ∥_{2}^{2}} = \frac{14}{25} + \frac{1}{100} = \frac{57}{100} .$ Thus $d_{1}^{c a n d} = - g_{1} + β^{P R +} d_{0} = (- 17 / 100, - 1 / 10)$ and $g_{1}^{T} d_{1}^{c a n d} = \frac{29}{500} > 0.$ The raw PR+ candidate is an ascent direction, refuting the statement.

4.1F3step 3.1algebra∎

For the safeguarded variant choose $σ = 1 / 2$ and $C = 2$ . Since $∥ g_{1} ∥_{2}^{2} = 17 / 100$ , we have $\frac{29}{500} > - \frac{1}{2} ∥ g_{1} ∥_{2}^{2} = - \frac{17}{200},$ so the descent test triggers a restart. The norm test alone would not: $∥ d_{1}^{c a n d} ∥_{2}^{2} = 389 / 10000 < 4 ∥ g_{1} ∥_{2}^{2}$ . The new direction $d_{1} = - g_{1}$ has $g_{1}^{T} d_{1} = - 17 / 100 < 0$ and $\cos θ_{1} = 1$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

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

Example

Take $A = diag (1, 2)$ , $b = (1, 1)$ , and $f (x) = \frac{1}{2} x^{T} A x - b^{T} x, x_{0} = (0, 0) .$ Use exact-SPD-quadratic mode with outer budget $K \geq 2$ and $c_{1} = 1 / 10$ , $c_{2} = 1 / 4$ . An exact-line-search FR run reaches the solution in two steps, with the same directions and steps as linear CG.

Facts & Assumptions

Given: The quadratic, start point, and exact-line-search conditions in the Example.

[F1]

FR and unrestarted PR+ match linear CG on SPD quadratics: on a real SPD quadratic in exact arithmetic, FR exact-line-search iterates, residuals and directions equal linear CG through the zero-residual exit.

[F2]

The conjugate-gradient recurrence: $α_{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}$ .

Verification

Given: $A = diag (1, 2)$ , $b = (1, 1)$ , and $x_{0} = (0, 0)$ .

1.1givenF2algebra

The initial residual and gradient are $r_{0} = (1, 1)$ and $g_{0} = - r_{0} = (- 1, - 1)$ , so $d_{0} = (1, 1)$ . By [F2], $α_{0} = (r_{0}^{T} r_{0}) / (d_{0}^{T} A d_{0}) = 2 / 3$ , giving $x_{1} = (2 / 3, 2 / 3)$ and $r_{1} = (1 / 3, - 1 / 3)$ .

2.1F2step 1.1algebra

The next coefficient is $β_{0} = (r_{1}^{T} r_{1}) / (r_{0}^{T} r_{0}) = (2 / 9) / 2 = 1 / 9$ , hence $d_{1} = r_{1} + β_{0} d_{0} = (4 / 9, - 2 / 9)$ . Also $d_{1}^{T} A d_{1} = 8 / 27$ , so $α_{1} = (2 / 9) / (8 / 27) = 3 / 4$ .

3.1F1step 2.1algebra∎

Therefore $x_{2} = x_{1} + α_{1} d_{1} = (1, 1 / 2)$ and $r_{2} = b - A x_{2} = 0$ . By [F1], the exact-line-search FR run has these same directions, step lengths, and terminal point.