(A.1) — for
ProvedBoydADMM.Convergence.ineq_A1admmconvergence-prooflyapunovp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Under Assumptions 1 and 2, with , a saddle point of and any ADMM run, let and . Then for every ,
This is the first key inequality of Appendix A: decreases by an amount controlled by the primal residual and the change in .
Formalization Note The book states (A.1) without an index range, but its proof uses the monotonicity step, which needs to be a -update, so it is proved for ; for and an arbitrary the inequality can fail. We state , written with , in place of , .
Preamble
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model
Formal statement
namespace BoydADMM.Convergence
/-- (A.1), p. 107: `V^{k+1} ≤ V^k − ρ‖r^{k+1}‖₂² − ρ‖B(z^{k+1} − z^k)‖₂²` for every book
index `k ≥ 1` (here written with `k + 1` in place of the book's `k`). -/
theorem ineq_A1
{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 + 2)) (y (k + 2)) ≤
P.lyapunov ρ zs ys (z (k + 1)) (y (k + 1))
- ρ * ‖P.resid (x (k + 2)) (z (k + 2))‖ ^ 2
- ρ * ‖P.Bmul (z (k + 2) - z (k + 1))‖ ^ 2 := by sorry
end BoydADMM.Convergence
Source
Boyd et al., Found. Trends Mach. Learn. 3(1) (2011), Appendix A, p. 107, (A.1); proof pp. 109–110
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.