The Multiplier Step Size of Two-Block ADMM

Source excerpts; proofs omitted.

Algorithm 1.1.1

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Algorithm 1.1.1: A trajectory of the relaxed two-block ADMM method for a closed proper convex linearly constrained problem. The penalty β and multiplier factor γ are positive. The first update minimizes with y k, the second minimizes with the already updated x (k + 1), and only the multiplier update contains γ.

#check (ADMM.Trajectory.admissible_spec : ∀ {n₁ n₂ m : ℕ} {P : ADMM.Problem n₁ n₂ m} {β γ : ℝ} (t : ADMM.Trajectory P β γ), t.IsAdmissible ↔ P.IsClosedProperConvex ∧ 0 < β ∧ 0 < γ ∧ ∀ k, ADMM.IsFiniteMinimizer (P.firstBlockObjective β (t.multiplier k) (t.y k)) (t.x (k + 1)) ∧ ADMM.IsFiniteMinimizer (P.secondBlockObjective β (t.multiplier k) (t.x (k + 1))) (t.y (k + 1)) ∧ t.multiplier (k + 1) = t.multiplier k + (γ * β) • (P.A.mulVec (t.x (k + 1)) + P.B.mulVec (t.y (k + 1)) - P.b))

Definition 2.1.1

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Definition 2.1.1 (1): the KKT set and its three defining conditions.

#check ADMM.Problem.kktSet

Theorem 2.1.2

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Theorem 2.1.2 (1): for an exact ADMM trajectory with closed proper convex objectives, a KKT solution, 0 < β, and 0 < γ ≤ 377 / 200, the first constraint images converge.

#check (ADMM.leftImage_tendsto : ∀ {n₁ n₂ m : ℕ} (P : ADMM.Problem n₁ n₂ m), ADMM.IsClosedProperConvex P.f → ADMM.IsClosedProperConvex P.g → (∃ x y multiplier, P.IsKKT x y multiplier) → ∀ {β γ : ℝ}, 0 < β → 0 < γ → γ ≤ (377 : ℝ) / 200 → ∀ z : ADMM.Trajectory P β γ, ∃ q : Fin m → ℝ, Filter.Tendsto (fun k ↦ P.A.mulVec (z.x k)) Filter.atTop (nhds q))

Theorem 2.1.3

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Theorem 2.1.3 (1): fixed compact convex polytopes give exact-period counterexamples for every multiplier factor at least criticalFactor.

namespace ConsensusADMM #check ConsensusADMM.fixedPolytopes

Theorem 2.1.4

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Theorem 2.1.4 (1): one fixed pair of compact convex polytopes in ℝ⁹⁶ supports, for every multiplier factor at least ConsensusADMM.criticalFactor, a unique-update consensus ADMM trajectory of exact period 48 and constant positive residual.

#check (ConsensusADMM.fixedPolytopes : ∃ X Y : Set (EuclideanSpace ℝ (Fin 96)), ConsensusADMM.IsCompactConvexPolytope X ∧ ConsensusADMM.IsCompactConvexPolytope Y ∧ ConsensusADMM.IsKKT (ConsensusADMM.extendedIndicator X) (ConsensusADMM.extendedIndicator Y) 0 0 0 ∧ ConsensusADMM.IsPrimalMinimizer (ConsensusADMM.extendedIndicator X) (ConsensusADMM.extendedIndicator Y) 0 ∧ ConsensusADMM.extendedIndicator X 0 + ConsensusADMM.extendedIndicator Y 0 = 0 ∧ ∀ γ, ConsensusADMM.criticalFactor ≤ γ → ∃ x y dual : ℕ → EuclideanSpace ℝ (Fin 96), ∃ c_r : ℝ, 0 < c_r ∧ ConsensusADMM.IsTrajectory γ (ConsensusADMM.extendedIndicator X) (ConsensusADMM.extendedIndicator Y) x y dual ∧ ConsensusADMM.HasUniqueUpdates (ConsensusADMM.extendedIndicator X) (ConsensusADMM.extendedIndicator Y) x y dual ∧ ConsensusADMM.HasExactPeriod 48 x y dual ∧ ∀ k, ‖x (k + 1) - y (k + 1)‖ = c_r)

