Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Convergence theorem — the convex-envelope branch-and-bound algorithm converges to a global solution of Problem P\mathcal PP

Disproved
BiconvexProg.BranchBound.branch_and_bound_converges

by mikedeng1 · Sep 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

bilinear-programmingbranch-and-boundglobal-optimizationp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let S⊆Rn×RnS \subseteq \mathbb{R}^n \times \mathbb{R}^nS⊆Rn×Rn be closed and convex, let Ω={(x,y):l≤x≤L, m≤y≤M}\Omega = \{(x,y) : l \le x \le L,\ m \le y \le M\}Ω={(x,y):l≤x≤L, m≤y≤M} with l≤Ll \le Ll≤L and m≤Mm \le Mm≤M, and let fff and ggg be convex and continuous on {x:l≤x≤L}\{x : l \le x \le L\}{x:l≤x≤L} and {y:m≤y≤M}\{y : m \le y \le M\}{y:m≤y≤M}. Assume S∩Ω≠∅S \cap \Omega \ne \emptysetS∩Ω=∅ and n>0n > 0n>0. Consider Problem P\mathcal PP,

min⁡ φ(x,y)=f(x)+x⊤y+g(y)subject to (x,y)∈S∩Ω.\min\ \varphi(x,y) = f(x) + x^\top y + g(y) \quad \text{subject to } (x,y) \in S \cap \Omega .min φ(x,y)=f(x)+x⊤y+g(y)subject to (x,y)∈S∩Ω.

Run the branch-and-bound algorithm of Al-Khayyal and Falk. It starts from Ω\OmegaΩ, lower-bounds each node BBB by ψB=f+VexB x⊤y+g\psi^B = f + \mathrm{Vex}_B\, x^\top y + gψB=f+VexB​x⊤y+g, selects an open node by the Best Bound Rule, and splits it at its subproblem solution along the coordinate with the largest gap xiyi−VexBi xiyix_i y_i - \mathrm{Vex}_{B_i}\, x_i y_ixi​yi​−VexBi​​xi​yi​. Let (xk,yk)(x^k, y^k)(xk,yk) be the stage points, vbkv_b^kvbk​ the best lower bounds and VbkV_b^kVbk​ the best upper bounds. Then:

  1. every accumulation point (xˉ,yˉ)(\bar x, \bar y)(xˉ,yˉ​) of ((xk,yk))k\big((x^k, y^k)\big)_k((xk,yk))k​ lies in S∩ΩS \cap \OmegaS∩Ω and is a global solution of Problem P\mathcal PP;
  2. the optimal value v∗=min⁡S∩Ωφv^* = \min_{S \cap \Omega} \varphiv∗=minS∩Ω​φ is attained, and
lim⁡k→∞vbk=v∗=lim⁡k→∞Vbk.\lim_{k\to\infty} v_b^k = v^* = \lim_{k \to \infty} V_b^k .k→∞lim​vbk​=v∗=k→∞lim​Vbk​.

The paper never states this as one sentence. It announces on p. 279 that "the best lower bounds increase towards v∗v^*v∗, while the best upper bounds decrease towards v∗v^*v∗. It remains to show that the procedure converges to a global solution", and its convergence proof ends with ψˉ(xˉ,yˉ)=φ(xˉ,yˉ)\bar\psi(\bar x,\bar y) = \varphi(\bar x,\bar y)ψˉ​(xˉ,yˉ​)=φ(xˉ,yˉ​) 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 000. Continuity of fff and ggg 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.

Preamble
import Mathlib
import Definitions.Def_BiconvexProg_BranchBound_run
Formal statement
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
Source
Al-Khayyal, Falk, Jointly Constrained Biconvex Programming, Math. Oper. Res. 8(2), 1983, pp. 279–282, Convergence proof (announced p. 279; concluding identity p. 280)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Fix a natural number nnn. Write Rn\mathbb{R}^nRn for real nnn-tuples, and give Rn×Rn\mathbb{R}^n \times \mathbb{R}^nRn×Rn the usual product (Euclidean) topology. The statement is universally quantified over the following data:

  • a set S⊆Rn×RnS \subseteq \mathbb{R}^n \times \mathbb{R}^nS⊆Rn×Rn;
  • two real-valued functions f,g:Rn→Rf, g : \mathbb{R}^n \to \mathbb{R}f,g:Rn→R;
  • an object Ω\OmegaΩ of type Boxn\mathrm{Box}_nBoxn​. This type is defined in the imported module Definitions.Def_BiconvexProg_BranchBound_run, which is not reproduced here. Ω\OmegaΩ has an associated point set set⁡(Ω)⊆Rn×Rn\operatorname{set}(\Omega) \subseteq \mathbb{R}^n \times \mathbb{R}^nset(Ω)⊆Rn×Rn. How that set is built from Ω\OmegaΩ is fixed by the imported module.
  • a sequence (Nk)k∈N(\mathcal{N}_k)_{k \in \mathbb{N}}(Nk​)k∈N​, where each Nk\mathcal{N}_kNk​ is a finite multiset of boxes (elements of Boxn\mathrm{Box}_nBoxn​), so repeats are allowed;
  • a sequence of boxes (Bk)k∈N(B_k)_{k \in \mathbb{N}}(Bk​)k∈N​ (called sel);
  • a sequence of coordinate indices (ik)k∈N(i_k)_{k \in \mathbb{N}}(ik​)k∈N​ with each ik∈{0,…,n−1}i_k \in \{0, \dots, n-1\}ik​∈{0,…,n−1} (called idx);
  • a sequence of points (zk)k∈N=((xk,yk))k∈N(z^k)_{k \in \mathbb{N}} = ((x^k, y^k))_{k \in \mathbb{N}}(zk)k∈N​=((xk,yk))k∈N​ in Rn×Rn\mathbb{R}^n \times \mathbb{R}^nRn×Rn (called pt).

