(3.11) —
ProvedBoydADMM.Convergence.ineq_3_11admmconvergence-proofp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1stopping-criterion
Under Assumptions 1 and 2, with , a saddle point of and any ADMM run, for every iteration
where is the primal residual and the dual residual.
The bound shows that small residuals force small objective suboptimality; it underlies the stopping criterion of §3.3.1.
Formalization Note Stated at index for (as on p. 107), since and are not defined by the method. is the infimum optVal. The book derives (3.11) from (A.2) via the identity printed as ""; the intended identity, forced by (A.2) and , is . The statement of (3.11) itself is unaffected.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model
Formal statement
namespace BoydADMM.Convergence
/-- (3.11), p. 19 (stated at index `k + 1` on p. 107): for every `k ≥ 0`,
`f(x^{k+1}) + g(z^{k+1}) − p⋆ ≤ −(y^{k+1})ᵀr^{k+1} + (x^{k+1} − x⋆)ᵀs^{k+1}`,
with `s^{k+1} = ρAᵀB(z^{k+1} − z^k)`. -/
theorem ineq_3_11
{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 ℝ (x (k + 1) - xs) (P.dualResid ρ (z k) (z (k + 1))) := by sorry
end BoydADMM.Convergence
Source
Boyd et al., Found. Trends Mach. Learn. 3(1) (2011), §3.3.1, p. 19, (3.11); derived on p. 107
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.