Definition 2.1.5

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Definition 2.1.5 (1): ADMM.UniformConvergenceAt γ requires the rank-free convergence conclusions for every admissible exact trajectory and convergence to a KKT triple when both constraint matrices have full column rank. Rank-free image convergence is an additional conclusion and is not part of this predicate.

#check ADMM.UniformConvergenceAt

Corollary 2.1.6

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Corollary 2.1.6: The uniform-convergence endpoint lies strictly between 377 / 200 and the critical factor.

namespace ADMM theorem uniformConvergenceEndpoint_bounds : (377 : ℝ) / 200 < uniformConvergenceEndpoint ∧ uniformConvergenceEndpoint < ConsensusADMM.criticalFactor

Definition 3.1.1

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Definition 3.1.1. Put q = A.mulVec x, v = B.mulVec y - b, and u = β⁻¹ • λ. The functions ADMM.ImageReduction.fiberInf and ADMM.ImageReduction.shiftedFiberInf are the image objectives on the fibers A.mulVec x = q and B.mulVec y - b = v, respectively. Their β-scaled Fenchel biconjugates are ADMM.ImageReduction.reducedFirst and ADMM.ImageReduction.reducedSecond; biconjugation is needed because an image objective need not be closed.

variable {n₁ n₂ m : ℕ} #check (ADMM.ImageReduction.fiberInf : ((Fin n₁ → ℝ) → EReal) → Matrix (Fin m) (Fin n₁) ℝ → (Fin m → ℝ) → EReal)

Lemma 3.1.2

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Lemma 3.1.2 (1): the first reduced objective is closed proper convex.

#check (ADMM.Problem.reducedFirst_isClosedProperConvex : ∀ {n₁ n₂ m : ℕ} (P : ADMM.Problem n₁ n₂ m), ADMM.IsClosedProperConvex P.f → ADMM.IsClosedProperConvex P.g → (∃ x y multiplier, P.IsKKT x y multiplier) → ∀ {β γ : ℝ}, 0 < β → 0 < γ → ADMM.Trajectory P β γ → ADMM.IsClosedProperConvex (P.reduced β).f)

Notation 3.1.3

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Notation 3.1.3: the reduced KKT normalization, scaled recurrence, generated graph normals, and support bounds are exposed by the following canonical declarations.

#check ERealConvex.centerAt

Definition 3.1.4

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Definition 3.1.4: An ADMM finite-memory certificate consists of its nonnegative lag weights, positive parameters, signed-value storage, and the descent and lower finite positive-semidefiniteness tests, including all directed origin gaps.

#check (ADMM.FiniteMemory.Certificate : (ℓ : ℕ) → (γ : ℝ) → Type)

Lemma 3.1.5

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Lemma 3.1.5 (1): common finite-memory certificates at two ordered relaxation endpoints force every intervening reduced image trajectory to converge to a reduced KKT triple.

namespace ADMM.FiniteMemory theorem intervalImage_tendsto_kkt {ℓ n₁ n₂ m : ℕ} (P : Problem n₁ n₂ m) {β γMinus γPlus γ : ℝ} (cMinus : Certificate ℓ γMinus) (cPlus : Certificate ℓ γPlus) (hEndpoints : γMinus < γPlus) (hγMinus : γMinus ≤ γ) (hγPlus : γ ≤ γPlus) (hLagMinus : cMinus.lagMinus = cPlus.lagMinus) (hLagPlus : cMinus.lagPlus = cPlus.lagPlus) (hOmega : cMinus.omega = cPlus.omega) (hEpsilon : cMinus.epsilon = cPlus.epsilon) (hZeta : cMinus.zeta = cPlus.zeta) (hMu : cMinus.μ = cPlus.μ) (hf : IsClosedProperConvex P.f) (hg : IsClosedProperConvex P.g) (hKKT : ∃ x y multiplier, P.IsKKT x y multiplier) (hβ : 0 < β) (z : Trajectory P β γ) : ∃ qBar vBar uBar, (P.reduced β).IsKKT qBar vBar uBar ∧ Filter.Tendsto (fun k ↦ (P.A.mulVec (z.x k), P.B.mulVec (z.y k) - P.b, β⁻¹ • z.multiplier k)) Filter.atTop (nhds (qBar, vBar, uBar))

