(A.2) —
ProvedBoydADMM.Convergence.ineq_A2admmconvergence-proofp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Under Assumptions 1 and 2, with , a saddle point of and any ADMM run , for every
where , and is the optimal value of (3.1).
This is the second key inequality of Appendix A; it bounds the objective from above by quantities that vanish along the iteration.
Formalization Note is the infimum optVal.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model
Formal statement
namespace BoydADMM.Convergence
/-- (A.2), p. 107: for every `k ≥ 0`,
`p^{k+1} − p⋆ ≤ −(y^{k+1})ᵀr^{k+1} − ρ(B(z^{k+1} − z^k))ᵀ(−r^{k+1} + B(z^{k+1} − z⋆))`. -/
theorem ineq_A2
{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.f (x (k + 1)) + P.g (z (k + 1)) - P.optVal ≤
-inner ℝ (y (k + 1)) (P.resid (x (k + 1)) (z (k + 1)))
- ρ * inner ℝ (P.Bmul (z (k + 1) - z k))
(-P.resid (x (k + 1)) (z (k + 1)) + P.Bmul (z (k + 1) - zs)) := by sorry
end BoydADMM.Convergence
Source
Boyd et al., Found. Trends Mach. Learn. 3(1) (2011), Appendix A, p. 107, (A.2); proof p. 108
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.