(13), proof of Theorem 8, pp. 221–222 — (x^{k+1}, p^{k+1}) = (∇h + c_k K)⁻¹(∇h(x^k, p^k))
ProvedBregmanPPA.ProxMult.eq13bregman-functionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-method-of-multipliersproximal-point
Under the hypotheses of Theorem 8 (with ), let conform to the recursions (12) and let . Then the pair sequence lies in and is a run of the Bregman proximal point algorithm for on :
With (13), the convergence claims of Theorem 8 follow from Theorem 1 under condition (C1).
Formalization Note (13) is stated in the equivalent form (4): and , where on WithLp 2 (E n × E m).
Preamble
import Mathlib import Definitions.Def_BregmanPPA_Convergence_Model import Definitions.Def_BregmanPPA_IneqMult_Program import Definitions.Def_BregmanPPA_ProxMult_Saddle
Formal statement
namespace BregmanPPA.ProxMult
/-- (13), proof of Theorem 8, pp. 221–222: a run of (12) is a run of the Bregman proximal point
algorithm (3), in its form (4), for `h = h_x ⊕ h_p` and `T = K` on `ℝⁿ⁺ᵐ`:
`(x^{k+1}, p^{k+1}) = (∇h + c_k K)⁻¹(∇h(x^k, p^k))`. -/
theorem eq13 {n m : ℕ} (C : Set (BregmanPPA.IneqMult.E n)) (f : BregmanPPA.IneqMult.E n → EReal) (g : Fin m → BregmanPPA.IneqMult.E n → EReal)
(Sx : Set (BregmanPPA.IneqMult.E n)) (hx : BregmanPPA.IneqMult.E n → ℝ) (Sp : Set (BregmanPPA.IneqMult.E m)) (hp : BregmanPPA.IneqMult.E m → ℝ)
(c : ℕ → ℝ) (x : ℕ → BregmanPPA.IneqMult.E n) (p : ℕ → BregmanPPA.IneqMult.E m)
(hP : BregmanPPA.IneqMult.IsConvexProgram C f g) (hc : ∀ k, 0 < c k)
(hhx : BregmanPPA.Convergence.IsBregmanFunction Sx hx) (hSx : C ⊆ Sx)
(hhp : BregmanPPA.Convergence.IsBregmanFunction Sp hp) (hSp : BregmanPPA.IneqMult.nonnegOrthant m ⊆ Sp)
(him : gradient hp '' Sp = Set.univ)
(hrun : IsProxMultRun C f g Sx hx Sp hp c x p) :
BregmanPPA.Convergence.IsBregmanPPARun (prodZone Sx Sp) (sumFn hx hp) (opK C f g) c
(fun k => pair (x k) (p k)) := by sorry
end BregmanPPA.ProxMult
Source
Eckstein, Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming, Math. Oper. Res. 18(1) (1993), pp. 221–222, proof of Theorem 8, display (13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.