Notation 3.1.6

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Notation 3.1.6 (1): for memory two, the tail-sum formula specializes to h₀ = δ₁ + δ₂ and h₁ = δ₂.

namespace ADMM.FiniteMemory theorem lagCoefficient_two (lagMinus lagPlus : Block → Fin 2 → NNReal) (b : Block) : let δ (d : Fin 2) : ℝ := (lagMinus b d : ℝ) - lagPlus b d (lagCoefficient lagMinus lagPlus b 0, lagCoefficient lagMinus lagPlus b 1) = (δ 0 + δ 1, δ 1)

Proposition 3.1.7

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Proposition 3.1.7: The uniform-convergence endpoint is strictly greater than 377 / 200.

namespace ADMM theorem uniformConvergenceEndpoint_gt : (377 : ℝ) / 200 < uniformConvergenceEndpoint

Definition 4.1.1

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Definition 4.1.1 (1): for cyclic indices modulo N ≥ 2 and γ > 0, the families ρ, ξ, a, and c are respectively residual, xVertex, xNormal, and yNormal.

namespace ConsensusADMM universe u variable {N : ℕ} {E : Type u} [AddCommGroup E] [Module ℝ E] #check (CycleConfig.cycleData_spec : ∀ (q : CycleConfig N E) (i : Fin N), q.residual i = q.gamma⁻¹ • (q.nu i - q.nu (q.previous i)) ∧ q.xVertex i = q.eta i + q.residual i ∧ q.xNormal i = q.eta (q.previous i) - q.nu (q.previous i) - q.xVertex i ∧ q.yNormal i = q.nu (q.previous i) + q.residual i)

Lemma 4.1.2

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Lemma 4.1.2 (1): the prescribed cyclic sequences form a unit-penalty consensus ADMM trajectory for the indicators of the two cycle polytopes.

open Filter universe u #check (ConsensusADMM.IsProjectionCycle.isTrajectory : ∀ {N : ℕ} {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] (γ : ℝ) (η ν : ZMod N → E), 2 ≤ N → 0 < γ → ConsensusADMM.IsProjectionCycle γ η ν → ConsensusADMM.IsTrajectory γ (ConsensusADMM.extendedIndicator (ConsensusADMM.ProjectionCycle.xSet γ η ν)) (ConsensusADMM.extendedIndicator (ConsensusADMM.ProjectionCycle.ySet η)) (ConsensusADMM.ProjectionCycle.xSequence γ η ν) (ConsensusADMM.ProjectionCycle.ySequence η) (ConsensusADMM.ProjectionCycle.dualSequence ν))

Proposition 4.1.3

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Proposition 4.1.3: an N-periodic consensus ADMM trajectory with a nonzero residual admits a cyclic projection reduction in dimension at most 2 * N - 2, at the same multiplier factor.

