§3.3.1 — if then
ProvedBoydADMM.Convergence.suboptimality_boundadmmp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1stopping-criterion
Under Assumptions 1 and 2, with , a saddle point of and any ADMM run, let and with . Then
where and .
The middle and right-hand expressions are computable from the iterates once a guess is fixed, and serve as approximate bounds on the suboptimality in a stopping criterion.
Formalization Note Stated at index , . is the infimum optVal.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model
Formal statement
namespace BoydADMM.Convergence
/-- §3.3.1, p. 19: if `‖x^k − x⋆‖₂ ≤ d` then
`f(x^k) + g(z^k) − p⋆ ≤ −(y^k)ᵀr^k + d‖s^k‖₂ ≤ ‖y^k‖₂‖r^k‖₂ + d‖s^k‖₂`, for every `k ≥ 1`
(written as `k + 1`, `k ≥ 0`). -/
theorem suboptimality_bound
{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 : ℕ) (d : ℝ) (hd : ‖x (k + 1) - xs‖ ≤ d) :
P.f (x (k + 1)) + P.g (z (k + 1)) - P.optVal ≤
-inner ℝ (y (k + 1)) (P.resid (x (k + 1)) (z (k + 1)))
+ d * ‖P.dualResid ρ (z k) (z (k + 1))‖ ∧
-inner ℝ (y (k + 1)) (P.resid (x (k + 1)) (z (k + 1)))
+ d * ‖P.dualResid ρ (z k) (z (k + 1))‖ ≤
‖y (k + 1)‖ * ‖P.resid (x (k + 1)) (z (k + 1))‖
+ d * ‖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
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.