Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Invariant of the Newton–Dinkelbach method: g(i)<0g^{(i)}<0g(i)<0 unless f(δ(i))=0f(\delta^{(i)})=0f(δ(i))=0, and then δ(i)=δ∗\delta^{(i)}=\delta^*δ(i)=δ∗

Proved
AccelNewtonDinkelbach.run_invariant

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

bregman-divergenceconcave-functionsfractional-programmingnewton-dinkelbachp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1root-finding

Let f:R→Rˉf:\mathbb R\to\bar{\mathbb R}f:R→Rˉ be a proper concave function, let δ∗=max⁡({δ:f(δ)=0}∪arg⁡max⁡f)\delta^*=\max(\{\delta:f(\delta)=0\}\cup\arg\max f)δ∗=max({δ:f(δ)=0}∪argmaxf) (assumed to exist), and let δ(1),…,δ(N)\delta^{(1)},\dots,\delta^{(N)}δ(1),…,δ(N) with supergradients g(1),…,g(N)g^{(1)},\dots,g^{(N)}g(1),…,g(N) be the iterates of a Newton–Dinkelbach-type run: the input satisfies δ(1)∈dom⁡(f)\delta^{(1)}\in\operatorname{dom}(f)δ(1)∈dom(f), f(δ(1))≤0f(\delta^{(1)})\le0f(δ(1))≤0, g(1)∈∂f(δ(1))g^{(1)}\in\partial f(\delta^{(1)})g(1)∈∂f(δ(1)), g(1)<0g^{(1)}<0g(1)<0, and each later pair arises from the previous one by a standard Newton–Dinkelbach update or by a successful look-ahead. Then for every 1≤i≤N1\le i\le N1≤i≤N:

  1. δ(i)∈dom⁡(f)\delta^{(i)}\in\operatorname{dom}(f)δ(i)∈dom(f), g(i)∈∂f(δ(i))g^{(i)}\in\partial f(\delta^{(i)})g(i)∈∂f(δ(i)) and f(δ(i))≤0f(\delta^{(i)})\le 0f(δ(i))≤0;
  2. if f(δ(i))<0f(\delta^{(i)})<0f(δ(i))<0 then g(i)<0g^{(i)}<0g(i)<0;
  3. if f(δ(i))=0f(\delta^{(i)})=0f(δ(i))=0 then δ(i)=δ∗\delta^{(i)}=\delta^*δ(i)=δ∗.

This is the invariant behind the correctness of the method: the supergradient stays negative except possibly in the final iteration, where the method stops at a root, and that root is the largest one. It also guarantees that the Newton step δ(i)−f(δ(i))/g(i)\delta^{(i)}-f(\delta^{(i)})/g^{(i)}δ(i)−f(δ(i))/g(i) never divides by zero.

Differences from the source:

  • encoding: proper concave f : ℝ → R̄ → dom : Set ℝ and f : ℝ → ℝ with ConcaveOn ℝ dom f; reason: x ∉ dom means f(x) = −∞; the effective domain of a proper concave function is convex and the values of f off dom are never used; same instances
  • encoding: δ* := max({δ : f(δ) = 0} ∪ arg max f(δ)), assumed well defined → hypothesis IsDeltaStar dom f δstar (δstar is the greatest element of the roots and maximizers of f in dom); reason: the page's max is a greatest element; the hypothesis is exactly that it exists
  • encoding: iterations of the algorithm with value and supergradient oracles → 1-indexed run prefixes δ(1..N), g(1..N) (IsRun), with the oracle answers existentially chosen at every call; reason: every execution with any oracle, stopped after any iteration, is such a run, and every such run is an execution prefix
  • encoding: g ∈ ∂f(δ) on lines 4 and 8 (empty only if f(δ) = −∞) → Newton point in dom with ∂f empty: no next iterate; look-ahead guess in dom with ∂f empty: the look-ahead fails; reason: the page's iteration cannot be executed, resp. its test cannot pass; no execution of the page is excluded
  • generalization: the standard Newton–Dinkelbach method of p.6 → every run of RelaxedStep: at each iteration either the standard update or a successful look-ahead, chosen freely; reason: runs of the standard method and of Algorithm 1 are relaxed runs (LookAheadStep implies RelaxedStep), so the statement specializes to both
  • encoding: g(i) < 0 except possibly in the final iteration when f(δ(i)) = 0 → f(δ(i)) < 0 → g(i) < 0 for every iterate; reason: the loop stops exactly at the first iterate with f(δ(i)) = 0, so "not the final iteration" is f(δ(i)) < 0
Preamble
import Mathlib
import Definitions.Def_AccelNewtonDinkelbach_IsDeltaStar
import Definitions.Def_AccelNewtonDinkelbach_RelaxedStep
import Definitions.Def_AccelNewtonDinkelbach_IsRun
Formal statement
namespace AccelNewtonDinkelbach

/-- **Invariant of the Newton–Dinkelbach method: `g(i) < 0` unless `f(δ(i)) = 0`, and then `δ(i) = δ*`.**
Dadush, Koh, Natura, Végh, arXiv:2004.08634v4, §3, p.6: "At the start of every iteration i ≥ 1, it
maintains a point δ(i) ∈ dom(f) and a supergradient g(i) ∈ ∂f(δ(i)) where f(δ(i)) ≤ 0." and
"According to this update rule, observe that g(i) < 0 except possibly in the final iteration when
f(δ(i)) = 0. This proves the correctness of the algorithm. Indeed, δ(i) = δ∗ if f(δ(i)) = 0."

For every proper concave `f` (encoded as `(dom, f)` with `f` concave on `dom`), every `δ*` as in
`IsDeltaStar`, every run `δ(1..N)`, `g(1..N)` of relaxed steps (standard Newton–Dinkelbach or
look-ahead updates), and every `1 ≤ i ≤ N`: `δ(i) ∈ dom`, `g(i) ∈ ∂f(δ(i))`, `f(δ(i)) ≤ 0`;
if `f(δ(i)) < 0` then `g(i) < 0`; and if `f(δ(i)) = 0` then `δ(i) = δ*`.

**Formalization Note** Only `i = 1` is assumed (the input of the algorithm); the other iterates
come from the step relation, which contains no monotonicity or sign assumption on `g`. Relaxed
runs include the runs of Algorithm 1. -/
theorem run_invariant (dom : Set ℝ) (f : ℝ → ℝ) (hf : ConcaveOn ℝ dom f)
    (δstar : ℝ) (hstar : IsDeltaStar dom f δstar)
    (δ g : ℕ → ℝ) (N : ℕ) (hrun : IsRun (RelaxedStep dom f) dom f δ g N)
    (i : ℕ) (hi : 1 ≤ i) (hiN : i ≤ N) :
    δ i ∈ dom ∧ g i ∈ superdiff dom f (δ i) ∧ f (δ i) ≤ 0 ∧
      (f (δ i) < 0 → g i < 0) ∧ (f (δ i) = 0 → δ i = δstar) := by sorry

end AccelNewtonDinkelbach
Source
Dadush, Koh, Natura, Végh, arXiv:2004.08634v4, §3, p.6 ("it maintains a point δ(i) ∈ dom(f) and a supergradient g(i) ∈ ∂f(δ(i)) where f(δ(i)) ≤ 0"; "observe that g(i) < 0 except possibly in the final iteration when f(δ(i)) = 0 … Indeed, δ(i) = δ∗ if f(δ(i)) = 0")
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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