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.

An indefinite Rosenbrock Hessian makes the raw Newton direction ascend

Example

For the Rosenbrock objective $f (x, y) = 100 (y - x^{2})^{2} + (1 - x)^{2}$ at $(x, y) = (0, 1 / 100)$ , the Hessian is indefinite and the unshifted Newton correction is an ascent direction. With shift $λ = 3$ , the linear solve produces a descent direction, and the objective is bounded below on its ray; a strong Wolfe interval therefore exists. A finite search budget may still return failure before finding a step.

Use the deterministic Krylov procedure which, for a two-dimensional operator $A$ and right-hand side $b$ , forms $V = [b A b]$ when $M \geq 2$ . If $V$ and $V^{T} A V$ are invertible, it returns $p = V (V^{T} A V)^{- 1} V^{T} b$ with iteration count $m = 2$ ; otherwise it returns no-candidate. On other input dimensions or budgets below two it returns no-candidate. Its candidate lies in $K_{2} (A, b)$ by construction. Take $M \geq 2$ , $N \geq 1$ , $E, Z \geq 1$ , $η_{k} = \overset{ˉ}{η} = 0$ , $γ = 2$ , $c_{1} = 1 / 10000$ , and $c_{2} = 2 / 5$ , with the shift parameters below.

Facts & Assumptions

Given: The objective and point in the Example, descent threshold $σ = 1 / 10$ , regularization seed $λ_{0} = 3$ , a regularization cap $λ_{\max} \geq 3$ , and attempt budget $J \geq 1$ .

[F1]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: the gradient is the vector of first partial derivatives in Euclidean coordinates.

[F2]

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

[F3]

Finite-budget inexact Newton–Krylov with a descent safeguard: the first linear system is unshifted; a failed residual or descent check triggers a positive shift, and a regularized candidate is accepted only after recomputing its residual and checking descent.

[F4]

A strong Wolfe step exists on a bounded-below descent ray: for a $C^{1}$ objective bounded below on an entire feasible descent ray, a strong Wolfe interval exists.

Verification

Given: The Rosenbrock objective, the point $(0, 1 / 100)$ , $σ = 1 / 10$ , $λ_{0} = 3$ , $λ_{\max} \geq 3$ , and $J \geq 1$ .

1.1givenF1F2algebra

Put $r : = y - x^{2}$ . Differentiating gives $g = (- 400 x r + 2 (x - 1), 200 r)$ and $H_{f} = [\begin{array}{cc} 1200 x^{2} - 400 y + 2 & - 400 x \\ - 400 x & 200 \end{array}]$ . At the given point, $g = (- 2, 2)$ and $H = diag (- 2, 200)$ . The quadratic form of $H$ is negative on $(1, 0)$ and positive on $(0, 1)$ , so $H$ is indefinite.

2.1givenF3step 1.1algebra

For $b = - g = (2, - 2)$ and either $A = H$ or $A = H + 3 I_{2}$ , $\det [b A b] = - 808 \neq 0$ , and both operators are invertible. Hence the specified projected solver returns the exact solution $A p = b$ in $K_{2} (A, b)$ , using $m = 2 \leq M$ . The unshifted Newton solve $H p = - g$ gives $p = (- 1, - 1 / 100)$ and $g^{T} p = 99 / 50 > 0$ . It is therefore not a descent direction and fails the algorithm's descent check.

2.2givenF3step 1.1algebra

For shift $λ = 3$ , $H + 3 I_{2} = diag (1, 203)$ and the exact shifted solve gives $p = (2, - 2 / 203)$ . Its residual is zero, while $g^{T} p = - 4 - 4 / 203 < - 4$ . Also $∥ g ∥_{2} = 2 \sqrt{2} < 3$ and $∥ p ∥_{2} < 3$ , hence $- (1 / 10) ∥ g ∥_{2} ∥ p ∥_{2} > - 9 / 10$ and $g^{T} p < - (1 / 10) ∥ g ∥_{2} ∥ p ∥_{2}$ . Thus the shifted candidate passes the stated residual and descent tests.

3.1givenF4step 2.2∎

The Rosenbrock objective is nonnegative on $R^{2}$ , and the shifted direction has $g^{T} p < 0$ . The entire ray is feasible because $D = R^{2}$ . Apply [F4] to conclude that a nonempty interval of strong Wolfe steps exists for this direction. This existence result does not guarantee that any specified finite expansion/zoom budget reaches the interval.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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