(A.3) —
ProvedBoydADMM.Convergence.ineq_A3admmconvergence-proofp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let satisfy Assumption 1, let , let be a saddle point of the Lagrangian (Assumption 2), and let be any ADMM run. Write and , and let be the optimal value of (3.1). Then for every ,
This is the third key inequality of the convergence proof: since , it bounds the objective from below in the limit.
Formalization Note is the infimum optVal over feasible points of the domains, not by definition.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model
Formal statement
namespace BoydADMM.Convergence
/-- (A.3), p. 107: `p⋆ − p^{k+1} ≤ y⋆ᵀr^{k+1}` for every `k ≥ 0`, where
`p^{k+1} = f(x^{k+1}) + g(z^{k+1})` and `r^{k+1} = Ax^{k+1} + Bz^{k+1} − c`. -/
theorem ineq_A3
{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.optVal - (P.f (x (k + 1)) + P.g (z (k + 1))) ≤
inner ℝ ys (P.resid (x (k + 1)) (z (k + 1))) := by sorry
end BoydADMM.Convergence
Source
Boyd et al., Found. Trends Mach. Learn. 3(1) (2011), Appendix A, p. 107, (A.3); proof p. 108
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.