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

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

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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