open scoped RealInnerProductSpace namespace ConsensusADMM universe u #check (ConsensusADMM.existsCyclicReduction : ∀ {N : ℕ} {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] (γ : ℝ) (f g : E → EReal) (x y dual : ℕ → E) (hN : 2 ≤ N) (hγ : 0 < γ) (hf : ADMM.IsClosedProperConvex f) (hg : ADMM.IsClosedProperConvex g) (htrajectory : ConsensusADMM.IsTrajectory γ f g x y dual) (hperiodic : Function.Periodic (fun k ↦ (x (k + 1), y (k + 1), dual (k + 1))) N) (hnonzero : ∃ k, x (k + 1) - y (k + 1) ≠ 0), ∃ d : ℕ, d ≤ 2 * N - 2 ∧ ∃ η ν : ZMod N → EuclideanSpace ℝ (Fin d), ConsensusADMM.IsCyclicReduction γ η ν)

Proposition 4.1.4

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Proposition 4.1.4 (1): the canonical positive-semidefinite square-root map converts the standard Euclidean pairing into a matrix-linear Gram pairing.

#check (ConsensusADMM.GramCycle.gramMap_inner : ∀ {N : ℕ} (G : Matrix (Fin 2 × Fin N) (Fin 2 × Fin N) ℝ) (hG : G.PosSemidef) (z w : (Fin 2 × Fin N) → ℝ), dotProduct (ConsensusADMM.GramCycle.gramMap G z) (ConsensusADMM.GramCycle.gramMap G w) = ConsensusADMM.GramCycle.supportFunctional z w G)

Definition 4.1.5

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Definition 4.1.5: the exact period-48 constants, alternating vector, rank-one perturbation of the integer matrix, and its parity-dependent support contributions.

#check (ConsensusADMM.Period48.gramMatrix : Matrix (Fin 2 × Fin 48) (Fin 2 × Fin 48) ℝ)

Proposition 4.1.6

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Proposition 4.1.6 (1): the explicit period-48 Gram matrix H = 2K - I₉₆ + 3hhᵀ is positive definite.

open scoped RealInnerProductSpace #check (ConsensusADMM.Period48.FixedPolytopes.gramMatrix_posDef : (ConsensusADMM.Period48.gramMatrix).PosDef)

Lemma 5.1.1

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Lemma 5.1.1 (1): strictification of a projection cycle with one strict block.

universe u #check (ConsensusADMM.IsProjectionCycle.strictifyOneBlock : ∀ {N : ℕ} {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] (γ : ℝ) (η ν : ZMod N → E) (hN : 2 ≤ N) (hγ : 0 < γ) (hγtwo : γ < 2) (hcycle : ConsensusADMM.IsProjectionCycle γ η ν) (hnonzero : ∃ i, ConsensusADMM.ProjectionCycle.residual γ ν i ≠ 0) (hstrict : ConsensusADMM.HasStrictBlock γ η ν), ∃ d : ℕ, d ≤ 2 * N ∧ ∃ eta' nu' : ZMod N → EuclideanSpace ℝ (Fin d), ConsensusADMM.IsStrictProjectionCycle γ eta' nu' ∧ (∃ i, ConsensusADMM.ProjectionCycle.residual γ nu' i ≠ 0) ∧ (ConsensusADMM.ProjectionCycle.HasOrthogonalCyclicSymmetry η ν → ConsensusADMM.ProjectionCycle.HasOrthogonalCyclicSymmetry eta' nu'))

Lemma 5.1.2

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Lemma 5.1.2 (1): a nontrivial projection cycle with one strict block can be strictified in dimension at most 2 * N, while preserving orthogonal cyclic symmetry.

universe u #check (ConsensusADMM.IsProjectionCycle.strictifyOneBlock : ∀ {N : ℕ} {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] (γ : ℝ) (η ν : ZMod N → E), 2 ≤ N → 0 < γ → γ < 2 → ConsensusADMM.IsProjectionCycle γ η ν → (∃ i, ConsensusADMM.ProjectionCycle.residual γ ν i ≠ 0) → ConsensusADMM.HasStrictBlock γ η ν → ∃ d : ℕ, d ≤ 2 * N ∧ ∃ eta' nu' : ZMod N → EuclideanSpace ℝ (Fin d), ConsensusADMM.IsStrictProjectionCycle γ eta' nu' ∧ (∃ i, ConsensusADMM.ProjectionCycle.residual γ nu' i ≠ 0) ∧ (ConsensusADMM.ProjectionCycle.HasOrthogonalCyclicSymmetry η ν → ConsensusADMM.ProjectionCycle.HasOrthogonalCyclicSymmetry eta' nu'))