Hypotheses. There are exactly two:

  1. IsProblemP(S,f,g,Ω)\mathrm{IsProblemP}(S, f, g, \Omega)IsProblemP(S,f,g,Ω) holds.
  2. IsRun(S,f,g,Ω,(Nk),(Bk),(ik),(zk))\mathrm{IsRun}(S, f, g, \Omega, (\mathcal{N}_k), (B_k), (i_k), (z^k))IsRun(S,f,g,Ω,(Nk​),(Bk​),(ik​),(zk)) holds.

Both predicates are defined in the imported module. Their content, and so exactly what they require of S,f,g,ΩS, f, g, \OmegaS,f,g,Ω and of the four sequences, is not visible in this declaration. The sequences (Nk)(\mathcal{N}_k)(Nk​) and (ik)(i_k)(ik​) appear only in the second hypothesis and nowhere in the conclusion.

Conclusion. Let K=S∩set⁡(Ω)K = S \cap \operatorname{set}(\Omega)K=S∩set(Ω). Let Φf,g:Rn×Rn→R\Phi_{f,g} : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}Φf,g​:Rn×Rn→R be the imported function objective f g. The statement asserts both of the following.

(1) Cluster points are feasible minimisers. Call zˉ∈Rn×Rn\bar z \in \mathbb{R}^n \times \mathbb{R}^nzˉ∈Rn×Rn a cluster point of (zk)(z^k)(zk) if every neighbourhood of zˉ\bar zzˉ contains zkz^kzk for infinitely many kkk. For every such zˉ\bar zzˉ:

zˉ∈KandΦf,g(zˉ)≤Φf,g(z)  for all z∈K.\bar z \in K \quad\text{and}\quad \Phi_{f,g}(\bar z) \le \Phi_{f,g}(z) \ \text{ for all } z \in K.zˉ∈KandΦf,g​(zˉ)≤Φf,g​(z)  for all z∈K.

(2) An attained minimum value that both bound sequences reach. There is a real number v∗v^\astv∗ with all four of these properties:

  • some z∈Kz \in Kz∈K has Φf,g(z)=v∗\Phi_{f,g}(z) = v^\astΦf,g​(z)=v∗, so KKK is nonempty and v∗v^\astv∗ is attained;
  • v∗≤Φf,g(z)v^\ast \le \Phi_{f,g}(z)v∗≤Φf,g​(z) for every z∈Kz \in Kz∈K, so v∗=min⁡KΦf,gv^\ast = \min_{K} \Phi_{f,g}v∗=minK​Φf,g​;
  • the real sequence LkL_kLk​ converges to v∗v^\astv∗ as k→∞k \to \inftyk→∞, where LkL_kLk​ is the kkk-th term of the imported bestLower f g sel pt. It depends on fff, ggg, the boxes (Bk)(B_k)(Bk​) and the points (zk)(z^k)(zk).
  • the real sequence UkU_kUk​ converges to v∗v^\astv∗ as k→∞k \to \inftyk→∞, where UkU_kUk​ is the kkk-th term of the imported bestUpper f g pt. It depends only on fff, ggg and the points (zk)(z^k)(zk).

The statement does not say how Φf,g\Phi_{f,g}Φf,g​, LkL_kLk​ or UkU_kUk​ are computed from their arguments. It also does not assert any ordering between LkL_kLk​, UkU_kUk​ and v∗v^\astv∗ (for example, that Lk≤v∗≤UkL_k \le v^\ast \le U_kLk​≤v∗≤Uk​), 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 v∗v^\astv∗.

Degenerate cases.

  • Contradictory or vacuous hypotheses. Part (2) requires K=S∩set⁡(Ω)K = S \cap \operatorname{set}(\Omega)K=S∩set(Ω) to be nonempty and Φf,g\Phi_{f,g}Φf,g​ to attain its infimum on KKK. So if the two hypotheses could hold together with KKK empty, or with no minimiser on KKK, the statement would be contradictory. Whether IsProblemP\mathrm{IsProblemP}IsProblemP or IsRun\mathrm{IsRun}IsRun 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 (zk)(z^k)(zk) has no cluster point, for example when ∥zk∥→∞\|z^k\| \to \infty∥zk∥→∞. Boundedness of (zk)(z^k)(zk) is not asserted in the conclusion. It holds only if the imported hypotheses force it.
  • n=0n = 0n=0. Then R0×R0\mathbb{R}^0 \times \mathbb{R}^0R0×R0 is a single point ∗\ast∗. There are no indices in {0,…,n−1}\{0, \dots, n-1\}{0,…,n−1}, so no sequence (ik)(i_k)(ik​) can exist, and the statement is vacuously true for n=0n = 0n=0. The same conclusion follows from the fact that all zkz^kzk equal ∗\ast∗: then ∗\ast∗ is the only cluster point and K⊆{∗}K \subseteq \{\ast\}K⊆{∗}.
  • Default values. Suppose LkL_kLk​ or UkU_kUk​ 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 000 for real inf⁡\infinf/sup⁡\supsup of an empty or unbounded set, and x/0=0x/0 = 0x/0=0). The asserted convergences concern those actual values, whatever they are. Whether such cases arise depends on the imported definitions, which are not shown.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me