Theorem 8 (existence clause) — if im ∇h_x = ℝⁿ, a sequence conforming to (12) exists from every (x⁰, p⁰) ∈ C × Ω̄⁺
ProvedBregmanPPA.ProxMult.theorem8_existencebregman-functionexistencep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-method-of-multipliers
Consider a problem of the form (10), a Bregman function on with zone , and a Bregman function on with zone and . If also , then for every sequence of positive scalars bounded away from zero and every there is an infinite sequence starting at and conforming to the recursions
This is the third sentence of Theorem 8; together with the goal it guarantees that the method never halts.
Formalization Note The page prints "for any " with an extra parenthesis. The step sizes satisfy the positive lower bound assumed at the start of Theorem 8.
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
/-- Theorem 8, p. 221 (third sentence): if moreover `im ∇h_x = ℝⁿ`, then for every sequence of
positive scalars `c k` bounded away from zero and every `(x⁰, p⁰) ∈ C × Ω̄⁺` an infinite sequence conforming to (12)
and starting at `(x⁰, p⁰)` exists. -/
theorem theorem8_existence {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 → ℝ)
(hP : BregmanPPA.IneqMult.IsConvexProgram C f g)
(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)
(himx : gradient hx '' Sx = Set.univ) :
∀ c : ℕ → ℝ, (∀ k, 0 < c k) →
(∃ ε : ℝ, 0 < ε ∧ ∀ k, ε ≤ c k) → ∀ x₀ ∈ C, ∀ p₀ ∈ BregmanPPA.IneqMult.nonnegOrthant m,
∃ (x : ℕ → BregmanPPA.IneqMult.E n) (p : ℕ → BregmanPPA.IneqMult.E m), x 0 = x₀ ∧ p 0 = p₀ ∧
IsProxMultRun C f g Sx hx Sp hp c x p := 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, Theorem 8 (third sentence)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.