(2.11) — δ_k(D) = Σλᵢ⟨gᵢ, xᵢ − x₀⟩ + ξ_D(−s_{k+1})
ProvedPrimalDualSubgrad.DA.eq_2_11convex-optimizationdual-averagingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a prox setting in a finite-dimensional normed space and arbitrary sequences , , . For every and , with ,
This is the explicit representation of the gap function through the support function of .
Preamble
import Mathlib import Definitions.Def_PrimalDualSubgrad_DA_DualAveraging
Formal statement
namespace PrimalDualSubgrad.DA
open Finset
/-- (2.11), p. 8: for any sequences `x_i ∈ E`, `g_i ∈ E*`, `λ_i ∈ ℝ` and `D ≥ 0`,
`δ_k(D) = ∑_{i=0}^k λ_i⟨g_i, x_i − x0⟩ + ξ_D(−s_{k+1})`. -/
theorem eq_2_11 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(P : ProxSetting E) (lam : ℕ → ℝ) (g : ℕ → StrongDual ℝ E) (x : ℕ → E)
(k : ℕ) (D : ℝ) (hD : 0 ≤ D) :
delta P lam g x k D =
∑ i ∈ range (k + 1), lam i * g i (x i - P.x0) + xi P D (-(sAgg lam g (k + 1))) := by sorry
end PrimalDualSubgrad.DA
Source
Nesterov, Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009), §2, (2.11), p. 8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.