The Multiplier Step Size of Two-Block ADMM
Source excerpts; proofs omitted.
Algorithm 1.1.1
Lean contributors (project-level attribution): Qiming Dai.
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.
Definition 2.1.1 (1): the KKT set and its three defining conditions.
#check ADMM.Problem.kktSetTheorem 2.1.2
Lean contributors (project-level attribution): Qiming Dai.
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.
Theorem 2.1.3 (1): fixed compact convex polytopes give exact-period counterexamples for every multiplier factor at least criticalFactor.
namespace ConsensusADMM
#check ConsensusADMM.fixedPolytopesTheorem 2.1.4
Lean contributors (project-level attribution): Qiming Dai.
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.
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.UniformConvergenceAtCorollary 2.1.6
Lean contributors (project-level attribution): Qiming Dai.
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.criticalFactorDefinition 3.1.1
Lean contributors (project-level attribution): Qiming Dai.
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.
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.
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.centerAtDefinition 3.1.4
Lean contributors (project-level attribution): Qiming Dai.
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.
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.
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.
Proposition 3.1.7: The uniform-convergence endpoint is strictly greater than 377 / 200.
namespace ADMM
theorem uniformConvergenceEndpoint_gt :
(377 : ℝ) / 200 < uniformConvergenceEndpointDefinition 4.1.1
Lean contributors (project-level attribution): Qiming Dai.
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.
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.
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.
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.
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.
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.
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.
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.
Lemma 5.1.3 (1): strictification of a projection cycle with one strict block.
#check ConsensusADMM.IsProjectionCycle.strictifyOneBlockLemma 5.1.4
Lean contributors (project-level attribution): Qiming Dai.
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 = 0Lemma 5.1.5
Lean contributors (project-level attribution): Qiming Dai.
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.smoothStronglyConvexRealizationDefinition 8.1.1
Lean contributors (project-level attribution): Qiming Dai.
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.RationalCaseNotation 9.1.1
Lean contributors (project-level attribution): Qiming Dai.
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.
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.
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.
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.
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.
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.
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 tCertificateUniform
Lean contributors (project-level attribution): Qiming Dai.
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.
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 xGeometricGrowth
Lean contributors (project-level attribution): Qiming Dai.
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.
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.
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_rFormalization contributors
Qiming Dai
Project-level credit · Source roster