(14), proof of Theorem 8, p. 221 — (1/c_k)(∇h_x(x^k) − ∇h_x(x^{k+1})) ∈ ∂ₓl(x^{k+1}, p^{k+1})
ProvedBregmanPPA.ProxMult.eq14lagrangianp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-method-of-multiplierssubdifferential
Assume the hypotheses of Theorem 8: a problem of the form (10); ; a Bregman function on with zone ; a Bregman function on with zone and ; and conforming to the recursions (12). Then for every , and
This is the -component of the identity (13) that makes (12) a Bregman proximal point run on .
Formalization Note The conjunct is part of the statement because is identically on for , where every vector satisfies the subgradient inequality; with it, (14) is the inclusion for the proper convex function , as in the paper (which uses on p. 222). The bounded-away-from-zero hypothesis on is not needed and is omitted.
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
/-- (14), proof of Theorem 8, p. 221: along a run of (12), `p^{k+1} ≥ 0` and
`(1/c_k)(∇h_x(x^k) − ∇h_x(x^{k+1})) ∈ ∂ₓ l(x^{k+1}, p^{k+1})`. -/
theorem eq14 {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) :
∀ k, p (k + 1) ∈ BregmanPPA.IneqMult.nonnegOrthant m ∧
(c k)⁻¹ • (gradient hx (x k) - gradient hx (x (k + 1)))
∈ subdiffX C f g (x (k + 1)) (p (k + 1)) := 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), p. 221, proof of Theorem 8, display (14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.