§3.3 —
ProvedBoydADMM.Convergence.x_update_dual_residualadmmoptimality-conditionsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1subdifferential
Let satisfy Assumption 1, let , and let be any ADMM run (3.2)–(3.4). Then for every ,
Thus the dual residual measures the violation of the dual feasibility condition (3.9), , at iteration . Here is the subdifferential of at .
Formalization Note Written as with ShorNonsmooth.Subdiff.subdifferential relative to .
Preamble
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model import Definitions.Def_ShorNonsmooth_Subdiff_Subdifferential
Formal statement
namespace BoydADMM.Convergence
/-- §3.3, p. 18: `ρAᵀB(z^{k+1} − z^k) ∈ ∂f(x^{k+1}) + Aᵀy^{k+1}`, i.e.
`s^{k+1} − Aᵀy^{k+1} ∈ ∂f(x^{k+1})`, for every `k ≥ 0`. -/
theorem x_update_dual_residual
{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 : ℕ) :
P.dualResid ρ (z k) (z (k + 1)) - P.ATmul (y (k + 1)) ∈
ShorNonsmooth.Subdiff.subdifferential P.Cf P.f (x (k + 1)) := by sorry
end BoydADMM.Convergence
Source
Boyd et al., Found. Trends Mach. Learn. 3(1) (2011), §3.3, p. 18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.