Lemma 5.1.3

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Lemma 5.1.3 (1): strictification of a projection cycle with one strict block.

#check ConsensusADMM.IsProjectionCycle.strictifyOneBlock

Lemma 5.1.4

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Lemma 5.1.4: strict finite projection-cycle data with a nonzero residual admit smooth strongly convex objectives whose unit-penalty consensus ADMM trajectory is the prescribed cycle with its exact minimal period, positive constant trajectory value, globally unique block minimizers, unique KKT triple (0, 0, 0), and optimal value zero.

open scoped RealInnerProductSpace namespace ConsensusADMM.IsStrictProjectionCycle open ConsensusADMM ProjectionCycle theorem smoothStronglyConvexRealization {N d : ℕ} (γ : ℝ) (η ν : ZMod N → EuclideanSpace ℝ (Fin d)) (hN : 2 ≤ N) (hγ : 0 < γ) (hcycle : ConsensusADMM.IsStrictProjectionCycle γ η ν) (hnonzero : ∃ i, residual γ ν i ≠ 0) : ∃ f g : EuclideanSpace ℝ (Fin d) → ℝ, IsSmoothStronglyConvex f ∧ IsSmoothStronglyConvex g ∧ IsTrajectory γ (ofReal f) (ofReal g) (xSequence γ η ν) (ySequence η) (dualSequence ν) ∧ HasUniqueBlockMinimizers (ofReal f) (ofReal g) ∧ (∃ p : ℕ, 0 < p ∧ p ∣ N ∧ HasExactPeriod p (xSequence γ η ν) (ySequence η) (dualSequence ν)) ∧ (∃ c : ℝ, 0 < c ∧ ∀ k, f (xSequence γ η ν (k + 1)) + g (ySequence η (k + 1)) = c) ∧ IsUniqueKKT (ofReal f) (ofReal g) 0 0 0 ∧ IsPrimalMinimizer (ofReal f) (ofReal g) 0 ∧ f 0 + g 0 = 0

Lemma 5.1.5

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Lemma 5.1.5: strict finite projection-cycle data with a nonzero residual admit smooth strongly convex real objectives whose unit-penalty consensus ADMM trajectory reproduces the prescribed cycle and its exact minimal period, has positive constant objective value and globally unique block minimizers, and has (0, 0, 0) as its unique KKT triple with optimal value zero.

#check ConsensusADMM.IsStrictProjectionCycle.smoothStronglyConvexRealization

Definition 8.1.1

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Definition 8.1.1 (1): exact rational cases store the common coefficients, lag tables, packed interpolation weights, endpoint parameters, and packed endpoint blocks.

#check ADMM.FiniteMemory.Reconstruction.RationalCase

Notation 9.1.1

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Notation 9.1.1: the unscaled integer matrix K uses the period-48 convention Circ(t) i j = t (j - i), the displayed rows p, q, and c, and blocks Circ(p), Circ(c), Circ(c)ᵀ, and Circ(q), with no scaling.

#check (ConsensusADMM.Period48.integerMatrix : Matrix (Fin 2 × Fin 48) (Fin 2 × Fin 48) ℤ)

Algorithm 9.1.2

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Algorithm 9.1.2: for J₀ = 2K - I₉₆ with K the period-48 two-block integer matrix, fraction-free elimination starts from B⁽⁰⁾ = J₀ and b₋₁ = 1, and for k = 0,…,94 updates the trailing entries by B⁽ᵏ⁺¹⁾ᵢⱼ = (b_k · B⁽ᵏ⁾ᵢⱼ - B⁽ᵏ⁾ᵢₖ · B⁽ᵏ⁾ₖⱼ) / b_{k-1} with b_k = B⁽ᵏ⁾ₖₖ, where each division is exact in ℤ. The 96 leading principal determinants are b_0,…,b_94, B⁽⁹⁵⁾₉₅,₉₅, each at least 1, so Sylvester's criterion gives J₀ ≻ 0.

