Theorem 8 — nonquadratic proximal methods of multipliers converge to a saddle point
ProvedBregmanPPA.ProxMult.theorem8Consider a problem of the form (10):
with closed, nonempty and convex and proper lower semicontinuous convex functions, finite on , and let be its Lagrangian. Let be positive scalars bounded away from zero, a Bregman function on with zone , and a Bregman function on with zone and . Suppose conforms to the recursions
Then:
- if (10) has an optimal solution–Lagrange multiplier pair, i.e. a saddle pair with for all , then converges to one such pair;
- if (10) has no such pair, at least one of the sequences , is unbounded.
With and this is Rockafellar's proximal method of multipliers; other choices of give nonquadratic versions with the same guarantee.
Formalization Note "Optimal solution–Lagrange multiplier pair" is the saddle inequality, which the paper identifies with these pairs on p. 220 and which is exactly the zero set of used in the proof. "Converges to one" means both sequences converge, to the two components of a single saddle pair. The page's "" is read as (the paper's typography; is open). The -step uses a minimality predicate instead of (equivalent, the minimizer being unique, p. 222); the run requires and ; enters through toReal, exact by Lemma 3. The existence of runs is the separate item theorem8_existence. The §4.2 assumption that the dual functional is not everywhere concerns the dual problem of §4.2 and is not used in §5; it is not assumed, which can only strengthen the statement.
import Mathlib import Definitions.Def_BregmanPPA_Convergence_Model import Definitions.Def_BregmanPPA_IneqMult_Program import Definitions.Def_BregmanPPA_ProxMult_Saddle open Filter Topology
namespace BregmanPPA.ProxMult
/-- Theorem 8, pp. 220–221 (first two sentences): along a run of the nonquadratic proximal
method of multipliers (12), if (10) has a saddle pair (an optimal solution–Lagrange multiplier
pair), then `(x^k, p^k)` converges to one; if it has none, `{x^k}` or `{p^k}` is unbounded. -/
theorem theorem8 {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) (hcinf : ∃ ε : ℝ, 0 < ε ∧ ∀ k, ε ≤ 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) :
((∃ x' p', IsSaddlePair C f g x' p') →
∃ x' p', IsSaddlePair C f g x' p' ∧
Tendsto x atTop (𝓝 x') ∧ Tendsto p atTop (𝓝 p')) ∧
((¬ ∃ x' p', IsSaddlePair C f g x' p') →
¬ Bornology.IsBounded (Set.range x) ∨ ¬ Bornology.IsBounded (Set.range p)) := by sorry
end BregmanPPA.ProxMult
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.