Theorem 6 — the nonquadratic method of multipliers (9) finds an optimal multiplier, and limit points of solve (7)
ProvedBregmanPPA.EqMult.theorem6Consider the convex program
where is lower semicontinuous and convex, is an matrix, , is closed and convex, and . Its dual functional is
assumed not identically ; an optimal (Lagrange) multiplier is a maximizer of over .
Let be a Bregman function with zone and , let be its convex conjugate, and let be positive scalars with positive infimum. Let conform to the recursion
Then:
- if an optimal multiplier exists, converges to an optimal multiplier, and every limit point of solves (7);
- if no optimal multiplier exists, is unbounded.
With , (9) is the classical (quadratic) method of multipliers; the theorem covers the whole family of nonquadratic penalties generated by Bregman functions with zone and surjective gradient.
Formalization Note is a continuous linear map between EuclideanSpace ℝ (Fin n) and EuclideanSpace ℝ (Fin m). "Zone " is the Bregman structure with the whole space; is surjectivity of . Recursion (9) uses the real value of , which is finite everywhere under ; the arg min is a minimality predicate. "Limit point" is a subsequential limit; "unbounded" is "the range of is not bounded". This statement is the first two sentences of the conclusion of Theorem 6; the third (existence of infinite sequences) is the separate item theorem6_existence.
import Mathlib import Definitions.Def_InertialFB_IFB_ConvexAnalysis import Definitions.Def_fenchelConjugate import Definitions.Def_BregmanPPA_Convergence_Model import Definitions.Def_BregmanPPA_EqMult_EqConstrainedProgram open InertialFB.IFB ConvexOptimization Filter Topology
namespace BregmanPPA.EqMult
theorem theorem6 {n m : ℕ}
(A : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin m))
(b : EuclideanSpace ℝ (Fin m)) (X : Set (EuclideanSpace ℝ (Fin n)))
(f : EuclideanSpace ℝ (Fin n) → EReal)
(hP : IsEqProgram X f) (hd : ∃ p, dualEq A b X f p ≠ ⊥)
(h : EuclideanSpace ℝ (Fin m) → ℝ) (hh : BregmanPPA.Convergence.IsBregmanFunction Set.univ h)
(him : Function.Surjective (gradient h))
(c : ℕ → ℝ) (hc : ∀ k, 0 < c k) (hcinf : ∃ ε > 0, ∀ k, ε ≤ c k)
(x : ℕ → EuclideanSpace ℝ (Fin n)) (p : ℕ → EuclideanSpace ℝ (Fin m))
(hrun : IsEqMultRun A b X f h c x p) :
((∃ q, IsOptimalMultiplier A b X f q) →
(∃ pstar, IsOptimalMultiplier A b X f pstar ∧ Tendsto p atTop (𝓝 pstar)) ∧
∀ (φ : ℕ → ℕ) (x' : EuclideanSpace ℝ (Fin n)), StrictMono φ →
Tendsto (x ∘ φ) atTop (𝓝 x') → IsSolution7 A b X f x') ∧
((¬ ∃ q, IsOptimalMultiplier A b X f q) → ¬ Bornology.IsBounded (Set.range p)) := by sorry
end BregmanPPA.EqMult
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.