#check (ConsensusADMM.Period48.j0 : Matrix (Fin 96) (Fin 96) ℤ)

Algorithm 9.1.3

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Algorithm 9.1.3: for the support tests, form H = 2K - I₉₆ + 3hhᵀ by eq:H, work with the coefficient vectors ηᵢ = eᵢ and wᵢ = e₄₈₊ᵢ / γ₀, and interpret every inner product as zᵀHw. Set ρᵢ = wᵢ - wᵢ₋₁, ξᵢ = ηᵢ + ρᵢ, and use the affine normals aᵢ(γ) = ηᵢ₋₁ - γ wᵢ₋₁ - ξᵢ and cᵢ(γ) = γ wᵢ₋₁ + ρᵢ of Proposition prop:fixed. At phase zero the support is evaluated against the origin and against every other phase, for both blocks. These 96 rational affine expressions give all 4608 supports by cyclic shifts; their slopes and endpoint values satisfy Table 2 and the single exceptional expression is eq:active, so the displayed inputs determine every check needed for Proposition prop:fixed.

#check (ConsensusADMM.Period48.Coefficient.support : Fin 2 → ℝ → ZMod 48 → ZMod 48 → ℝ)

Finite Objectives And Growth

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

The orientation of the second consensus block is the first-block orientation with the multiplier negated.

open scoped RealInnerProductSpace namespace ConsensusADMM theorem FiniteObjectivesAndGrowth.ObjectiveData.hasUniqueBlockMinimizers {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] {f g : E → ℝ} (hf : FiniteObjectivesAndGrowth.ObjectiveData f) (hg : FiniteObjectivesAndGrowth.ObjectiveData g) : HasUniqueBlockMinimizers (ofReal f) (ofReal g)

Convergence

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

The objective-value sequence along an exact ADMM trajectory.

namespace ADMM namespace Trajectory noncomputable def objectiveValue {n₁ n₂ m : ℕ} {P : Problem n₁ n₂ m} {β γ : ℝ} (t : Trajectory P β γ) (k : ℕ) : EReal := P.objective (t.x k) (t.y k)

ProjectionCycleStrictification

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

A nontrivial projection cycle with one strict block can be strictified in dimension at most 2 * N, while preserving orthogonal cyclic symmetry.

