Proof of Theorem 8, p. 221 — the supergradients of l in p: ∂̂ₚl(x, p) = {g(x)} − ∂δ⁺(p)
ProvedBregmanPPA.ProxMult.supdiff_formulalagrangianp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1saddle-pointsupergradient
For a problem of the form (10), every and every , the set of supergradients of the concave function at is
Coordinatewise, this says when and when . It is the step of the proof of Theorem 8 that identifies the -update of (12) with the -component of the proximal step on .
Formalization Note The page prints , using for the subdifferential of the indicator (the normal cone of at ), as on p. 222. The statement uses , built from IsSubgradient and the indicator indicatorPos.
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
/-- Proof of Theorem 8, p. 221: for `x ∈ C` and `p ≥ 0`, the supergradients of `l(x, ·)` at `p`
are `∂̂ₚ l(x, p) = {g(x)} − ∂δ⁺(p)`. -/
theorem supdiff_formula {n m : ℕ} (C : Set (BregmanPPA.IneqMult.E n)) (f : BregmanPPA.IneqMult.E n → EReal) (g : Fin m → BregmanPPA.IneqMult.E n → EReal)
(hP : BregmanPPA.IneqMult.IsConvexProgram C f g) :
∀ x ∈ C, ∀ p ∈ BregmanPPA.IneqMult.nonnegOrthant m,
supdiffP C f g x p = {v | ∃ u ∈ BregmanPPA.Convergence.subdiffOp (BregmanPPA.IneqMult.indicatorPos m) p, v = BregmanPPA.IneqMult.gvec g x - u} := 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 (supergradient set of l)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.