Documentation

glowinski_admm_counterexample.GlowinskiADMM.lemma_3_1_5

theorem ADMM.FiniteMemory.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 : Fin n₁ → ℝ) (y : Fin n₂ → ℝ) (multiplier : Fin m → ℝ), P.IsKKT x y multiplier) (hβ : 0 < β) (z : Trajectory P β γ) :
∃ (qBar : Fin m → ℝ) (vBar : Fin m → ℝ) (uBar : Fin m → ℝ), (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))

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.

theorem ADMM.FiniteMemory.intervalResidual_sq_summable {ℓ 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 : Fin n₁ → ℝ) (y : Fin n₂ → ℝ) (multiplier : Fin m → ℝ), P.IsKKT x y multiplier) (hβ : 0 < β) (z : Trajectory P β γ) :
Summable fun (k : ℕ) => ‖z.primalResidual k‖ ^ 2

Lemma 3.1.5 (2): under common endpoint certificates, the squared primal residual norms of every intervening exact trajectory are summable.

theorem ADMM.FiniteMemory.intervalSecondIncrement_sq_summable {ℓ 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 : Fin n₁ → ℝ) (y : Fin n₂ → ℝ) (multiplier : Fin m → ℝ), P.IsKKT x y multiplier) (hβ : 0 < β) (z : Trajectory P β γ) :
Summable fun (k : ℕ) => ‖z.secondIncrement k‖ ^ 2

Lemma 3.1.5 (3): under common endpoint certificates, the squared second-image increment norms of every intervening exact trajectory are summable.

theorem ADMM.FiniteMemory.intervalFirstTilt_tendsto_zero {ℓ 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 : Fin n₁ → ℝ) (y : Fin n₂ → ℝ) (multiplier : Fin m → ℝ), P.IsKKT x y multiplier) (hβ : 0 < β) (z : Trajectory P β γ) (qBar vBar uBar : Fin m → ℝ) (hReducedKKT : (P.reduced β).IsKKT qBar vBar uBar) (hState : 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))) :
Filter.Tendsto (fun (k : ℕ) => (P.reduced β).f (P.A.mulVec (z.x k)) - (P.reduced β).f qBar + ↑(uBar ⬝ᵥ (P.A.mulVec (z.x k) - qBar))) Filter.atTop (nhds 0)

Lemma 3.1.5 (4): along the reduced-state limit supplied by the interval certificate, the first reduced objective tilted at its KKT support tends to zero.

theorem ADMM.FiniteMemory.intervalSecondTilt_tendsto_zero {ℓ 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 : Fin n₁ → ℝ) (y : Fin n₂ → ℝ) (multiplier : Fin m → ℝ), P.IsKKT x y multiplier) (hβ : 0 < β) (z : Trajectory P β γ) (qBar vBar uBar : Fin m → ℝ) (hReducedKKT : (P.reduced β).IsKKT qBar vBar uBar) (hState : 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))) :
Filter.Tendsto (fun (k : ℕ) => (P.reduced β).g (P.B.mulVec (z.y k) - P.b) - (P.reduced β).g vBar + ↑(uBar ⬝ᵥ (P.B.mulVec (z.y k) - P.b - vBar))) Filter.atTop (nhds 0)

Lemma 3.1.5 (5): along the reduced-state limit supplied by the interval certificate, the second reduced objective tilted at its KKT support tends to zero.