CounterexampleConstruction: 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 invalid lower bound can prune the true global minimizer

Statement refuted

A branch-and-bound certificate remains sound even when a reported box lower bound can exceed the true infimum on that box.

Construction

Take the unconstrained instance $C = D_{0} = [0, 1]$ , $f (x) = x$ , $ε = 1 / 4$ , and node budget $N = 1$ . The root oracle returns the required exact midpoint witness $x = 1 / 2$ with exact upper bound $U = 1 / 2$ , but the invalid lower bound $ℓ (D_{0}) = 1 / 2$ .

Verification

Given: The algorithm Finite-budget certified spatial branch and bound, except that its oracle violates the lower-bound condition in Certified lower, upper, and emptiness bounds on a box.

[F1] A valid lower bound on a box must be at most the infimum of the feasible objective there. Certified lower, upper, and emptiness bounds on a box

[F2] If all terminal leaves have valid lower bounds, then a gap $U - L \leq ε$ proves global epsilon-optimality. A spatial branch-and-bound gap certificate proves global epsilon-optimality

1.1givenalgebra

The true infimum on $[0, 1]$ is $f^{*} = 0$ , attained at $x = 0$ , whereas the reported value $1 / 2$ is not a lower bound because $1 / 2 > 0 = f^{*}$ .

1.2givenF1algebra

After the single root call, the procedure computes the spurious gap $U - ℓ = 0 \leq 1 / 4$ and returns its midpoint witness without further search, although that witness has error $f (1 / 2) - f^{*} = 1 / 2 > 1 / 4$ . The root containing the true minimizer has therefore been discarded from further search on an invalid certificate.

2.1F1F2step 1.2∎

The claimed certificate contradicts the explicit objective difference, so the stated robustness to invalid lower bounds is false. This does not contradict A spatial branch-and-bound gap certificate proves global epsilon-optimality, whose hypothesis [F1] is violated.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

5 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

Arnold Neumaier, Complete Search in Continuous Global Optimization and Constraint Satisfaction, §12 (standard reference, not scraped)