Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.2, p. 8 — every run of SteepestDescentMML1 from x_σ ∈ M_σ has x_k ∈ M_k for all k ≤ γ, so x_γ is optimal for (MML1)

Proved
MConvexL1.SD.theorem_4_2

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

l1-distance-constraintm-convex-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1steepest-descent

Throughout, VVV is a finite ground set (the paper's N={1,…,n}N = \{1,\dots,n\}N={1,…,n}), vectors are integer vectors x∈ZVx \in \mathbb Z^Vx∈ZV, x(V)=∑vx(v)x(V) = \sum_{v} x(v)x(V)=∑v​x(v), χi\chi_iχi​ is the iii-th unit vector, supp+(z)={v∣z(v)>0}\mathrm{supp}^+(z) = \{v \mid z(v) > 0\}supp+(z)={v∣z(v)>0}, supp−(z)={v∣z(v)<0}\mathrm{supp}^-(z) = \{v \mid z(v) < 0\}supp−(z)={v∣z(v)<0} and ∥z∥1=∑v∣z(v)∣\|z\|_1 = \sum_v |z(v)|∥z∥1​=∑v​∣z(v)∣. The function f:ZV→R∪{+∞}f : \mathbb Z^V \to \mathbb R \cup \{+\infty\}f:ZV→R∪{+∞} is M-convex (in the paper's sense, p. 4), its effective domain dom⁡f\operatorname{dom} fdomf is bounded, and the center xc∈ZVx_c \in \mathbb Z^Vxc​∈ZV satisfies xc(V)=θx_c(V) = \thetaxc​(V)=θ where dom⁡f⊆{x∣x(V)=θ}\operatorname{dom} f \subseteq \{x \mid x(V) = \theta\}domf⊆{x∣x(V)=θ}; the center need not lie in dom⁡f\operatorname{dom} fdomf. For k∈Z+k \in \mathbb Z_+k∈Z+​, MkM_kMk​ is the set of optimal solutions of

(MML1(k))min⁡{f(x)∣x∈dom⁡f, ∥x−xc∥1≤2k},(\mathrm{MML1}(k))\qquad \min\{ f(x) \mid x \in \operatorname{dom} f,\ \|x - x_c\|_1 \le 2k\},(MML1(k))min{f(x)∣x∈domf, ∥x−xc​∥1​≤2k},

and σ,τ∈Z+\sigma, \tau \in \mathbb Z_+σ,τ∈Z+​ are defined by (4.1): 2σ=min⁡{∥x−xc∥1∣x∈dom⁡f}2\sigma = \min\{\|x - x_c\|_1 \mid x \in \operatorname{dom} f\}2σ=min{∥x−xc​∥1​∣x∈domf} and 2τ=min⁡{∥x−xc∥1∣x∈arg⁡min⁡f}2\tau = \min\{\|x - x_c\|_1 \mid x \in \arg\min f\}2τ=min{∥x−xc​∥1​∣x∈argminf}.

Algorithm SteepestDescentMML1 (p. 8), for an integer γ≥σ\gamma \ge \sigmaγ≥σ: Step 0: choose xσ∈Mσx_\sigma \in M_\sigmaxσ​∈Mσ​ and set k:=σ+1k := \sigma + 1k:=σ+1. Step 1: if k−1=γk - 1 = \gammak−1=γ, output xk−1x_{k-1}xk−1​ and stop. Step 2: find ik,jk∈Vi_k, j_k \in Vik​,jk​∈V minimizing f(xk−1+χik−χjk)f(x_{k-1} + \chi_{i_k} - \chi_{j_k})f(xk−1​+χik​​−χjk​​) over all pairs. Step 3: set xk:=xk−1+χik−χjkx_k := x_{k-1} + \chi_{i_k} - \chi_{j_k}xk​:=xk−1​+χik​​−χjk​​, k:=k+1k := k + 1k:=k+1, and go to Step 1.

Theorem. Every run of the algorithm, with any choice in Step 0 and any tie-breaking in Step 2, outputs after γ−σ\gamma - \sigmaγ−σ iterations an optimal solution of

(MML1)min⁡{f(x)∣x(V)=θ, ∥x−xc∥1≤2γ, x∈dom⁡f};(\mathrm{MML1})\qquad \min\{ f(x) \mid x(V) = \theta,\ \|x - x_c\|_1 \le 2\gamma,\ x \in \operatorname{dom} f\};(MML1)min{f(x)∣x(V)=θ, ∥x−xc​∥1​≤2γ, x∈domf};

moreover every iterate satisfies xk∈Mkx_k \in M_kxk​∈Mk​ for σ≤k≤γ\sigma \le k \le \gammaσ≤k≤γ.

This is the paper's pseudo-polynomial algorithm for M-convex minimization under an ℓ1\ell_1ℓ1​-distance constraint: greedy single exchanges started at the nearest feasible point are optimal at every radius simultaneously. In the bike-sharing application (§3, §6) the radius is the number of docks moved.

