§3.3 — and always satisfy (3.10):
ProvedBoydADMM.Convergence.z_update_dual_feasibleadmmoptimality-conditionsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1subdifferential
Let satisfy Assumption 1 (closed, proper, convex), let , and let be any ADMM run (3.2)–(3.4) for problem (3.1). Then for every ,
that is, the pair satisfies the dual feasibility condition (3.10) at every iteration. Here is the subdifferential of at : the set of with for all .
Consequently optimality of ADMM iterates reduces to the two remaining conditions, primal feasibility (3.8) and dual feasibility (3.9).
Formalization Note The statement is written as with the published subdifferential ShorNonsmooth.Subdiff.subdifferential relative to , which is the convex-analysis subdifferential of the extended-valued at a point of its domain.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model import Definitions.Def_ShorNonsmooth_Subdiff_Subdifferential
Formal statement
namespace BoydADMM.Convergence
/-- §3.3, p. 18: `z^{k+1}` and `y^{k+1}` always satisfy (3.10),
`0 ∈ ∂g(z^{k+1}) + Bᵀy^{k+1}`, i.e. `−Bᵀy^{k+1} ∈ ∂g(z^{k+1})`, for every `k ≥ 0`. -/
theorem z_update_dual_feasible
{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.BTmul (y (k + 1)) ∈ ShorNonsmooth.Subdiff.subdifferential P.Cg P.g (z (k + 1)) := by sorry
end BoydADMM.Convergence
Source
Boyd et al., Found. Trends Mach. Learn. 3(1) (2011), §3.3, p. 18, (3.10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.