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.

Numerical optimization globalization and inexact certificates — Examples

1 · Prerequisites

2 · Summary

Examples

These verifications calculate exact-search and Armijo steps on an anisotropic quadratic, a damped Newton step before its local quadratic phase, and the poor distance information in a small gradient when curvature is weak. The final two examples separate a computed-gradient residual from its discrepancy and calculate an inner quadrature contribution to that discrepancy exactly. Each certificate states the assumptions needed for its bound.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Exact and Armijo rates on an anisotropic quadratic

Example

For $f (u, v) = \frac{1}{2} u^{2} + 2 v^{2}$ , the exact-gradient step has an explicit nontrivial line minimizer, and Armijo backtracking shows the accepted-step bound in a finite calculation.

Facts & Assumptions

Given: $f (u, v) = \frac{1}{2} u^{2} + 2 v^{2}$ on $R^{2}$ , initial point $x_{0} = (1, 1)$ , exact gradient line search, and Armijo parameters $a = \frac{1}{4}$ , $b = \frac{1}{2}$ .

[F1]

Exact gradient line search has a global objective-gap contraction: under compact sublevel and $m I ⪯ H_{f} ⪯ M I$ , an exact negative-gradient line-search step contracts the objective gap by at least the factor $1 - m / M$ .

[F2]

Armijo gradient descent has an explicit global linear rate: with $0 < a < 1 / 2$ and $0 < b < 1$ , the accepted step is at least $\min {1, 2 b (1 - a) / M}$ and the objective-gap factor is $1 - 2 a m \min {1, 2 b (1 - a) / M}$ .

[F3]

Gradient descent: backtracking tests $t = 1, b, b^{2}, \dots$ and accepts when $f (x - t \nabla f (x)) \leq f (x) - a t ∥ \nabla f (x) ∥_{2}^{2}$ .

[F4]

Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line: in Euclidean space, a closed and bounded set is compact.

Verification

1.1F4given

The Hessian is $diag (1, 4)$ , so $m = 1$ and $M = 4$ ; $x^{*} = (0, 0)$ is the unique minimizer and $f (x_{0}) = 5 / 2$ . The sublevel set is closed by continuity and bounded because $\frac{1}{2} u^{2} \leq 5 / 2$ and $2 v^{2} \leq 5 / 2$ on it; it is compact by [F4]. The gradient at $x_{0}$ is $(1, 4)$ .

1.2F1givenalgebra

