Lemma 2 — h*⁺ = (h + δ⁺)* = h* □ δ⁻ = inf_{w ≥ z} h*(w), and h*⁺ is nondecreasing
ProvedBregmanPPA.ProxMult.lemma2convex-conjugateinfimal-convolutionmonotone-conjugatep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a Bregman function on with zone and (the two standing assumptions of §4.2), extended by outside , and let be its monotone conjugate. Then for all
Furthermore, is nondecreasing: if componentwise, then .
These descriptions of the monotone conjugate are used to compute in the proof of Theorem 8, and its monotonicity is the hypothesis of the chain rule, Lemma A4.
Formalization Note All four quantities are EReal-valued; in the conjugates is the extension (extendedH S h), which agrees with on . The infimum over is an EReal infimum over the componentwise upper set of .
Preamble
import Mathlib import Definitions.Def_BregmanPPA_Convergence_Model import Definitions.Def_BregmanPPA_IneqMult_Program open Filter Topology
Formal statement
namespace BregmanPPA.ProxMult
/-- Lemma 2, p. 215: `h*⁺ = (h + δ⁺)* = h* □ δ⁻ = inf_{w ≥ z} h*(w)`, and `h*⁺` is
nondecreasing; here `h` is a Bregman function on `ℝᵐ` satisfying the two standing assumptions
of §4.2 (zone `S ⊇ Ω⁺`, `im ∇h ⊇ Ω⁺`), extended by `+∞` off `S̄`. -/
theorem lemma2 {m : ℕ} (S : Set (BregmanPPA.IneqMult.E m)) (h : BregmanPPA.IneqMult.E m → ℝ)
(hh : BregmanPPA.Convergence.IsBregmanFunction S h) (hS : BregmanPPA.IneqMult.posOrthant m ⊆ S)
(him : BregmanPPA.IneqMult.posOrthant m ⊆ gradient h '' S) :
(∀ z : BregmanPPA.IneqMult.E m,
BregmanPPA.IneqMult.monoConj h z = BregmanPPA.IneqMult.conjE (fun p => BregmanPPA.IneqMult.extendedH S h p + BregmanPPA.IneqMult.indicatorPos m p) z ∧
BregmanPPA.IneqMult.monoConj h z = BregmanPPA.IneqMult.infConv (BregmanPPA.IneqMult.conjE (BregmanPPA.IneqMult.extendedH S h)) (BregmanPPA.IneqMult.indicatorNeg m) z ∧
BregmanPPA.IneqMult.monoConj h z = ⨅ w ∈ {w : BregmanPPA.IneqMult.E m | ∀ i, z i ≤ w i}, BregmanPPA.IneqMult.conjE (BregmanPPA.IneqMult.extendedH S h) w) ∧
(∀ z z' : BregmanPPA.IneqMult.E m, (∀ i, z i ≤ z' i) → BregmanPPA.IneqMult.monoConj h z ≤ BregmanPPA.IneqMult.monoConj h z') := 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. 215, Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.