Lemma 6 — a strongly convex function has a unique minimizer on Q, with quadratic growth
ProvedPrimalDualSubgrad.DA.lemma_6convex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1strong-convexity
Let be a nonempty closed convex set in a finite-dimensional real normed space , and let be continuous on and strongly convex on with convexity parameter : for all , , (9.3). Then the problem (9.4) has a unique solution , and for every
The lemma makes the prox-center and the argmin map well defined, and (9.5) applied to is the quadratic growth used in Lemma 1 and Theorem 1.
Formalization Note Nonemptiness of and finite dimension of are implicit on the page (the proof starts from a nonempty level set; is finite-dimensional throughout the paper). The norm is arbitrary.
Preamble
import Mathlib
Formal statement
namespace PrimalDualSubgrad.DA
/-- Lemma 6 (p. 36). Let `Q` be a nonempty closed convex set in a finite-dimensional real normed
space and `d` a function continuous on `Q` and strongly convex on `Q` with parameter `σ > 0`
(Definition 1, (9.3)). Then `min_{x ∈ Q} d(x)` (9.4) has a unique solution `x*`, and
`d(x) ≥ d(x*) + σ/2 ‖x − x*‖²` for every `x ∈ Q` (9.5). -/
theorem lemma_6 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(Q : Set E) (d : E → ℝ) (σ : ℝ)
(hQc : IsClosed Q) (hQconv : Convex ℝ Q) (hQne : Q.Nonempty)
(hd : ContinuousOn d Q) (hσ : 0 < σ) (hsc : StrongConvexOn Q σ d) :
(∃! xs : E, xs ∈ Q ∧ ∀ x ∈ Q, d xs ≤ d x) ∧
∀ xs ∈ Q, (∀ x ∈ Q, d xs ≤ d x) → ∀ x ∈ Q, d xs + σ / 2 * ‖x - xs‖ ^ 2 ≤ d x := by sorry
end PrimalDualSubgrad.DA
Source
Nesterov, Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009), p. 36, Lemma 6 (with Definition 1, (9.3), (9.4))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.