Along the negative-gradient ray, $ϕ (t) = \frac{1}{2} (1 - t)^{2} + 2 (1 - 4 t)^{2}$ and $ϕ^{'} (t) = 65 t - 17$ , so the unique minimizer is $t_{*} = 17 / 65$ . It gives $x_{+} = (48 / 65, - 3 / 65)$ and $f (x_{+}) = 234 / 845$ . The theorem [F1] bounds the gap by $(1 - 1 / 4) (5 / 2) = 15 / 8$ , and $234 / 845 < 15 / 8$ .

1.3F3givenalgebra

For Armijo, the first trial $t = 1$ has candidate $(0, - 3)$ with value $18$ and threshold $5 / 2 - 17 / 4 = - 7 / 4$ , so it fails. The second trial $t = 1 / 2$ has candidate $(1 / 2, - 1)$ with value $17 / 8$ and threshold $3 / 8$ , so it fails. At $t = 1 / 4$ , the candidate is $(3 / 4, 0)$ with value $9 / 32 < 23 / 16$ , the Armijo threshold; hence [F3] accepts $t = 1 / 4$ .

2.1F1F2step 1.3algebra∎

Here $τ = \min {1, 2 b (1 - a) / M} = 3 / 16$ , so [F2] gives the gap factor $1 - 2 a m τ = 29 / 32$ . The actual new gap $9 / 32$ is below $(29 / 32) (5 / 2) = 145 / 64$ . The exact and Armijo calculations concern objective gaps; neither calculation supplies an iterate-error bound.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

A damped Newton step precedes the local quadratic phase

Example

The strongly convex objective $f (x) = \frac{1}{2} x^{2} + 10 \sqrt{1 + x^{2}}$ makes a Newton step from $x_{0} = 2$ increase the objective, while its half-step passes Armijo. With a small positive decrement tolerance, the global-to-local theorem then ensures a finite damped phase followed by unit Newton steps whenever the decrement test continues to permit updates.

Facts & Assumptions

Given: $f (x) = \frac{1}{2} x^{2} + 10 \sqrt{1 + x^{2}}$ on $R$ , $x_{0} = 2$ , Armijo parameter $a = 1 / 100$ , shrink factor $b = 1 / 2$ , and decrement tolerance $ε = 10^{- 16}$ .

[F1]

Damped Newton reaches its local quadratic phase in finitely many continued updates: with global bounds $m, M$ , local radius $ρ$ , and $ε < m^{2} ρ^{2} / (2 M)$ , the method reaches the local ball in finitely many updates; later attempted steps are unit and quadratic.

[F2]

Damped Newton method: the method computes $p = - H (x)^{- 1} \nabla f (x)$ and $λ^{2} = \nabla f (x)^{T} H (x)^{- 1} \nabla f (x)$ , stops before line search when $λ^{2} / 2 \leq ε$ , and otherwise starts backtracking at $t = 1$ .

[F3]

Newton's method has local quadratic convergence under a Lipschitz Hessian: with a positive-definite critical Hessian and a Lipschitz Hessian on a ball, there are local constants such that every generated iterate stays in the ball and every attempted Newton update not stopped by the decrement test accepts a unit step with a quadratic error bound.

[F4]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : a differentiable scalar function whose derivative is bounded in absolute value by $L$ on an interval is $L$ -Lipschitz there.

[F5]

Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line: a closed and bounded subset of the real line is compact.

[F6]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case and The Hessian matrix and critical points of a scalar field: the gradient is the first derivative and the Hessian is the second derivative in the one-dimensional coordinate.

[F7]

Multivariable Taylor formula with a Lagrange remainder along a line segment: on a segment in an open convex domain, the second-order Taylor remainder is one half the Hessian at an interior point times the squared step.

Verification

1.1F4F5F6givenalgebra

Differentiation gives $g (x) = x + 10 x / \sqrt{1 + x^{2}}$ , $H (x) = 1 + 10 / (1 + x^{2})^{3 / 2}$ , and $H^{'} (x) = - 30 x / (1 + x^{2})^{5 / 2}$ . Thus $1 \leq H (x) \leq 11$ , $g (x)$ has the sign of $x$ , and $x^{*} = 0$ is the unique minimizer. Also $∣ H^{'} (x) ∣ \leq 30$ , since $∣ x ∣ \leq 1 + x^{2} \leq (1 + x^{2})^{5 / 2}$ ; [F4] makes $H$ globally $30$ -Lipschitz. The initial sublevel set is closed by continuity and bounded because $f (x) \geq x^{2} / 2$ , hence compact by [F5].

1.2F2F6givenalgebra

At $x_{0} = 2$ , $g = 2 + 4 \sqrt{5}$ , $H = 1 + 2 / \sqrt{5}$ , and the Newton direction is $p = - g / H = 30 - 16 \sqrt{5}$ . Its decrement is $λ^{2} = g^{2} / H = 260 - 88 \sqrt{5} > 62$ , since $5 < 81 / 16$ gives $\sqrt{5} < 9 / 4$ ; hence the positive tolerance test does not stop before the first line search.

2.1F3F4F7givenstep 1.1algebrachoose

Step 1.1 gives $g (0) = 0$ , $H (0) = 11 > 0$ , and a $30$ -Lipschitz Hessian on $B (0, 1)$ , so [F3] applies there; we directly verify the local radius $ρ = 10^{- 6}$ and constant $C = 10$ . For $0 < ∣ x ∣ \leq ρ$ , $H (x) \geq 1$ and $∣ g (x) ∣ \leq 11 ∣ x ∣$ , so the Newton direction $p = - g (x) / H (x)$ satisfies $∣ p ∣ \leq 11 ∣ x ∣$ . Every point $ξ$ between $x$ and $x + p$ therefore satisfies $∣ H (ξ) - H (x) ∣ \leq 30 ∣ p ∣ \leq 330 ρ$ . Since $330 ρ = 33 / 100000 < 49 / 50 = 1 - 2 a$ and $H (x) \geq 1$ , we have $H (ξ) \leq H (x) + 330 ρ \leq 2 (1 - a) H (x)$ . Taylor's formula [F7] and $g (x) p = - H (x) p^{2}$ now give $f (x + p) - f (x) - a g (x) p = - (1 - a) H (x) p^{2} + H (ξ) p^{2} / 2 \leq 0$ , so the full step passes Armijo. Also $x + p = (x H (x) - g (x)) / H (x) = - 10 x^{3} / ((1 + x^{2})^{3 / 2} H (x))$ , hence $∣ x + p ∣ \leq 10 ∣ x ∣^{3} \leq 10 ∣ x ∣^{2}$ because $∣ x ∣ \leq ρ < 1$ , and $∣ x + p ∣ \leq 10 ρ^{2} ∣ x ∣ < ρ$ since $10 ρ^{2} = 10^{- 11} < 1$ . Thus $C = 10$ and this $ρ$ give a directly verified invariant local ball and quadratic bound whenever the decrement test permits an update.

2.2F2step 1.2algebra

The full-step point is $x_{1} = 32 - 16 \sqrt{5}$ , whose absolute value exceeds $2$ because $289 / 64 < 5$ gives $\sqrt{5} > 17 / 8$ . The objective is even and strictly increasing as a function of $∣ x ∣ > 0$ , so $f (x_{1}) > f (2)$ ; its Armijo threshold $f (2) + a g p = f (2) - a λ^{2}$ is smaller than $f (2)$ , and the unit step fails.

2.3F2step 1.2algebra

The half-step point is $x_{1 / 2} = 17 - 8 \sqrt{5} = - r$ , where $0 < r = 8 \sqrt{5} - 17 < 1$ : indeed $289 / 64 < 5 < 324 / 64$ implies $17 / 8 < \sqrt{5} < 9 / 4$ . Thus $f (x_{1 / 2}) = r^{2} / 2 + 10 \sqrt{1 + r^{2}} < 1 / 2 + 10 \sqrt{2} < 31 / 2$ , using $2 < 9 / 4$ and so $\sqrt{2} < 3 / 2$ , while $f (2) = 2 + 10 \sqrt{5} > 22$ because $\sqrt{5} > 2$ . The objective drop exceeds $13 / 2$ . The half-step Armijo decrease required is $q / 200$ , where $q = λ^{2} < 84$ because $\sqrt{5} > 2$ , so $q / 200 < 21 / 50 < 13 / 2$ . Hence $t = 1 / 2$ passes, and it is accepted after the failed unit trial.

3.1F1step 2.3step 2.1givenalgebra∎

Choose $V = R$ , which contains every trial segment and $B (0, 1)$ . By step 1.1 the global Hessian bounds are $m = 1$ , $M = 11$ , and the decrement threshold in [F1] is $m^{2} ρ^{2} / (2 M) = 10^{- 12} / 22$ . The chosen $ε = 10^{- 16}$ is smaller, since $22 < 10^{4}$ gives $10^{- 16} < 10^{- 12} / 22$ , so the decrement test cannot stop outside $B (0, ρ)$ . The first accepted step was the damped half-step in step 2.3; [F1] now gives finite entry into the local ball, followed by unit quadratic updates whenever the decrement test does not stop.

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

A small gradient can hide error when the minimizer is ill conditioned

Example

For $f (u, v) = \frac{1}{2} (10^{- 8} u^{2} + v^{2})$ , the exact gradient norm can be tiny at a point a unit distance from the minimizer.

Facts & Assumptions

Given: $f (u, v) = \frac{1}{2} (10^{- 8} u^{2} + v^{2})$ on $R^{2}$ and candidate $\tilde{x} = (1, 0)$ .

[F1]

An inexact gradient residual certifies distance under strong convexity: with strong-convexity constant $μ$ , exact gradient residual $η$ , and discrepancy $δ = 0$ , the distance to the minimizer is at most $η / μ$ .

[F2]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: the gradient consists of the standard-coordinate first partial derivatives.

Verification

1.1F2givenalgebra

The Hessian is $diag (10^{- 8}, 1)$ , so the unique minimizer is $x^{*} = (0, 0)$ and the strong-convexity constant is $μ = 10^{- 8}$ . At $\tilde{x} = (1, 0)$ , $\nabla f (\tilde{x}) = (10^{- 8}, 0)$ , so $η = ∥ \nabla f (\tilde{x}) ∥_{2} = 10^{- 8}$ and the true distance is $∥ \tilde{x} - x^{*} ∥_{2} = 1$ .

2.1F1step 1.1algebra∎

Applying [F1] gives the sharp bound $η / μ = 10^{- 8} / 10^{- 8} = 1$ . The residual is small in absolute size, but the weak curvature in the first coordinate makes this distance bound equal to one rather than a small number.

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

A computed-gradient residual needs its discrepancy bound

Example

On a one-dimensional quadratic, omitting the computed-gradient discrepancy would give a false distance certificate.

Facts & Assumptions

Given: $f (x) = \frac{1}{2} x^{2}$ , minimizer $x^{*} = 0$ , candidate $\tilde{x} = 1 / 10$ , and computed gradient $\hat{g} = 1 / 50$ .

[F1]

An inexact gradient residual certifies distance under strong convexity: if $∥ \hat{g} ∥_{2} \leq η$ and $∥ \hat{g} - \nabla f (\tilde{x}) ∥_{2} \leq δ$ , then $∥ \tilde{x} - x^{*} ∥_{2} \leq (η + δ) / μ$ .

[F2]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: in one dimension the gradient is the ordinary first derivative.

Verification

1.1F2givenalgebra

On $U = R$ , $f$ is $C^{2}$ and $f^{''} (x) = 1$ , so $μ = 1$ . Thus $\nabla f (\tilde{x}) = 1 / 10$ , and the computed residual is $η = ∣ \hat{g} ∣ = 1 / 50$ . The independently verified discrepancy is $δ = ∣ 1 / 50 - 1 / 10 ∣ = 2 / 25$ . The actual distance is $∣ \tilde{x} - x^{*} ∣ = 1 / 10$ .

2.1F1step 1.1algebra∎

The certificate [F1] gives $(η + δ) / μ = (1 / 50 + 2 / 25) = 1 / 10$ , exactly the actual distance. If the discrepancy were omitted, the proposed bound $1 / 50$ would be false.

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

Inner quadrature error enters an outer gradient certificate

Example

The gradient of an integral objective may itself be computed by quadrature. Its quadrature discrepancy must be included separately from the computed-gradient residual.

Facts & Assumptions

Given: $f (x) = \int_{0}^{1} (x - s)^{4} d s$ on $R$ , candidate $\tilde{x} = 3 / 5$ , and the two-panel composite midpoint rule applied to the integral of $\partial_{x} (x - s)^{4}$ .

[F1]

An inexact gradient residual certifies distance under strong convexity: if the computed gradient residual is at most $η$ and its discrepancy from the true gradient is at most $δ$ , then the distance to a $μ$ -strongly convex minimizer is at most $(η + δ) / μ$ .

[F2]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: the gradient is the first derivative in the standard real coordinate.

Verification

1.1F2givenalgebra

Integrating gives $f (x) = (x^{5} - (x - 1)^{5}) / 5$ , hence $f^{'} (x) = x^{4} - (x - 1)^{4}$ and $f^{''} (x) = 12 (x - 1 / 2)^{2} + 1 \geq 1$ . Thus $μ = 1$ is valid and the minimizer is $x^{*} = 1 / 2$ .

1.2F2givenalgebra

At $\tilde{x} = 3 / 5$ , the true gradient is $f^{'} (3 / 5) = 13 / 125 = 104 / 1000$ . The two midpoint nodes are $1 / 4$ and $3 / 4$ , so the composite midpoint estimate is $\hat{g} = \frac{1}{2} (4 (7 / 20)^{3} + 4 (- 3 / 20)^{3}) = 79 / 1000$ . Therefore the computed residual is $η = 79 / 1000$ and the exact discrepancy is $δ = ∣ 104 / 1000 - 79 / 1000 ∣ = 1 / 40 = 25 / 1000$ .

2.1F1step 1.1step 1.2algebra∎

The actual distance is $∣ 3 / 5 - 1 / 2 ∣ = 1 / 10 = 100 / 1000$ . By [F1] the certificate is $(η + δ) / μ = 104 / 1000$ , which is valid and close to the actual distance. The objective's inner integral was evaluated approximately, so its gradient discrepancy was not inferred from the residual.