(A.6) —
ProvedBoydADMM.Convergence.ineq_A6admmconvergence-prooflyapunovp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Under Assumptions 1 and 2, with , a saddle point of and any ADMM run, let
Then for every ,
where . In particular : the Lyapunov function does not increase.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model
Formal statement
namespace BoydADMM.Convergence
/-- (A.6), p. 110: `V^k − V^{k+1} ≥ ρ‖r^{k+1} − B(z^{k+1} − z^k)‖₂²` for every `k ≥ 0`,
with `V^k = (1/ρ)‖y^k − y⋆‖₂² + ρ‖B(z^k − z⋆)‖₂²`. -/
theorem ineq_A6
{n m p : ℕ} (P : Problem n m p) (hA1 : P.Assumption1) {ρ : ℝ} (hρ : 0 < ρ)
{xs : EuclideanSpace ℝ (Fin n)} {zs : EuclideanSpace ℝ (Fin m)}
{ys : EuclideanSpace ℝ (Fin p)} (hsp : P.IsSaddlePoint xs zs ys)
{x : ℕ → EuclideanSpace ℝ (Fin n)} {z : ℕ → EuclideanSpace ℝ (Fin m)}
{y : ℕ → EuclideanSpace ℝ (Fin p)} (hrun : P.IsADMMSeq ρ x z y) (k : ℕ) :
P.lyapunov ρ zs ys (z k) (y k) - P.lyapunov ρ zs ys (z (k + 1)) (y (k + 1)) ≥
ρ * ‖P.resid (x (k + 1)) (z (k + 1)) - P.Bmul (z (k + 1) - z k)‖ ^ 2 := by sorry
end BoydADMM.Convergence
Source
Boyd et al., Found. Trends Mach. Learn. 3(1) (2011), Appendix A, p. 110, (A.6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.