Convergence theorem — the convex-envelope branch-and-bound algorithm converges to a global solution of Problem
DisprovedBiconvexProg.BranchBound.branch_and_bound_convergesLet be closed and convex, let with and , and let and be convex and continuous on and . Assume and . Consider Problem ,
Run the branch-and-bound algorithm of Al-Khayyal and Falk. It starts from , lower-bounds each node by , selects an open node by the Best Bound Rule, and splits it at its subproblem solution along the coordinate with the largest gap . Let be the stage points, the best lower bounds and the best upper bounds. Then:
- every accumulation point of lies in and is a global solution of Problem ;
- the optimal value is attained, and
The paper never states this as one sentence. It announces on p. 279 that "the best lower bounds increase towards , while the best upper bounds decrease towards . It remains to show that the procedure converges to a global solution", and its convergence proof ends with at a limit point of any convergent subsequence of stage points. Part 1 is what convergence to a global solution means for an infinite branch-and-bound procedure. Part 2 makes precise the two monotone limits of p. 279.
Formalization Note Runs are infinite and ignore the stopping test; a run the paper stops is a prefix of such a run. Stages are numbered from . Continuity of and is an added hypothesis that the paper takes for granted. The optional pruning of p. 278 is omitted. The paper's proof relies on two intermediate claims that are false as printed, the well-definedness of the stage function on shared faces (p. 277) and the equicontinuity of the stage functions (p. 282). Only the theorem, not that proof, is formalized.
import Mathlib import Definitions.Def_BiconvexProg_BranchBound_run
namespace BiconvexProg.BranchBound
open Filter Topology
/-- Convergence theorem ("Convergence proof", pp. 279–282): along every run of the convex-envelope
branch-and-bound algorithm on Problem 𝒫,
1. every accumulation point of the stage points `(xᵏ, yᵏ)` is feasible and globally minimises
`φ` over `S ∩ Ω`;
2. the best lower bounds `v_bᵏ` and 3. the best upper bounds `V_bᵏ` converge to the optimal value
`v*`. -/
theorem branch_and_bound_converges {n : ℕ} {S : Set ((Fin n → ℝ) × (Fin n → ℝ))}
{f g : (Fin n → ℝ) → ℝ} {Ω : Box n} (hP : IsProblemP S f g Ω)
{nodes : ℕ → Multiset (Box n)} {sel : ℕ → Box n} {idx : ℕ → Fin n}
{pt : ℕ → (Fin n → ℝ) × (Fin n → ℝ)} (hrun : IsRun S f g Ω nodes sel idx pt) :
(∀ zbar, MapClusterPt zbar atTop pt →
zbar ∈ S ∩ Ω.toSet ∧ IsMinOn (objective f g) (S ∩ Ω.toSet) zbar) ∧
∃ vstar : ℝ, (∃ z ∈ S ∩ Ω.toSet, objective f g z = vstar) ∧
(∀ z ∈ S ∩ Ω.toSet, vstar ≤ objective f g z) ∧
Tendsto (bestLower f g sel pt) atTop (𝓝 vstar) ∧
Tendsto (bestUpper f g pt) atTop (𝓝 vstar) := by sorry
end BiconvexProg.BranchBound
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Fix a natural number . Write for real -tuples, and give the usual product (Euclidean) topology. The statement is universally quantified over the following data:
- a set ;
- two real-valued functions ;
- an object of type . This type is defined in the imported module
Definitions.Def_BiconvexProg_BranchBound_run, which is not reproduced here. has an associated point set . How that set is built from is fixed by the imported module. - a sequence , where each is a finite multiset of boxes (elements of ), so repeats are allowed;
- a sequence of boxes (called
sel); - a sequence of coordinate indices with each (called
idx); - a sequence of points in (called
pt).
Hypotheses. There are exactly two:
- holds.
- holds.
Both predicates are defined in the imported module. Their content, and so exactly what they require of and of the four sequences, is not visible in this declaration. The sequences and appear only in the second hypothesis and nowhere in the conclusion.
Conclusion. Let . Let be the imported function objective f g. The statement asserts both of the following.
(1) Cluster points are feasible minimisers. Call a cluster point of if every neighbourhood of contains for infinitely many . For every such :
(2) An attained minimum value that both bound sequences reach. There is a real number with all four of these properties:
- some has , so is nonempty and is attained;
- for every , so ;
- the real sequence converges to as , where is the -th term of the imported
bestLower f g sel pt. It depends on , , the boxes and the points . - the real sequence converges to as , where is the -th term of the imported
bestUpper f g pt. It depends only on , and the points .
The statement does not say how , or are computed from their arguments. It also does not assert any ordering between , and (for example, that ), and does not assert that either sequence is monotone. Only the two convergences are asserted. The convergence is ordinary convergence of real numbers, so both sequences must end up with finite real values close to .
Degenerate cases.
- Contradictory or vacuous hypotheses. Part (2) requires to be nonempty and to attain its infimum on . So if the two hypotheses could hold together with empty, or with no minimiser on , the statement would be contradictory. Whether or rules this out cannot be seen from this declaration. If the two hypotheses can never hold together, the theorem is vacuously true.
- No cluster points. Part (1) says nothing when has no cluster point, for example when . Boundedness of is not asserted in the conclusion. It holds only if the imported hypotheses force it.
- . Then is a single point . There are no indices in , so no sequence can exist, and the statement is vacuously true for . The same conclusion follows from the fact that all equal : then is the only cluster point and .
- Default values. Suppose or is defined through an infimum or supremum over a possibly empty or unbounded set, or through a division. Then Lean's total definitions would give a default value there (typically for real / of an empty or unbounded set, and ). The asserted convergences concern those actual values, whatever they are. Whether such cases arise depends on the imported definitions, which are not shown.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.