Theorem 4.1 (ii), p. 8, part (ii) of 3 ((i), (iii) are theorem_4_1_i, theorem_4_1_iii) — every y ∈ M_k has a neighbour y + χ_i − χ_j in M_{k+1} moving away from x_c
ProvedMConvexL1.SD.theorem_4_1_iil1-distance-constraintm-convex-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1steepest-descent
Throughout, is a finite ground set (the paper's ), vectors are integer vectors , , is the -th unit vector, , and . The function is M-convex (in the paper's sense, p. 4), its effective domain is bounded, and the center satisfies where ; the center need not lie in . For , is the set of optimal solutions of
and are defined by (4.1): and .
Then for every integer and every there is some of the form
Part (ii) of Theorem 4.1; parts (i) and (iii) are separate items. It is the step that makes steepest descent from the center work: one exchange suffices to pass from an optimum at radius to an optimum at radius .
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
- 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: τ = (1/2) min{‖x − x_c‖₁ | x ∈ arg min f} (4.1) → τ : ℕ with IsLeast {‖x − x_c‖₁ | x ∈ arg min f} (2τ); reason: same reason as for σ; arg min f ≠ ∅ follows from bounded dom f (p. 7)
- 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
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_1_ii {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τ : IsLeast {d | ∃ x ∈ ArgMin f, L1Dist x xc = d} (2 * τ)) :
∀ k, σ ≤ k → k < τ → ∀ y ∈ Mset f xc k, ∃ i j : V, i ∉ SuppNeg y xc ∧ j ∉ SuppPos y xc ∧
(fun w => y w + CharVec i w - CharVec j w) ∈ Mset f xc (k + 1) := by sorry
end MConvexL1.SD
Source
Shioura, M-convex Function Minimization Under L1-Distance Constraint, arXiv:1809.03126v3, p. 8, Theorem 4.1 (ii) (proof Appendix A.2, pp. 17–18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.