namespace ConsensusADMM.IsProjectionCycle open ConsensusADMM ProjectionCycle universe u variable {N : ℕ} {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] theorem strictifyOneBlock (γ : ℝ) (η ν : ZMod N → E) (hN : 2 ≤ N) (hγ : 0 < γ) (hγtwo : γ < 2) (hcycle : ConsensusADMM.IsProjectionCycle γ η ν) (hnonzero : ∃ i, residual γ ν i ≠ 0) (hstrict : HasStrictBlock γ η ν) : ∃ d : ℕ, d ≤ 2 * N ∧ ∃ eta' nu' : ZMod N → EuclideanSpace ℝ (Fin d), IsStrictProjectionCycle γ eta' nu' ∧ (∃ i, residual γ nu' i ≠ 0) ∧ (HasOrthogonalCyclicSymmetry η ν → HasOrthogonalCyclicSymmetry eta' nu')

EndpointLower

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Assemble the original interval convergence theorem into the uniform interface.

namespace ADMM.EndpointLower open FiniteMemory.Reconstruction.EndpointLower theorem uniformConvergenceAt_original {t : ℝ} (ht : 0 < t) (hUpper : t ≤ (377 : ℝ) / 200) : UniformConvergenceAt t

CertificateUniform

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

A finite-memory certificate implies the full uniform convergence property at its parameter, including the original objective and multiplier conclusions.

open Filter ADMM.FiniteMemory namespace ADMM.ConvergenceProof theorem uniformConvergenceAt_of_certificate {ℓ : ℕ} {γ : ℝ} (c : Certificate ℓ γ) : UniformConvergenceAt γ

SmoothRealization

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

A smooth realization certificate for a finite strictly supported family.

open Set Filter open scoped Topology RealInnerProductSpace namespace ConsensusADMM.SmoothRealization variable {N : ℕ} [NeZero N] {E : Type*} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] structure Interpolates (p n : ZMod N → E) (f : E → ℝ) where modulus : ℝ level : ℝ constant : NNReal modulus_pos : 0 < modulus level_pos : 0 < level stronglyConvex : StrongConvexOn univ modulus f contDiff : ContDiff ℝ 1 f lipschitz : LipschitzWith constant (fderiv ℝ f) zero : f 0 = 0 derivative_zero : HasFDerivAt f (0 : E →L[ℝ] ℝ) 0 lower : ∀ x, modulus / 2 * ‖x‖ ^ 2 ≤ f x values : ∀ i, f (p i) = level supports : ∀ i x, f (p i) + ⟪n i, x - p i⟫ ≤ f x

GeometricGrowth

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

The phase residual for a trajectory expanding by the factor κ per step.

open Filter namespace ConsensusADMM.GeometricGrowth universe u variable {N : ℕ} {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] noncomputable def residual (γ κ : ℝ) (ν : ZMod N → E) (i : ZMod N) : E := γ⁻¹ • (ν i - κ⁻¹ • ν (i - 1))

FiniteObjectivesAndGrowth

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

Every augmented block problem has a unique finite minimizer, for all centers and multipliers, rather than only along one prescribed trajectory.

open Set open scoped RealInnerProductSpace namespace ConsensusADMM.FiniteObjectivesAndGrowth variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable [FiniteDimensional ℝ E] def UniqueAugmentedMinimizers (f : E → ℝ) : Prop := ∀ center dual, ∃! p, ofReal f p ≠ ⊤ ∧ ofReal f p ≠ ⊥ ∧ ∀ z, ofReal f p + ((inner ℝ dual (p - center) + ‖p - center‖ ^ 2 / 2 : ℝ) : EReal) ≤ ofReal f z + ((inner ℝ dual (z - center) + ‖z - center‖ ^ 2 / 2 : ℝ) : EReal)

Counterexamples

Lean contributors (project-level attribution): Qiming Dai.

Source header · Attribution source

One fixed pair of compact convex polytopes in ℝ⁹⁶ supports, for every multiplier factor at least criticalFactor, a unique-update consensus ADMM trajectory of exact period 48 and constant positive residual.

namespace ConsensusADMM open scoped MatrixOrder theorem fixedPolytopes : ∃ X Y : Set (EuclideanSpace ℝ (Fin 96)), IsCompactConvexPolytope X ∧ IsCompactConvexPolytope Y ∧ IsKKT (extendedIndicator X) (extendedIndicator Y) 0 0 0 ∧ IsPrimalMinimizer (extendedIndicator X) (extendedIndicator Y) 0 ∧ extendedIndicator X 0 + extendedIndicator Y 0 = 0 ∧ ∀ γ, criticalFactor ≤ γ → ∃ x y dual : ℕ → EuclideanSpace ℝ (Fin 96), ∃ c_r : ℝ, 0 < c_r ∧ IsTrajectory γ (extendedIndicator X) (extendedIndicator Y) x y dual ∧ HasUniqueUpdates (extendedIndicator X) (extendedIndicator Y) x y dual ∧ HasExactPeriod 48 x y dual ∧ ∀ k, ‖x (k + 1) - y (k + 1)‖ = c_r

Formalization contributors

Qiming Dai

Project-level credit · Source roster