Proof of (A.1) — for
ProvedBoydADMM.Convergence.dual_step_monotoneadmmconvergence-proofp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let satisfy Assumption 1, let and let be any ADMM run. Then for every ,
This is the monotonicity step in the proof of (A.1): minimizes and minimizes , and the two optimality conditions combine.
Formalization Note The book does not state the index range; its argument needs to be itself a -update, i.e. , because is an arbitrary starting point. The Lean statement is written with and in place of the book's and , .
Preamble
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model
Formal statement
namespace BoydADMM.Convergence
/-- Proof of (A.1), p. 110: `(y^{k+1} − y^k)ᵀ(B(z^{k+1} − z^k)) ≤ 0` for every book index
`k ≥ 1` (here written with `k + 1` in place of the book's `k`, so that `z^k` is itself a
`z`-update). -/
theorem dual_step_monotone
{n m p : ℕ} (P : Problem n m p) (hA1 : P.Assumption1) {ρ : ℝ} (hρ : 0 < ρ)
{x : ℕ → EuclideanSpace ℝ (Fin n)} {z : ℕ → EuclideanSpace ℝ (Fin m)}
{y : ℕ → EuclideanSpace ℝ (Fin p)} (hrun : P.IsADMMSeq ρ x z y) (k : ℕ) :
inner ℝ (y (k + 2) - y (k + 1)) (P.Bmul (z (k + 2) - z (k + 1))) ≤ 0 := by sorry
end BoydADMM.Convergence
Source
Boyd et al., Found. Trends Mach. Learn. 3(1) (2011), Appendix A, proof of (A.1), p. 110
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.