Differences from the source:

  • generalization: N = {1, …, n} with n ≥ 2 (§2, p. 4) → an arbitrary finite type V with decidable equality (any cardinality, including 0 and 1); reason: taking V = Fin n with n ≥ 2 gives the paper's setting; for |V| ≤ 1 the hypotheses force dom f to be at most one point and the statement still holds
  • generalization: the standing assumption τ > γ of §4 (p. 8: "Hence, we assume τ > γ in the following") → no assumption relating τ and γ; τ does not appear; reason: for γ < τ it is the printed theorem; for k ≥ τ one has M_k = {x ∈ arg min f | ‖x − x_c‖₁ ≤ 2k} (p. 8), and the paper itself applies the theorem with γ = τ (Corollary A.5, p. 19)
  • encoding: f : ℤⁿ → ℝ ∪ {+∞} → f : (V → ℤ) → WithTop ℝ, dom f = {x | f x ≠ ⊤}; reason: Lean convention for ℝ ∪ {+∞}; same instances
  • encoding: ‖x − y‖₁ = Σ |x(i) − y(i)| → L1Dist x y = Σ_v |x v − y v| as a natural number; reason: the norm is a nonnegative integer; same values
  • encoding: M-convex: (M♮-EXC) with ∃ j ∈ supp⁻(x − y) ∪ {0}, χ₀ = 0, and dom f in a hyperplane {x(N) = θ} (p. 4) → MConvex f := MNatExchangeAxiom f ∧ ∃ θ, ∀ x ∈ dom f, Σ x = θ, where MNatExchangeAxiom states f(x) + f(y) ≥ min(f(x − χ_i) + f(y + χ_i), min_{j ∈ supp⁻(x−y)} (f(x − χ_i + χ_j) + f(y + χ_i − χ_j))); reason: a minimum over a finite set in the linear order WithTop ℝ is attained, so the min form is the existential with j = 0 meaning χ₀ = 0
  • encoding: dom f ⊆ {x | x(N) = θ} and x_c(N) = θ (p. 2), x_c possibly outside dom f (p. 7) → hxc : ∀ x ∈ dom f, Σ_v x v = Σ_v xc v, with θ eliminated; xc ∈ dom f is not assumed; reason: same condition with θ := x_c(N)
  • encoding: σ = (1/2) min{‖x − x_c‖₁ | x ∈ dom f} (4.1) → σ : ℕ with IsLeast {‖x − x_c‖₁ | x ∈ dom f} (2σ); reason: under hxc every such distance is even, so this is the paper's half-minimum; it also records dom f ≠ ∅, which the paper's min presupposes
  • encoding: M_k = set of optimal solutions of (MML1(k)): minimize f(x) s.t. x(N) = θ, ‖x − x_c‖₁ ≤ 2k, x ∈ dom f (pp. 2, 8) → Mset f xc k = {x ∈ dom f | ‖x − x_c‖₁ ≤ 2k ∧ ∀ y ∈ dom f, ‖y − x_c‖₁ ≤ 2k → f x ≤ f y}; reason: the constraint x(N) = θ is implied by x ∈ dom f under hxc, so omitting it changes no instance
  • encoding: the algorithm stops after γ − σ iterations, which presupposes γ ≥ σ → hypothesis σ ≤ γ; reason: for γ < σ the problem (MML1) is infeasible and Step 1 never fires; the hypothesis only excludes this undefined case
  • encoding: Algorithm SteepestDescentMML1, Steps 0–3 (p. 8), with any choice in Step 0 and any tie-break in Step 2 → IsSDRun f xc σ γ x: x σ ∈ M_σ and, for σ < k ≤ γ, x k = x (k−1) + χ_i − χ_j for a pair (i, j) ∈ V × V minimizing f(x (k−1) + χ_i − χ_j) over all pairs; reason: the run is the sequence of iterates; quantifying over every such sequence covers every execution
  • encoding: "outputs an optimal solution of (MML1)" → x γ ∈ M_γ; reason: M_γ is exactly the set of optimal solutions of (MML1) with radius 2γ
Preamble
import Mathlib
import Definitions.Def_MConvexL1_SD_Basic
import Definitions.Def_DiscreteConvex_MConvexFunctions_MExchangeAxiom
import Definitions.Def_DiscreteConvex_MConvexFunctions_ArgMin
open DiscreteConvex.MConvexFunctions DiscreteConvex.Algorithms
Formal statement
namespace MConvexL1.SD

theorem theorem_4_2 {V : Type*} [Fintype V] [DecidableEq V] (f : (V → ℤ) → WithTop ℝ)
    (hf : MConvex f) (hbdd : BddDom f) (xc : V → ℤ)
    (hxc : ∀ x ∈ DomZ f, ∑ v, x v = ∑ v, xc v)
    (σ γ : ℕ) (hσ : IsLeast {d | ∃ x ∈ DomZ f, L1Dist x xc = d} (2 * σ)) (hγ : σ ≤ γ)
    (x : ℕ → V → ℤ) (hrun : IsSDRun f xc σ γ x) :
    (∀ k, σ ≤ k → k ≤ γ → x k ∈ Mset f xc k) ∧ x γ ∈ Mset f xc γ := by sorry

end MConvexL1.SD
Source
Shioura, M-convex Function Minimization Under L1-Distance Constraint, arXiv:1809.03126v3, p. 8, Theorem 4.2 (algorithm SteepestDescentMML1, p. 8)
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 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