§4.2.1, p. 150 — optimality of f + g is 0 ∈ ∇f(x) + ∂g(x)
ProvedProxAlg.FixedPoint.minimizer_iff_zero_memconvex-optimizationoptimality-conditionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1subdifferential
Let be differentiable and convex, and let be closed, proper and convex. A point minimizes their sum exactly when the negative gradient of is a subgradient of there:
This is the first-order condition on which the paper bases the fixed-point interpretation of proximal gradient.
Formalization Note The real-valued is finite everywhere, so its convex epigraph is closed and it is proper. No Lipschitz condition on is needed for this optimality statement. Values of are compared in EReal.
Preamble
import Mathlib import Definitions.Def_MoreauProx_Decomposition_ConvexDuality import Definitions.Def_ProxAlg_FixedPoint_Basic
Formal statement
namespace ProxAlg.FixedPoint
theorem minimizer_iff_zero_mem {n : ℕ}
(f : EuclideanSpace ℝ (Fin n) → ℝ) (hf : ConvexOn ℝ Set.univ f)
(hfd : Differentiable ℝ f) (g : EuclideanSpace ℝ (Fin n) → EReal)
(hg : MoreauProx.Decomposition.GammaZero g)
(xs : EuclideanSpace ℝ (Fin n)) :
(∀ y, ((f xs : ℝ) : EReal) + g xs ≤ ((f y : ℝ) : EReal) + g y) ↔
∃ v ∈ subdifferential g xs, gradient f xs + v = 0 := by sorry
end ProxAlg.FixedPoint
Source
Parikh & Boyd, Proximal Algorithms, Found. Trends Optim. 1(3) (2014), §4.2.1, p. 150, first displayed optimality condition
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.