Chapter 08 — Primal and Dual Projected Subgradient Methods
Proofs omitted. Hover over highlighted terms to see their Lean types.
Algorithm 8.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.1: for a differentiable objective f on an abstract Euclidean space E, the gradient method with stepsizes t_k and initial point x0 is the sequence generated by the update x^{k+1} = x^k - t_k ∇ f(x^k) from equation (8.1).
universe u
open scoped Gradient
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
def gradient_method (f : E → ℝ) (t : ℕ → ℝ) (x0 : E) : ℕ → EDefinition 8.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.1: in this chapter, an abstract Euclidean space is modeled by the canonical real inner-product-space owner InnerProductSpace ℝ E; the finite-dimensionality hypothesis and the derived Euclidean norm formula are recalled below as companion views.
universe u
open scoped RealInnerProductSpace
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
#check InnerProductSpace ℝ EProposition 8.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 8.1 (1): if a finite family of closed sets has nonempty intersection, then the global minimizer set of the pointwise maximum of the distance functions is exactly that intersection.
universe u v
variable {E : Type u} {ι : Type v} [PseudoMetricSpace E] [Fintype ι] [Nonempty ι]
theorem global_minimizers_max_infDist_to_family
(S : ι → Set E) (hclosed : ∀ i, IsClosed (S i))
(hnonempty : (⋂ i, S i).Nonempty) :
{x | IsMinOn (max_infDist_to_family S) Set.univ x} = ⋂ i, S iTheorem 8.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.1: if a proper convex extended-real-valued function has uniformly bounded subgradients on a set C contained in interior (effective_domain f), then x ↦ (f x).toReal is Lipschitz on C with Lipschitz constant L_f.
universe u
open Metric
open Bornology
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
theorem lipschitzOnWith_toReal_of_subgradientNormBoundOn
(f : E → EReal) (C : Set E) (hf_proper : IsProperExtendedRealFunction f)
(hf_convex : is_convex_function f)
(hC_subset : C ⊆ interior (effective_domain f))
(hbound : SubgradientNormBoundOn f C) :
LipschitzOnWith (Real.toNNReal hbound.L_f) (fun x ↦ (f x).toReal) CAlgorithm 8.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.2: given an initial point x0, step sizes t_k, and an index-dependent rule g that selects the current direction from the current iterate, the subgradient method generates the iterates by the update x^{k+1} = x^k - t_k g_k(x^k).
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
def subgradient_method (g : ℕ → E → E) (t : ℕ → ℝ) (x0 : E) : ℕ → EDefinition 8.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.2: the unconstrained problem (P) for an objective f is represented by the set of points that globally minimize f on the whole ambient space.
universe u v
variable {E : Type u} {α : Type v} [Preorder α]
def unconstrained_problem_solutions (f : E → α) : Set E :=
{x | IsMinOn f Set.univ x}
-- Proof sketch: unfold `unconstrained_problem_solutions`; membership in the set is definitionally
-- the statement that the point is a global minimizer of `f`.Lemma 8.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.2: if f : E → (-∞, ∞] is represented by an EReal-valued function with no ⊥ values, x lies in the interior of dom(f), and d is a descent direction of f at x, then f strictly decreases along the ray x + t • d for all sufficiently small t > 0, and those nearby points remain in dom(f).
universe u
open scoped Topology
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem exists_strict_decrease_along_descent_direction
(f : E → EReal) (x d : E) (h_ne_bot : ∀ y, f y ≠ ⊥)
(hx : x ∈ interior (effective_domain f))
(hd : is_descent_direction_at f x d) :
∃ ε > 0, ∀ t : ℝ, t ∈ Set.Ioc (0 : ℝ) ε →
x + t • d ∈ effective_domain f ∧ f (x + t • d) < f xAlgorithm 8.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.3: for a nonempty closed convex feasible set C, a feasible initial point x0, stepsizes t_k, and a rule g selecting a subgradient direction at each current feasible iterate, the projected subgradient method generates the sequence x^{k+1} = P_C (x^k - t_k g_k(x^k)).
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
def projected_subgradient_method (C : Set E)
(hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
(g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C) : ℕ → CDefinition 8.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.3: a nonzero vector d is a descent direction of f at x when the directional derivative of f at x along d exists and is strictly negative.
universe u
open Filter
open scoped Topology
variable {E : Type u} [AddCommMonoid E] [Module ℝ E]
def is_descent_direction_at (f : E → EReal) (x d : E) : Prop :=
d ≠ 0 ∧
∃ ℓ : EReal,
Tendsto (fun α : ℝ ↦ (f (x + α • d) - f x) / (α : EReal)) (𝓝[>] (0 : ℝ)) (𝓝 ℓ) ∧
ℓ < 0
-- Proof sketch: unfold `is_descent_direction_at`; the statement is exactly the defining
-- right-limit characterization of a descent direction.Definition 8.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.4: the exact line search stepsizes at the current iterate x are the nonnegative scalars that minimize the one-dimensional descent objective t ↦ f (x - t • ∇ f x) over all t ≥ 0.
universe u
open scoped Gradient
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
def exact_line_search_stepsizes (f : E → ℝ) (x : E) : Set ℝ :=
{t | t ∈ Set.Ici (0 : ℝ) ∧ IsMinOn (fun s ↦ f (x - s • ∇ f x)) (Set.Ici 0) t}
-- Proof sketch: unfold `exact_line_search_stepsizes`; membership is definitionally the conjunction
-- that `t` is feasible (`t ≥ 0`) and that it minimizes the line-search objective on the feasible
-- ray `Set.Ici 0`.Lemma 8.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.4: if the maximization problem with only the constraint f1 ≤ 0 has unique optimal solution yTilde, then exactly one of the following holds for the two-constraint problem: (i) f2 yTilde ≤ 0 and the optimal solution set is {yTilde}; (ii) 0 < f2 yTilde and the optimal solution set is the maximizer set on the boundary f2 = 0.
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
theorem optimalSolutionSet_xor_singleton_or_boundary_of_unique_one_constraint_solution
(g f1 f2 : E → ℝ) (hg_concave : ConcaveOn ℝ Set.univ g)
(hf1_convex : ConvexOn ℝ Set.univ f1) (hf2_convex : ConvexOn ℝ Set.univ f2)
(yTilde : E)
(hyTilde :
optimalSolutionSet g (oneConstraintFeasibleRegion f1) = {yTilde}) :
Xor'
(optimalSolutionSetSingletonCase g f1 f2 yTilde)
(optimalSolutionSetBoundaryCase g f1 f2 yTilde)Definition 8.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.5: the constrained minimization model min {f(x) : x ∈ C} is represented by the set of feasible points that minimize f over C.
universe u v
variable {E : Type u} {α : Type v} [Preorder α]
def constrained_problem_solutions (f : E → α) (C : Set E) : Set E :=
{x | x ∈ C ∧ IsMinOn f C x}
-- Proof sketch: unfold `constrained_problem_solutions`; membership is definitionally feasibility
-- together with the owner predicate `IsMinOn` on the same feasible set.Lemma 8.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.5 (1): for γ > 0, the piecewise Wolfe example function from equation (8.5) is the support function σ_C of the set C = {(y₁, y₂) | y₁^2 + y₂^2 / γ ≤ 1, y₁ ≥ 1 / √(1 + γ)}.
open InnerProductSpace (toDualMap)
open WithLp (toLp ofLp)
local notation "E" => EuclideanSpace ℝ (Fin 2)
theorem wolfe_example_function_eq_support_function
(γ : ℝ) (hγ : 0 < γ) :
(fun x : E ↦ (wolfe_example_function γ x : EReal)) =
fun x : E ↦ support_function (wolfe_example_support_set γ) (toDualMap ℝ E x)Algorithm 8.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.6: for a finite family S of nonempty closed convex sets, an initial point x0, and a rule i selecting at each iterate one of the currently farthest sets, the greedy projection algorithm generates the sequence x^{k+1} = P_{S_{i_k}}(x^k).
universe u
open Metric
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ}
def greedy_projection_method (S : Fin m → Set E)
(hS_nonempty : ∀ j, (S j).Nonempty) (hS_closed : ∀ j, IsClosed (S j))
(hS_convex : ∀ j, Convex ℝ (S j)) (i : ℕ → E → Fin m) (x0 : E) : ℕ → ELemma 8.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.6 (1): source clause (a). The iterates generated by the gradient method with exact line search for Wolfe's example are differentiability points of the objective.
universe u
open scoped Gradient
theorem wolfe_example_gradient_method_iterate_differentiableAt
{γ : ℝ} (hγ : 1 < γ) {t : ℕ → ℝ}
(ht :
∀ k,
t k ∈ exact_line_search_stepsizes (wolfe_example_function γ)
(gradient_method (wolfe_example_function γ) t (wolfe_initial_point γ) k)) :
∀ k,
DifferentiableAt ℝ (wolfe_example_function γ)
(gradient_method (wolfe_example_function γ) t (wolfe_initial_point γ) k)Algorithm 8.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.7: for two nonempty closed convex sets S₁ and S₂ and an initial point x0 ∈ S₂, the alternating projection method generates the sequence x^{k+1} = P_{S₂}(P_{S₁}(x^k)).
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
def alternating_projection_method (S₁ S₂ : Set E)
(hS₁_nonempty : S₁.Nonempty) (hS₁_closed : IsClosed S₁) (hS₁_convex : Convex ℝ S₁)
(hS₂_nonempty : S₂.Nonempty) (hS₂_closed : IsClosed S₂) (hS₂_convex : Convex ℝ S₂)
(x0 : S₂) : ℕ → S₂Assumption 8.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Assumption 8.7: clauses (A)-(D) hold for the constrained convex problem min {f x : x ∈ C}, namely f is proper, closed, and convex, C is a nonempty closed convex subset of interior (dom(f)), XStar is the nonempty optimal set of the constrained problem min {f x : x ∈ C}, and fOpt is its optimal value.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
class IsConstrainedConvexProblem
(f : E → EReal) (C XStar : Set E) (fOpt : ℝ) : Prop
extends IsProperExtendedRealFunction f where
closed : LowerSemicontinuous f
convex : is_convex_function f
feasible_nonempty : C.Nonempty
feasible_closed : IsClosed C
feasible_convex : Convex ℝ C
feasible_subset_interior_effective_domain : C ⊆ interior (effective_domain f)
optimal_set_eq : XStar = constrained_problem_solutions f C
optimal_set_nonempty : XStar.Nonempty
optimal_value_isGLB : IsGLB (f '' C) (fOpt : EReal)Definition 8.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.7: a subgradient selection for f on C is a deterministic rule assigning to each x ∈ C a chosen subgradient f'(x) ∈ ∂ f(x), that is, a function C → E* whose value at every feasible point belongs to the subdifferential of f at that point.
universe u
variable {E : Type u} [AddCommGroup E] [Module ℝ E]
structure SubgradientSelection (f : E → EReal) (C : Set E) where
toFun : C → Module.Dual ℝ E
mem_subdifferential : ∀ x : C, toFun x ∈ subdifferential f x.1Proposition 8.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 8.7: for a real-valued objective, clause (A) of Assumption 8.34 is equivalent to saying that, for each k, the conditional expectation of the stochastic subgradient given x^k satisfies the pointwise subgradient inequality at x^k almost surely, i.e. for every z, one has f z ≥ f (x^k) + ⟪E[g^k | x^k], z - x^k⟫. Since f is real-valued here, dom(f) = E.
universe u v
open scoped ProbabilityTheory
open MeasureTheory
variable {Ω : Type v} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [MeasurableSpace E] [BorelSpace E]
variable {f : E → ℝ} {x : ℕ → Ω → E} {g : ℕ → Ω → E}
-- Proof sketch: expand `StochasticProjectedSubgradientOracle.unbiased k` and rewrite membership in
-- `euclideanSubdifferentialAt` using the Chapter 3 bridge lemmas
-- `mem_euclideanSubdifferentialAt_iff`, `mem_strongDualSubdifferential`, `mem_subdifferential`,
-- and `is_subgradient_at_coe_iff`; then use `toDualMap_apply_apply` to identify the pairing with
-- the inner product.
theorem stochastic_projected_subgradient_unbiased_iff_ae_subgradient_inequality (k : ℕ) :
(∀ᵐ ω ∂μ,
μ[g k | MeasurableSpace.comap (x k) inferInstance] ω ∈
euclideanSubdifferentialAt f (x k ω)) ↔
∀ᵐ ω ∂μ,
∀ z : E,
f z ≥
f (x k ω) +
inner ℝ
(μ[g k | MeasurableSpace.comap (x k) inferInstance] ω)
(z - x k ω)Algorithm 8.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.8: given a real matrix A with A Aᵀ invertible, a right-hand side b, and an initial point x0 ∈ ℝ^n_+, Algorithm 1 generates the sequence x^{k+1} = [x^k - Aᵀ (A Aᵀ)⁻¹ (A x^k - b)]_+, where [·]_+ is the coordinatewise positive part.
open Matrix
open scoped Matrix
variable {m n : ℕ}
def nonnegative_affine_feasibility_method
(A : Matrix (Fin m) (Fin n) ℝ) [Invertible (A * A.transpose)] (b : Fin m → ℝ)
(x0 : Set.Ici (0 : Fin n → ℝ)) : ℕ → Set.Ici (0 : Fin n → ℝ)Definition 8.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.8: the best achieved function value at iteration k is the minimum of the objective values f (x^n) over all indices n = 0, 1, …, k.
universe u v
variable {E : Type u} {α : Type v} [LinearOrder α]
def best_achieved_function_value (f : E → α) (x : ℕ → E) (k : ℕ) : α :=
((Finset.range (k + 1)).image fun n ↦ f (x n)).min' (objective_value_prefix_nonempty f x k)Proposition 8.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 8.8: if the stochastic projected subgradient oracle along the sampled Algorithm 8.12 iterates has bound constant L_tilde_f controlled by δ * finite_sum_stochastic_subgradient_bound_constant L, and Algorithm 8.12 uses the canonical half-squared-diameter stepsize rule from Theorem 8.30, then the expected best objective gap of the first k + 1 iterates satisfies the finite-sum O(1 / √k) estimate `E(f_best^k) - fOpt ≤ δ * finite_sum_stochastic_subgradient_bound_constant L * √(2 Θ) / √(k + 2)`.
universe u v
open MeasureTheory
open scoped ProbabilityTheory
variable {E : Type u} {Ω : Type v}
variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]
variable [MeasurableSpace E] [BorelSpace E]
variable {f : E → ℝ} {C XStar : Set E} {fOpt δ Θ : ℝ} {m : ℕ}
variable (L : Fin m → ℝ)
variable (h_problem : IsConstrainedConvexProblem (fun x : E ↦ (f x : EReal)) C XStar fOpt)
variable (i : ℕ → Ω → Fin m) (g : ℕ → C → Fin m → E) (x0 : C)
local notation "x[" k "]" =>
finite_sum_stochastic_projected_subgradient_method
C h_problem.feasible_closed h_problem.feasible_convex Θ L i g x0 k
theorem finite_sum_stochastic_projected_subgradient_expected_best_value_gap_le
(h_oracle :
StochasticProjectedSubgradientOracle μ f
(fun n ω ↦ (x[n] ω : E))
(fun n ω ↦ g n (x[n] ω) (i n ω)))
(hΘ : C.HasHalfSquaredDiameterBound Θ)
(h_stepsize :
projectedSubgradientUsesHalfSquaredDiameterStepsize Θ h_oracle.L_tilde_f
(finite_sum_stochastic_projected_subgradient_stepsize Θ L))
(h_oracle_bound :
(2 * (1 + Real.log 3)) * h_oracle.L_tilde_f ≤
δ * finite_sum_stochastic_subgradient_bound_constant L)
{k : ℕ} (hk : 2 ≤ k) :
μ[fun ω ↦ best_achieved_function_value f (fun n ↦ (x[n] ω : E)) k] - fOpt ≤
δ * finite_sum_stochastic_subgradient_bound_constant L *
Real.sqrt (2 * Θ) / Real.sqrt ((k : ℝ) + 2)Remark 8.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Remark 8.8: if f is convex and the feasible set C lies in the interior of dom(f), then f is subdifferentiable at every point of C, equivalently C ⊆ dom(∂ f).
universe u
open scoped Topology
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
theorem subset_subdifferential_domain_of_subset_interior_effective_domain
(f : E → EReal) (C : Set E) (hf_convex : is_convex_function f)
(hC : C ⊆ interior (effective_domain f)) :
C ⊆ subdifferential_domain fAlgorithm 8.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.9: given affine rows a_iᵀ x = b_i, an initial point x0, and a rule choosing at each iterate a row with maximal normalized residual, the greedy linear-feasibility projection method updates x^k either by the orthogonal correction onto the selected row hyperplane or by the positive part x⁺ = [x]_+, according to which correction is farther from the current iterate.
variable {m n : ℕ}
local notation "E" => Fin n → ℝ
def greedy_linear_feasibility_projection_method
(a : Fin m → E) (b : Fin m → ℝ) (i : ℕ → E → Fin m) (x0 : E) : ℕ → EProposition 8.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 8.9: for m nonnegative numbers with positive maximum, the ratio β = (∑ i, α_i) / max_i α_i lies between 1 and m.
open scoped BigOperators
variable {m : ℕ} [NeZero m]
theorem sum_div_max_mem_Icc
(a : Fin m → NNReal)
(hmax_pos : 0 < Finset.univ.sup' Finset.univ_nonempty a) :
(∑ i, a i) / (Finset.univ.sup' Finset.univ_nonempty a) ∈ Set.Icc (1 : NNReal) mAlgorithm 8.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.10: for a nonempty closed convex feasible set C, a feasible initial point x0, stepsizes t_k, and a sample-indexed direction rule g, the stochastic projected subgradient method generates the pathwise iterate sequence x^{k+1}(ω) = P_C (x^k(ω) - t_k g_k(x^k(ω), ω)).
universe u v
variable {E : Type u} {Ω : Type v}
variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
def stochastic_projected_subgradient_method (C : Set E)
(hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
(g : ℕ → C → Ω → E) (t : ℕ → ℝ) (x0 : C) : ℕ → Ω → CDefinition 8.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.10: Polyak's stepsize rule assigns to a point x with chosen subgradient vector g the stepsize (f x - fOpt) / ‖g‖^2 when g ≠ 0, and the fallback value 1 when g = 0.
universe u
variable {E : Type u} [NormedAddCommGroup E]
def polyak_stepsize (f : E → EReal) (fOpt : ℝ) (x g : E) : ℝ :=
if ‖g‖ = 0 then 1 else ((f x).toReal - fOpt) / ‖g‖ ^ (2 : ℕ)
-- Proof sketch: unfold `polyak_stepsize`; for `g = 0` one has `‖g‖ = 0`, so the defining `if`
-- reduces immediately to its first branch.Algorithm 8.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.11: for a nonempty closed convex feasible set C, a feasible initial point x0, a constant Θ, and a rule selecting one component subgradient for each summand at each current iterate, the finite-sum projected subgradient method generates the sequence x^{k+1} = P_C (x^k - (√(2 Θ) / (‖∑ᵢ fᵢ'(x^k)‖ √(k + 1))) ∑ᵢ fᵢ'(x^k)).
universe u
open scoped BigOperators
open Metric
open Bornology
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
def finite_sum_projected_subgradient_method {m : ℕ} (C : Set E)
(hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
(Θ : ℝ) (g : ℕ → C → Fin m → E) (x0 : C) : ℕ → CLemma 8.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.11: under Assumption 8.7, every projected-subgradient step with nonnegative stepsize satisfies the fundamental inequality `‖x^{k+1} - xStar‖^2 ≤ ‖x^k - xStar‖^2 - 2 t_k ((f x^k).toReal - fOpt) + t_k^2 ‖g_k‖^2` for each optimal point xStar ∈ XStar, where the chosen direction at iteration k is a subgradient of f at x^k.
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable {f : E → EReal} {C XStar : Set E} {fOpt : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
-- Proof sketch: use nonexpansiveness of the metric projection to compare `‖x[k + 1] - xStar‖`
-- with `‖x[k] - t_k g_k - xStar‖`, expand the square, and rewrite the cross term with the
-- subgradient inequality coming from the hypothesis
-- `toDualMap ℝ E (g k (x[k])) ∈ ∂ₛ f(x̄[k])`. Then use
-- `hxStar : xStar ∈ XStar` together with `h_problem.optimal_set_eq` and
-- `h_problem.optimal_value_isGLB` to identify `xStar` as an optimal feasible point with value
-- `fOpt`.
variable [CompleteSpace E]
variable {g : ℕ → C → E} {t : ℕ → ℝ} {x0 : C}
local notation "x[" k "]" =>
projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
local notation "x̄" =>
projected_subgradient_method_iterate C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
theorem projected_subgradient_method_fundamental_inequality
(h_subgrad :
∀ k,
toDualMap ℝ E (g k (x[k])) ∈ ∂ₛf(x̄[k]))
{xStar : E} (hxStar : xStar ∈ XStar) (k : ℕ) (ht_nonneg : 0 ≤ t k) :
‖x̄[k + 1] - xStar‖ ^ 2 ≤
‖x̄[k] - xStar‖ ^ 2 -
2 * t k * ((f x̄[k]).toReal - fOpt) +
(t k) ^ 2 * ‖g k (x[k])‖ ^ 2Proposition 8.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 8.11 is source-facing in the Chapter 8 dual projected-subgradient API. Domain sampling against the existing project owners shows that the canonical subgradient surface is Chapter 3's strongDualSubdifferential; the genuinely new object here is only the dual function q. Since the textbook writes the subgradient as the multiplier-space vector -g(x_λ), the main statement uses the canonical Riesz bridge toDualMap rather than introducing a second local subgradient owner.
universe u
open InnerProductSpace (toDualMap)
open Matrix
variable {E : Type u} {m : ℕ}
recall strongDualSubdifferentialAlgorithm 8.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.12: for a closed convex feasible set C, a feasible initial point x0, componentwise subgradient choices g k x j, and a sampled index rule i_k, the stochastic projected subgradient method for a finite-sum objective is the Algorithm 8.10 iteration specialized to the sampled direction g k x (i_k ω) and the stepsize √(2 Θ m) / (L̃_f √(k + 1)), where L̃_f = √m * √(∑ i, L_i^2).
universe u v
open scoped BigOperators
variable {E : Type u} {Ω : Type v}
variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
abbrev finite_sum_stochastic_projected_subgradient_method {m : ℕ} (C : Set E)
(hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
(Θ : ℝ) (L : Fin m → ℝ) (i : ℕ → Ω → Fin m) (g : ℕ → C → Fin m → E) (x0 : C) :
ℕ → Ω → C :=
stochastic_projected_subgradient_method C (set_nonempty_of_mem x0) hC_closed hC_convex
(fun k x ω ↦ g k x (i k ω))
(finite_sum_stochastic_projected_subgradient_stepsize Θ L)
x0Assumption 8.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Assumption 8.12: a subgradient norm bound on f over C consists of a constant L_f > 0 such that every continuous-dual subgradient of f at every point of C has norm at most L_f.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
structure SubgradientNormBoundOn (f : E → EReal) (C : Set E) where
L_f : ℝ
L_f_pos : 0 < L_f
norm_le {x : E} {g : StrongDual ℝ E}
(hx : x ∈ C) (hg : g ∈ strongDualSubdifferential f x) : ‖g‖ ≤ L_fDefinition 8.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.12: a vector x is an ε-optimal solution of min {f(x) : x ∈ C} when x lies in C and its objective value is at most fOpt + ε.
universe u
variable {E : Type u}
def is_epsilon_optimal_solution
(f : E → EReal) (C : Set E) (fOpt ε : ℝ) (x : E) : Prop :=
x ∈ C ∩ f ⁻¹' Set.Iic (fOpt + ε : EReal)
-- Proof sketch: unfold `is_epsilon_optimal_solution`; the predicate was defined to be membership
-- in the feasible sublevel set `C ∩ f ⁻¹' Set.Iic (fOpt + ε)`.Proposition 8.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 8.12: if the partial-averaging iterate x̄^k = ∑_{n=[k/2]}^k η_n^k x^n is feasible and its objective gap is bounded by M / √(k + 1), then the usual threshold M² / ε² - 1 ≤ k guarantees that x̄^k lies in the feasible (fOpt + ε)-sublevel set. In particular, the required number of iterations is of order 1 / ε².
universe u v
open scoped BigOperators
variable {E : Type u} {G : Type v}
variable [AddCommMonoid E] [Module ℝ E] [Norm G]
variable {m : ℕ}
variable (x : ℕ → E) (γ : ℕ → ℝ) (h : ℕ → G)
local notation "x̄[" k "]" =>
Finset.sum (Finset.Icc (k / 2) k) fun n ↦
((γ n / ‖h n‖) /
Finset.sum (Finset.Icc (k / 2) k) (fun j ↦ γ j / ‖h j‖)) • x n
theorem partial_averaging_iterate_mem_feasible_sublevel_set_of_iteration_count
{X : Set E} {f : E → ℝ} {g : Fin m → E → ℝ}
(fOpt M ε : ℝ) (k : ℕ)
(hM : 0 ≤ M) (hε : 0 < ε)
(h_rate : f x̄[k] - fOpt ≤ M / Real.sqrt ((k : ℝ) + 1))
(h_feasible : x̄[k] ∈ partialAveragingFeasibleSet X g)
(hk : M ^ (2 : ℕ) / ε ^ (2 : ℕ) - 1 ≤ (k : ℝ)) :
x̄[k] ∈
partialAveragingFeasibleSet X g ∩
(fun y ↦ (f y : EReal)) ⁻¹' Set.Iic (fOpt + ε : EReal)Algorithm 8.13
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.13: for a nonempty closed convex feasible set C, a feasible initial point x0, positive stepsizes t_k, and chosen component subgradients g^{k,i}, the incremental projected subgradient method generates outer iterates x^{k+1} = x^{k,m} where x^{k,i+1} = P_C (x^{k,i} - t_k g^{k,i}) and x^{k,0} = x^k.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
def incremental_projected_subgradient_method {m : ℕ} (C : Set E)
(hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
(t : ℕ → ℝ) (g : ℕ → C → Fin m → E) (x0 : C) : ℕ → CDefinition 8.13
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.13: the convex feasibility problem for a finite nonempty family of sets S i can be reformulated through the max-distance objective x ↦ max_i d_{S_i}(x).
universe u v
variable {ι : Type v} {α : Type u} [Fintype ι] [Nonempty ι] [PseudoMetricSpace α]
def convex_feasibility_max_distance (S : ι → Set α) : α → ℝ :=
fun x ↦ Finset.univ.sup' Finset.univ_nonempty (fun i ↦ Metric.infDist x (S i))
-- Proof sketch: unfold `convex_feasibility_max_distance`; evaluation at `x` is exactly the
-- defining finite maximum of the distances from `x` to the sets `S i`.Theorem 8.13
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.13 (1): clause (a). Under Assumptions 8.7 and 8.12, the projected subgradient method with Polyak's stepsize rule has nonincreasing squared distance to every optimal point xStar ∈ XStar.
universe u
open InnerProductSpace (toDualMap)
open scoped BigOperators
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable (f : E → EReal) (C XStar : Set E) (fOpt : ℝ)
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
local notation "gap" =>
objective_gap (f := f) (C := C) (XStar := XStar) (fOpt := fOpt) (h_problem := h_problem)
(g := g) (t := t) (x0 := x0)
theorem projected_subgradient_method_sqdist_mono_of_polyak_stepsize
(h_norm : SubgradientNormBoundOn f C)
(h_subgrad :
∀ k,
(toDualMap ℝ E (g k (x[k])) : Module.Dual ℝ E) ∈ subdifferential f (x[k] : E))
(h_polyak :
∀ k,
t k = polyak_stepsize f fOpt (x[k] : E) (g k (x[k])))
{xStar : E} (hxStar : xStar ∈ XStar) (k : ℕ) :
‖(x[k + 1] : E) - xStar‖ ^ 2 ≤ ‖(x[k] : E) - xStar‖ ^ 2Algorithm 8.14
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.14: given an initial multiplier λ^0 ∈ ℝ_+^m, positive stepsizes γ_k, and a rule selecting for each multiplier λ a minimizer of the Lagrangian over X, the dual projected subgradient method generates the multiplier sequence λ^k; if g(x^k) = 0 it stays at λ^k, and otherwise updates by λ^{k+1} = [λ^k + γ_k g(x^k) / ‖g(x^k)‖]_+, where x^k is the selected Lagrangian minimizer at λ^k.
universe u
open scoped BigOperators
variable {E : Type u} {m : ℕ}
variable [NormedAddCommGroup E]
local notation "Λ" => EuclideanSpace ℝ (Fin m)
def dual_projected_subgradient_method
(X : Set E) (g : Fin m → E → ℝ)
(xSel : (Fin m → NNReal) → {x // x ∈ X}) (γ : ℕ → ℝ) (lam0 : Fin m → NNReal) :
ℕ → Fin m → NNRealAlgorithm 8.15
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.15: given an initial multiplier λ⁰ ∈ ℝ_+^m and a rule selecting for each multiplier λ an index minimizing the score vector v = c + Aᵀ λ, the dual projected subgradient method for (LP) generates the multiplier sequence λ^k by setting x^k = e_{i_k} and updating λ^{k+1} = [λ^k + (1 / √(k + 1)) (A x^k - b) / ‖A x^k - b‖₂]_+.
open Matrix
open WithLp (toLp)
variable {m n : ℕ}
local notation "Λ" => EuclideanSpace ℝ (Fin m)
local notation "X" => Fin n → ℝ
def dual_projected_subgradient_lp_method
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(iSel : (Fin m → NNReal) → Fin n) (lam0 : Fin m → NNReal) : ℕ → Fin m → NNRealDefinition 8.15
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.15: a sequence x is Fejér monotone with respect to S if, for every y ∈ S, the distance from x (k + 1) to y is at most the distance from x k to y for all k ≥ 0.
universe u
variable {α : Type u} [PseudoMetricSpace α]
def IsFejerMonotoneWithRespectTo (x : ℕ → α) (S : Set α) : Prop :=
∀ y ∈ S, ∀ k : ℕ, dist (x (k + 1)) y ≤ dist (x k) y
-- Proof sketch: apply `antitone_nat_of_succ_le` pointwise in `y` to pass from the successor-step
-- inequalities to an antitone distance profile, and recover the displayed successor inequality
-- from antitonicity by evaluating at `k ≤ k + 1`.Algorithm 8.16
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 8.16: given a route-incidence map linksUsedBySource, link capacities c, stepsizes α_k, and a rule xSel selecting for each link-price vector λ^k the corresponding source-rate update from step (A), the NUM dual projected subgradient method starts from λ^0 = 0 and recursively generates the link-price sequence by λ^{k+1}_ℓ = [λ^k_ℓ + α_k (∑_{s ∈ S(ℓ)} x_s^k - c_ℓ)]_+.
universe u v
variable {Source : Type u} {Link : Type v}
variable [Fintype Source] [DecidableEq Link]
def network_utility_dual_projected_subgradient_method
(linksUsedBySource : Source → Finset Link) (c : Link → ℝ)
(α : ℕ → ℝ) (xSel : (Link → NNReal) → Source → ℝ) : ℕ → Link → NNRealDefinition 8.16
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.16: the incremental projected subgradient problem uses the aggregate objective obtained by summing the component functions f i.
universe u v w
open scoped BigOperators
variable {ι : Type w} [Fintype ι] {E : Type u} {α : Type v} [AddCommMonoid α]
def finite_sum_objective (f : ι → E → α) : E → α :=
fun x ↦ ∑ i, f i x
-- Proof sketch: unfold `finite_sum_objective`; evaluation at `x` is definitionally the finite sum
-- of the component objective values `f i x`.Theorem 8.16
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.16: if a sequence is Fejér monotone with respect to a set S, every sequential limit point of the sequence belongs to S, and the sequence has at least one sequential limit point, then the whole sequence converges to one of its sequential limit points.
universe u
variable {α : Type u} [PseudoMetricSpace α]
theorem tendsto_to_limitPoint_of_isFejerMonotoneWithRespectTo
{x : ℕ → α} {S : Set α}
(hFejer : ∀ y ∈ S, ∀ k : ℕ, dist (x (k + 1)) y ≤ dist (x k) y)
(hlimitPoints_subset : {y : α | MapClusterPt y Filter.atTop x} ⊆ S)
(hlimitPoint : ∃ y : α, MapClusterPt y Filter.atTop x) :
∃ y : α, MapClusterPt y Filter.atTop x ∧ Filter.Tendsto x Filter.atTop (nhds y)Definition 8.17
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.17: the feasible set of the problem min f(x) subject to g(x) ≤ 0 and x ∈ X consists of the points of X satisfying every coordinatewise inequality constraint g x i ≤ 0.
universe u v
variable {E : Type u} {m : ℕ}
def inequality_constrained_primal_feasible_set
(X : Set E) (g : E → Fin m → ℝ) : Set E :=
{x | x ∈ X ∧ ∀ i : Fin m, g x i ≤ 0}
-- Proof sketch: unfold `inequality_constrained_primal_feasible_set`; membership is exactly the
-- conjunction of `x ∈ X` and the coordinatewise inequalities `g x i ≤ 0`.Theorem 8.17
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.17: under Assumptions 8.7 and 8.12, the projected subgradient sequence generated with Polyak's stepsize rule converges to a point of the optimal set XStar = X^*.
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
variable {f : E → EReal} {C XStar : Set E} {fOpt : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (h_bound : SubgradientNormBoundOn f C)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
include h_bound
theorem projected_subgradient_method_tendsto_point_in_optimal_set_of_polyak_stepsize
(h_subgrad :
∀ n,
toDualMap ℝ E (g n (x[n])) ∈ strongDualSubdifferential f (x[n] : E))
(h_polyak :
∀ n,
t n = polyak_stepsize f fOpt (x[n] : E) (g n (x[n]))) :
∃ xStar : E,
xStar ∈ XStar ∧
Filter.Tendsto (fun n ↦ (x[n] : E)) Filter.atTop (nhds xStar)Theorem 8.17.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.17.1: if the previously established projected-subgradient bound f_best - f_opt ≤ L_f d_{X^*}(x^0) / √(k + 1) holds, then the sufficient condition L_f d_{X^*}(x^0) / √(k + 1) ≤ ε implies f_best - f_opt ≤ ε. In particular, this yields the usual O(ε⁻²) iteration estimate through the companion iteration-count inequality.
universe u
variable {E : Type u} [PseudoMetricSpace E]
theorem best_function_value_gap_le_epsilon_of_rate_bound
(x0 : E) (XStar : Set E) (fBest fOpt Lf ε : ℝ) (k : ℕ)
(h_rate : fBest - fOpt ≤ Lf * Metric.infDist x0 XStar / Real.sqrt (k + 1))
(h_bound : Lf * Metric.infDist x0 XStar / Real.sqrt (k + 1) ≤ ε) :
fBest - fOpt ≤ εTheorem 8.18
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.18: under Assumptions 8.7 and 8.12, if the projected subgradient method uses Polyak's stepsize rule along the generated trajectory, then every index k with h_bound.L_f^2 d_{X^*}(x^0)^2 / ε^2 - 1 ≤ k guarantees that the best objective value attained up to iteration k differs from the optimum by at most ε.
universe u
open InnerProductSpace (toDualMap)
open Metric
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → EReal} {C XStar : Set E} {fOpt : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (h_bound : SubgradientNormBoundOn f C)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
theorem projected_subgradient_best_value_gap_le_epsilon_of_polyak_stepsize
(ε : ℝ) (k : ℕ) (hε : 0 < ε)
(h_subgrad :
∀ n,
toDualMap ℝ E (g n (x[n])) ∈ strongDualSubdifferential f (x[n] : E))
(h_polyak :
∀ n,
t n = polyak_stepsize f fOpt (x[n] : E) (g n (x[n])))
(hk :
h_bound.L_f ^ (2 : ℕ) * infDist (x0 : E) XStar ^ (2 : ℕ) / ε ^ (2 : ℕ) - 1 ≤ (k : ℝ)) :
best_achieved_function_value (fun x : E ↦ (f x).toReal) (fun n ↦ (x[n] : E)) k - fOpt ≤ εDefinition 8.19
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.19: the Lagrangian dual objective function q(λ) of min f(x) subject to g(x) ≤ 0 and x ∈ X is the existing owner lagrangian_dual_objective, which formalizes the textbook formula by sending λ to the infimum over X of the Lagrangian L(x; λ) = f(x) + λᵀ g(x).
recall lagrangian_dual_objectiveExample 8.19
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 8.19 (4): the example objective satisfies Assumption 8.7 on ℝ², with feasible set Set.univ, optimal set {0}, and optimal value 0.
open Matrix
open WithLp (toLp)
open scoped Matrix
local notation "E" => EuclideanSpace ℝ (Fin 2)
local notation "fE" => fun x : E ↦ (example_8_19_objective x : EReal)
-- Proof sketch: compute `example_8_19_matrix.toEuclideanLin x`, identify its two coordinates with
-- `x₁ + 2x₂` and `3x₁ + 4x₂`, and rewrite the `ℓ¹` norm on `ℝ²` as the sum of the absolute values
-- of those coordinates.
instance example_8_19_isConstrainedConvexProblem :
IsConstrainedConvexProblem fE Set.univ ({(0 : E)}) 0Definition 8.20
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.20: the feasible multiplier region of the dual problem is the nonnegative orthant ℝ_+^m. The dual problem maximizes the dual function q over this set.
universe u
variable {m : ℕ}
local notation "Λ" => EuclideanSpace ℝ (Fin m)
def dual_problem_feasible_set (m : ℕ) : Set (EuclideanSpace ℝ (Fin m)) :=
{lam | ∀ i : Fin m, 0 ≤ lam i}
-- Proof sketch: unfold `dual_problem_feasible_set`; membership is definitionally the
-- coordinatewise nonnegativity condition `∀ i, 0 ≤ λ i`.Lemma 8.20
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.20: for a finite nonempty family of sets, the function x ↦ max_i d_{S_i}(x) is globally Lipschitz continuous with constant 1; in particular this applies to the nonempty closed convex sets of the convex feasibility setting.
universe u v
open Metric
variable {α : Type u} [PseudoMetricSpace α]
variable {ι : Type v} [Finite ι] [Nonempty ι]
theorem lipschitzWith_max_distance_to_sets (S : ι → Set α) :
LipschitzWith 1 (max_distance_to_sets S)Theorem 8.20
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.20 (1): under Assumption 8.41, if qOpt is the optimal value of the dual problem max {q(λ) : λ ∈ ℝ_+^m}, then qOpt = fOpt.
universe u
variable {E : Type u} [AddCommMonoid E] [Module ℝ E]
variable {m : ℕ}
variable {X XStar : Set E} {f : E → ℝ} {g : Fin m → E → ℝ} {fOpt : ℝ}
local notation "Λ" => EuclideanSpace ℝ (Fin m)
local notation "Eq0" => EuclideanSpace ℝ (Fin 0)
local notation "q" => lagrangian_dual_objective X f (dual_constraint_vector g)
theorem dual_projected_subgradient_problem_strong_duality
(h_problem : IsDualProjectedSubgradientProblem X XStar f g fOpt)
{qOpt : EReal}
(hdual_value : IsLUB (q '' dual_problem_feasible_set m) qOpt) :
qOpt = (fOpt : EReal)Definition 8.21
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.21: the full averaging sequence uses the entire iterate history up to time k, forming x^(k) as the weighted average ∑_{n=0}^k μ_n^k x^n, where μ_n^k = (γ_n / ‖g(x^n)‖₂) / ∑_{j=0}^k γ_j / ‖g(x^j)‖₂.
universe u v
open scoped BigOperators
variable {E : Type u} {G : Type v}
variable [AddCommMonoid E] [Module ℝ E] [Norm G]
def full_averaging_sequence (x : ℕ → E) (γ : ℕ → ℝ) (g : ℕ → G) : ℕ → E :=
fun k ↦ ∑ n : Fin (k + 1), full_averaging_weight γ g k n • x n
-- Proof sketch: unfold `full_averaging_sequence`; evaluation at `k` is definitionally the finite
-- sum of the prefix iterates `x^0, …, x^k` with coefficients `full_averaging_weight γ g k n`.Theorem 8.21
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.21 (1): source part (a). For the greedy projection algorithm, the best value of the max-distance objective attained among the first k + 1 iterates is at most d_{⋂ i, S_i}(x^0) / √(k + 1).
universe u
open Metric
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ} [Nonempty (Fin m)]
variable {S : Fin m → Set E}
variable (hS_closed : ∀ i, IsClosed (S i)) (hS_convex : ∀ i, Convex ℝ (S i))
variable (hinter : (⋂ i, S i).Nonempty)
variable (i : ℕ → E → Fin m) (x0 : E)
local notation "hS_nonempty" => family_nonempty_of_iInter_nonempty hinter
local notation "x" =>
greedy_projection_method S hS_nonempty hS_closed hS_convex i x0
theorem greedy_projection_method_best_max_distance_le
(hgreedy : greedy_projection_method_is_admissible S hS_nonempty hS_closed hS_convex i x0)
(k : ℕ) :
best_achieved_function_value (convex_feasibility_max_distance S) x k ≤
infDist x0 (⋂ j, S j) / Real.sqrt (k + 1)Corollary 8.22
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Corollary 8.22 (1): among the first k + 1 iterates of the alternating projection method, there is an iterate whose distance to S₁ is at most d_{S₁ ∩ S₂}(x^0) / √(k + 1).
universe u
open scoped BigOperators
open Metric
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {S₁ S₂ : Set E}
variable (hS₁_closed : IsClosed S₁) (hS₁_convex : Convex ℝ S₁)
variable (hS₂_closed : IsClosed S₂) (hS₂_convex : Convex ℝ S₂)
variable (hinter : (S₁ ∩ S₂).Nonempty) (x0 : S₂)
local notation "x[" k "]" =>
alternating_projection_method S₁ S₂
(hinter.mono Set.inter_subset_left) hS₁_closed hS₁_convex
(hinter.mono Set.inter_subset_right) hS₂_closed hS₂_convex x0 k
theorem alternating_projection_exists_prefix_iterate_infDist_le (k : ℕ) :
∃ n ≤ k,
infDist (x[n] : E) S₁ ≤ infDist (x0 : E) (S₁ ∩ S₂) / Real.sqrt (k + 1)Definition 8.22
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.22: the partial averaging sequence uses only the iterate window x^([k/2]), x^([k/2] + 1), …, x^k, forming x^(k) = ∑_{n=[k/2]}^k η_n^k x^n with η_n^k = (γ_n / ‖g(x^n)‖₂) / ∑_{j=[k/2]}^k γ_j / ‖g(x^j)‖₂.
universe u v
open scoped BigOperators
variable {E : Type u} {G : Type v}
variable [AddCommMonoid E] [Module ℝ E] [Norm G]
def partial_averaging_sequence (x : ℕ → E) (γ : ℕ → ℝ) (g : ℕ → G) : ℕ → E :=
fun k ↦
Finset.sum (Finset.Icc (k / 2) k) fun n ↦ partial_averaging_weight γ g k n • x n
-- Proof sketch: unfold `partial_averaging_sequence`; evaluation at `k` is definitionally the
-- finite weighted sum of the iterates with indices in the suffix window `[k / 2, k]`.Definition 8.23
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.23: a vector x ∈ X is an ε-optimal and feasible solution of min f(x) subject to g(x) ≤ 0 and x ∈ X when it is ε-optimal in objective value and the Euclidean norm of the positive part of the constraint vector g x is at most ε.
universe u
open WithLp (toLp)
variable {E : Type u} {m : ℕ}
def is_epsilon_optimal_and_feasible_solution
(f : E → ℝ) (X : Set E) (g : E → Fin m → ℝ) (fOpt ε : ℝ) (x : E) : Prop :=
is_epsilon_optimal_point f X fOpt ε x ∧
positive_constraint_violation g x ≤ ε
-- Proof sketch: unfold `is_epsilon_optimal_and_feasible_solution`; this is definitionally the
-- conjunction of `ε`-optimality in objective value and the residual bound
-- `positive_constraint_violation g x ≤ ε`.Definition 8.24
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.24: the feasible set of the linear program (LP) consists of the vectors x ∈ Δ_n = stdSimplex ℝ (Fin n) satisfying the coordinatewise linear inequality A x ≤ b.
open Matrix
variable {m n : ℕ}
def simplex_linear_program_feasible_set
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) : Set (Fin n → ℝ) :=
{x | A *ᵥ x ≤ b ∧ x ∈ stdSimplex ℝ (Fin n)}
-- Proof sketch: unfold `simplex_linear_program_feasible_set`; membership is exactly the
-- conjunction of the coordinatewise inequality `A *ᵥ x ≤ b` and the simplex constraint
-- `x ∈ stdSimplex ℝ (Fin n)`.Lemma 8.24
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.24: under Assumption 8.7 and nonnegative stepsizes, the stepsize-weighted cumulative objective gap along the projected subgradient iterates up to step k is bounded by one half of the initial squared distance to an optimal point plus one half of the accumulated squared subgradient norms.
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable (f : E → EReal) (C XStar : Set E) (fOpt : ℝ)
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
local notation "x̄" =>
projected_subgradient_method_iterate C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
-- Proof sketch: strengthen the target inequality by keeping the nonnegative terminal term
-- Keep `(1 / 2) ‖x^{k+1} - xStar‖²` on the left. Induct on `k`, combining with the induction
-- the one-step inequality from Lemma 8.11 at index `k + 1`, and split the sums over
-- `Finset.range (k + 2)` using `Finset.sum_range_succ`.
theorem projected_subgradient_method_weighted_objective_gap_sum_le
(h_subgrad :
∀ k,
toDualMap ℝ E (g k (x[k])) ∈ ∂ₛf(x̄[k]))
(h_stepsize_nonneg : ∀ n, 0 ≤ t n)
{xStar : E} (hxStar : xStar ∈ XStar) (k : ℕ) :
Finset.sum (Finset.range (k + 1)) (fun n ↦ t n * ((f x̄[n]).toReal - fOpt)) ≤
(1 / 2 : ℝ) * ‖(x0 : E) - xStar‖ ^ 2 +
(1 / 2 : ℝ) *
Finset.sum (Finset.range (k + 1)) (fun n ↦ (t n) ^ 2 * ‖g n (x[n])‖ ^ 2)Definition 8.25
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 8.25: the feasible rate vectors for the network utility maximization problem (8.91) are those satisfying every link-capacity constraint ∑_{s ∈ S(ℓ)} x_s ≤ c_ℓ and every box constraint x_s ∈ [0, M_s].
open scoped BigOperators
universe u v
variable {Source : Type u} {Link : Type v}
variable [Fintype Source] [DecidableEq Link]
def network_utility_maximization_feasible_set
(linksUsedBySource : Source → Finset Link) (c : Link → ℝ) (M : Source → ℝ) :
Set (Source → ℝ) :=
{x |
(∀ ℓ : Link, network_link_load linksUsedBySource x ℓ ≤ c ℓ) ∧
∀ s : Source, x s ∈ Set.Icc 0 (M s)}
-- Proof sketch: unfold `network_utility_maximization_feasible_set`; membership is exactly the
-- conjunction of the link-capacity constraints and the interval constraints `x_s ∈ [0, M_s]`.Theorem 8.25
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.25: under Assumptions 8.7 and 8.12, if the projected subgradient method uses positive stepsizes and the ratio (∑_{n=0}^k t_n^2) / (∑_{n=0}^k t_n) tends to 0, then the best objective value achieved by the first k + 1 iterates has objective gap converging to 0.
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → EReal} {C XStar : Set E} {fOpt : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
local notation "x̄" =>
projected_subgradient_method_iterate C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
theorem projected_subgradient_method_best_value_gap_tendsto_zero_of_stepsize_ratio
(h_bound : SubgradientNormBoundOn f C)
(h_subgrad :
∀ n, toDualMap ℝ E (g n (x[n])) ∈ strongDualSubdifferential f x̄[n])
(h_stepsize_pos : ∀ n, 0 < t n)
(h_ratio :
Filter.Tendsto
(fun k ↦
(Finset.sum (Finset.range (k + 1)) fun n ↦ (t n) ^ (2 : ℕ)) /
Finset.sum (Finset.range (k + 1)) fun n ↦ t n)
Filter.atTop (nhds 0)) :
Filter.Tendsto
(fun k ↦
best_achieved_function_value (fun y ↦ (f y).toReal) x̄ k - fOpt)
Filter.atTop (nhds 0)Lemma 8.26
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.26: if f : [a - 1, b + 1] → ℝ is continuous and nonincreasing on the real interval with integer endpoints a - 1 and b + 1, then the sum of its values at the integers a, a + 1, …, b lies between the integrals over [a, b + 1] and [a - 1, b].
open scoped Interval
theorem sum_integer_samples_bounds_intervalIntegrals_of_antitoneOn
(f : ℝ → ℝ) (a b : ℤ) (hab : a ≤ b)
(h_cont : ContinuousOn f (Set.Icc (((a - 1 : ℤ) : ℝ)) (((b + 1 : ℤ) : ℝ))))
(h_anti : AntitoneOn f (Set.Icc (((a - 1 : ℤ) : ℝ)) (((b + 1 : ℤ) : ℝ)))) :
((∫ t in (a : ℝ)..(((b + 1 : ℤ) : ℝ)), f t) ≤
Finset.sum (Finset.Icc a b) (fun k ↦ f (k : ℝ))) ∧
(Finset.sum (Finset.Icc a b) (fun k ↦ f (k : ℝ)) ≤
∫ t in (((a - 1 : ℤ) : ℝ))..(b : ℝ), f t)Lemma 8.27
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.27 (2): for every nonnegative real D and every k, the ratio of the tail sums from ⌊k / 2⌋ to k is bounded by 4 (D + log 3) / √(k + 2) as in equation (8.31).
lemma harmonic_half_tail_ratio_le_log_three_bound
(D : ℝ) (hD : 0 ≤ D) (k : ℕ) :
(D + harmonicHalfTailSum k) / inverseSqrtHalfTailSum k ≤
(4 * (D + Real.log 3)) / Real.sqrt ((k : ℝ) + 2)Theorem 8.28
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.28: under Assumptions 8.7 and 8.12, if the projected subgradient method uses the dynamic stepsizes t_k = 1 / (‖f'(x^k)‖ √(k + 1)) when the chosen subgradient f'(x^k) is nonzero and t_k = 1 / L_f otherwise, then for every k ≥ 1 the larger of the best-value gap f_best^k - fOpt and the averaged-iterate gap f(x^(k)) - fOpt is bounded by (L_f / 2) (‖x^0 - xStar‖^2 + 1 + log(k + 1)) / √(k + 1).
universe u
open InnerProductSpace (toDualMap)
open scoped BigOperators
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → EReal} {C XStar : Set E} {fOpt : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (h_bound : SubgradientNormBoundOn f C)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
local notation "x̄" =>
projected_subgradient_method_iterate C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
open scoped ProjectedSubgradientErgodicNotation
local notation "T_" k => (T[t](k))
local notation "x^(" k ")" => x^[h_problem, g, t, x0](k)
theorem projected_subgradient_best_and_average_value_gap_le_of_dynamic_stepsize
(h_subgrad :
∀ n,
toDualMap ℝ E (g n (x[n])) ∈ strongDualSubdifferential f x̄[n])
(h_stepsize :
∀ n, t n = projectedSubgradientDynamicStepsize h_bound.L_f n (g n (x[n])))
{xStar : E} (hxStar : xStar ∈ XStar) {k : ℕ} (hk : 1 ≤ k) :
max
(best_achieved_function_value (fun x : E ↦ (f x).toReal) x̄ k - fOpt)
((f (x^(k))).toReal - fOpt) ≤
(h_bound.L_f / 2) *
(‖x0 - xStar‖ ^ (2 : ℕ) + 1 + Real.log ((k : ℝ) + 1)) /
Real.sqrt ((k : ℝ) + 1)Remark 8.29
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Remark 8.29: if the prefix sums T_k = ∑_{n=0}^k t_n and T_{k+1} are nonzero, then the weighted averages from Theorem 8.28 satisfy the recursion x^(k+1) = (T_k / T_{k+1}) x^(k) + (t_{k+1} / T_{k+1}) x̄[k+1], where x̄[k+1] is the canonical ambient projected iterate. In the dynamic-stepsize regime of Theorem 8.28, these nonvanishing prefix-sum hypotheses hold automatically.
universe u
open scoped ProjectedSubgradientErgodicNotation
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → EReal} {C XStar : Set E} {fOpt : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x̄" =>
projected_subgradient_method_iterate C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
local notation "T_" k => T[t](k)
local notation "x^(" k ")" => x^[h_problem, g, t, x0](k)
theorem projected_subgradient_stepsize_average_iterate_succ
(k : ℕ) (hTk : (T_ k) ≠ 0) (hTsucc : (T_(k + 1)) ≠ 0) :
x^(k + 1) = ((T_ k) / T_(k + 1)) • x^(k) +
(t (k + 1) / T_(k + 1)) • x̄[k + 1]Theorem 8.30
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.30: if Θ bounds the half squared diameter of the feasible set C, each chosen direction satisfies toDualMap ℝ E (g k (x[k])) ∈ ∂ₛf(x̄[k]), and the projected subgradient method uses either textbook half-squared-diameter stepsize rule, then for every k ≥ 2 the best objective gap is O(1 / √k) with the stated explicit constant.
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → EReal} {C XStar : Set E} {fOpt Θ : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (h_bound : SubgradientNormBoundOn f C)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
local notation "x̄" =>
projected_subgradient_method_iterate C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
theorem projected_subgradient_best_value_gap_le_of_half_squared_diameter_stepsizes
(h_subgrad :
∀ n,
toDualMap ℝ E (g n (x[n])) ∈ ∂ₛf(x̄[n]))
(hΘ : C.HasHalfSquaredDiameterBound Θ)
(h_stepsize :
projectedSubgradientUsesHalfSquaredDiameterStepsize Θ h_bound.L_f t ∨
projectedSubgradientUsesAdaptiveHalfSquaredDiameterStepsize Θ h_bound.L_f
(fun n ↦ g n (x[n])) t)
{k : ℕ} (hk : 2 ≤ k) :
best_achieved_function_value (fun x : E ↦ (f x).toReal) x̄ k - fOpt ≤
(2 * (1 + Real.log 3)) * h_bound.L_f * Real.sqrt (2 * Θ) /
Real.sqrt ((k : ℝ) + 2)Theorem 8.31
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.31 (1): source part (a). Under Assumptions 8.7 and 8.12, if f is σ-strongly convex with σ > 0 and the projected subgradient method uses the stepsizes t_k = 2 / (σ (k + 1)), then the best objective value attained among the first k + 1 iterates satisfies the O(1 / k) bound f_best^k - fOpt ≤ 2 L_f^2 / (σ (k + 1)).
universe u
open InnerProductSpace (toDualMap)
open scoped BigOperators
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → EReal} {C XStar : Set E} {fOpt σ : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (h_bound : SubgradientNormBoundOn f C)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
local notation "x̄" =>
projected_subgradient_method_iterate C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
open scoped ProjectedSubgradientErgodicNotation
-- Proof sketch: unfold `projected_subgradient_strongly_convex_average_weight`; the displayed
-- piecewise formula is exactly the defining equation.
local notation "x^(" k ")" =>
projected_subgradient_strongly_convex_average_iterate h_problem g t x0 k
-- Proof sketch: unfold `projected_subgradient_strongly_convex_average_iterate`; evaluation at
-- `k` is definitionally the finite weighted sum of the iterates `x^0, …, x^k`.
theorem projected_subgradient_best_value_gap_le_of_strongly_convex_stepsize
(h_strong : StrongConvexOn (effective_domain f) σ (fun x ↦ (f x).toReal))
(hσ : 0 < σ)
(h_subgrad :
∀ n, toDualMap ℝ E (g n (x[n])) ∈ strongDualSubdifferential f x̄[n])
(h_stepsize : ∀ n, t n = 2 / (σ * (n + 1 : ℝ)))
{xStar : E} (hxStar : xStar ∈ XStar) (k : ℕ) :
best_achieved_function_value (fun x : E ↦ (f x).toReal) x̄ k - fOpt ≤
2 * h_bound.L_f ^ (2 : ℕ) / (σ * (k + 1 : ℝ))Remark 8.32
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Remark 8.32: the weighted average iterates x^(k) from Theorem 8.31 satisfy the recursion x^(k + 1) = (k / (k + 2)) x^(k) + (2 / (k + 2)) x̄[k + 1], where x̄[k + 1] is the canonical ambient projected iterate.
universe u
open scoped ProjectedSubgradientErgodicNotation
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → EReal} {C XStar : Set E} {fOpt : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x̄" =>
projected_subgradient_method_iterate C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
local notation "x^(" k ")" =>
projected_subgradient_strongly_convex_average_iterate h_problem g t x0 k
theorem projected_subgradient_strongly_convex_average_iterate_succ (k : ℕ) :
x^(k + 1) = ((k : ℝ) / (k + 2 : ℝ)) • x^(k) +
((2 : ℝ) / (k + 2 : ℝ)) • x̄[k + 1]Theorem 8.33
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.33 (1): under the setting and assumptions of Theorem 8.31, every index k with 2 L_f^2 / (σ ε) - 1 ≤ k guarantees that the best objective value attained among the first k + 1 projected-subgradient iterates differs from the optimum by at most ε, provided σ > 0.
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → EReal} {C XStar : Set E} {fOpt σ : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (h_bound : SubgradientNormBoundOn f C)
variable (g : ℕ → C → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
local notation "x̄" =>
projected_subgradient_method_iterate C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
theorem projected_subgradient_best_value_gap_le_epsilon_of_strongly_convex_stepsize
(h_strong : StrongConvexOn (effective_domain f) σ (fun x ↦ (f x).toReal))
(hσ : 0 < σ) (ε : ℝ) (k : ℕ) (hε : 0 < ε)
(h_subgrad :
∀ n,
toDualMap ℝ E (g n (x[n])) ∈ strongDualSubdifferential f x̄[n])
(h_stepsize : ∀ n, t n = 2 / (σ * (n + 1 : ℝ)))
(hk : 2 * h_bound.L_f ^ (2 : ℕ) / (σ * ε) - 1 ≤ (k : ℝ)) :
best_achieved_function_value (fun x ↦ (f x).toReal) x̄ k - fOpt ≤ εAssumption 8.34
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Assumption 8.34: a stochastic projected subgradient oracle for f along the iterate sequence x^k and sampled directions g^k satisfies (A) unbiasedness, namely the conditional expectation of g^k given the sigma-algebra generated by x^k is almost surely a Euclidean subgradient of f at x^k, and (B) boundedness, namely there is a chosen constant L_tilde_f > 0 such that the conditional expectation of ‖g^k‖^2 given x^k is almost surely bounded above by L_tilde_f^2.
universe u v
open scoped ProbabilityTheory
open MeasureTheory
variable {Ω : Type v} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [MeasurableSpace E] [BorelSpace E]
structure StochasticProjectedSubgradientOracle
(μ : Measure Ω) (f : E → ℝ) (x : ℕ → Ω → E) (g : ℕ → Ω → E) where
integrable_subgradient (k : ℕ) : Integrable (g k) μ
integrable_sqnorm_subgradient (k : ℕ) :
Integrable (fun ω ↦ ‖g k ω‖ ^ (2 : ℕ)) μ
unbiased (k : ℕ) :
∀ᵐ ω ∂μ,
μ[g k | MeasurableSpace.comap (x k) inferInstance] ω ∈
euclideanSubdifferentialAt f (x k ω)
L_tilde_f : ℝ
L_tilde_f_pos : 0 < L_tilde_f
sqnorm_condexp_le (k : ℕ) :
∀ᵐ ω ∂μ,
μ[(fun ω ↦ ‖g k ω‖ ^ (2 : ℕ)) | MeasurableSpace.comap (x k) inferInstance] ω ≤
L_tilde_f ^ (2 : ℕ)Theorem 8.35
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.35 (1), gap form: under Assumptions 8.7 and 8.34, if the stochastic projected subgradient method uses positive stepsizes and (∑_{n=0}^k t_n^2) / (∑_{n=0}^k t_n) → 0, then the expected best objective gap attained by the first k + 1 stochastic iterates converges to 0.
universe u v
open MeasureTheory
open scoped BigOperators ProbabilityTheory
variable {E : Type u} {Ω : Type v}
variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]
variable [MeasurableSpace E] [BorelSpace E]
variable {f : E → ℝ} {C XStar : Set E} {fOpt Θ : ℝ}
variable (h_problem : IsConstrainedConvexProblem (fun x : E ↦ (f x : EReal)) C XStar fOpt)
variable (g : ℕ → C → Ω → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
stochastic_projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
local notation "x̄" =>
stochastic_projected_subgradient_method_iterate C h_problem.feasible_nonempty
h_problem.feasible_closed h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
theorem stochastic_projected_subgradient_expected_best_value_gap_tendsto_zero_of_stepsize_ratio
(h_stepsize_pos : stochastic_projected_subgradient_stepsizes_positive t)
(h_oracle :
StochasticProjectedSubgradientOracle μ f
(fun k ω ↦ (x[k] ω : E))
(fun k ω ↦ g k (x[k] ω) ω))
(h_ratio :
Filter.Tendsto
(fun k ↦
(Finset.sum (Finset.range (k + 1)) fun n ↦ (t n) ^ (2 : ℕ)) /
Finset.sum (Finset.range (k + 1)) fun n ↦ t n)
Filter.atTop (nhds 0)) :
Filter.Tendsto
(fun k ↦
μ[fun ω ↦
best_achieved_function_value f (fun n ↦ (x[n] ω : E)) k] - fOpt)
Filter.atTop (nhds 0)Example 8.36
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 8.36: if each summand f i is convex, the feasible set C lies in the interior of each effective domain, and every subgradient of f i on C has norm at most L i > 0, then the sum objective x ↦ ∑ i, f i x satisfies Assumption 8.12 with Lipschitz constant ∑ i, L i.
universe u
open Metric
open scoped BigOperators Pointwise Topology
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
theorem finset_sum_satisfies_subgradient_norm_bound
{m : ℕ} (hm : 0 < m) (f : Fin m → E → EReal) (C : Set E) (L : Fin m → ℝ)
(hfi_ne_bot : ∀ i : Fin m, ∀ x : E, f i x ≠ ⊥)
(hfi_convex : ∀ i : Fin m, is_convex_function (f i))
(hC_nonempty : C.Nonempty)
(hC_subset : ∀ i : Fin m, C ⊆ interior (effective_domain (f i)))
(hL_pos : ∀ i : Fin m, 0 < L i)
(hbound : ∀ i : Fin m, ∀ ⦃x : E⦄, ∀ ⦃g : StrongDual ℝ E⦄,
x ∈ C → g ∈ strongDualSubdifferential (f i) x → ‖g‖ ≤ L i) :
0 < ∑ i : Fin m, L i ∧
∀ ⦃x : E⦄, ∀ ⦃g : StrongDual ℝ E⦄,
x ∈ C →
g ∈ strongDualSubdifferential (fun y ↦ ∑ i : Fin m, f i y) x →
‖g‖ ≤ ∑ i : Fin m, L iTheorem 8.37
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.37: integrating the conditional one-step inequality first yields the stable expectation-level remainder estimate before the stepsize coefficients are normalized.
universe u v
open scoped BigOperators ProbabilityTheory ProjectedSubgradientErgodicNotation
open MeasureTheory
open InnerProductSpace (toDualMap)
variable {Ω : Type v}
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → EReal} {C XStar : Set E} {fOpt σ : ℝ}
variable (h_problem : IsConstrainedConvexProblem f C XStar fOpt)
variable (g : ℕ → C → Ω → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
stochastic_projected_subgradient_method C h_problem.feasible_nonempty h_problem.feasible_closed
h_problem.feasible_convex g t x0 k
local notation "x̄" =>
stochastic_projected_subgradient_method_iterate C h_problem.feasible_nonempty
h_problem.feasible_closed h_problem.feasible_convex g t x0
local notation "x̄[" k "]" => x̄ k
local notation "x^(" k ")" =>
stochastic_projected_subgradient_strongly_convex_average_iterate h_problem g t x0 k
variable [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]
variable [MeasurableSpace E] [BorelSpace E]
lemma expectedGapStepWithStrongRemainder_le
(h_strong : StrongConvexOn (effective_domain f) σ (fun x ↦ (f x).toReal))
(hσ : 0 < σ)
(h_stepsize : ∀ n, t n = 2 / (σ * (n + 1 : ℝ)))
(h_iterate_meas : ∀ n, Measurable (x̄[n]))
(h_oracle :
StochasticProjectedSubgradientOracle μ (fun x ↦ (f x).toReal)
x̄ (fun n ω ↦ g n (x[n] ω) ω))
{xStar : E} (hxStar : xStar ∈ XStar) (n : ℕ) :
2 * t n * (μ[fun ω ↦ (f (x̄[n] ω)).toReal] - fOpt) +
σ * t n * μ[fun ω ↦ ‖x̄[n] ω - xStar‖ ^ (2 : ℕ)] +
μ[fun ω ↦ ‖x̄[n + 1] ω - xStar‖ ^ (2 : ℕ)] ≤
μ[fun ω ↦ ‖x̄[n] ω - xStar‖ ^ (2 : ℕ)] +
(t n) ^ (2 : ℕ) * h_oracle.L_tilde_f ^ (2 : ℕ)Assumption 8.38
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Assumption 8.38: a finite family of component functions f i, indexed by i = 1, …, m, admits a common constant L > 0 such that (a) each f i is proper, closed, and convex, and (b) every continuous-dual subgradient of every f i at every point of C has norm at most L.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
structure IncrementalProjectedSubgradientAssumptions {m : ℕ}
(f : Fin m → E → EReal) (C : Set E) where
L : ℝ
L_pos : 0 < L
proper (i : Fin m) : IsProperExtendedRealFunction (f i)
closed (i : Fin m) : LowerSemicontinuous (f i)
convex (i : Fin m) : is_convex_function (f i)
norm_le {i : Fin m} {x : E} {g : StrongDual ℝ E}
(hx : x ∈ C) (hg : g ∈ strongDualSubdifferential (f i) x) : ‖g‖ ≤ LLemma 8.39
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.39: under Assumptions 8.7 and 8.38, every outer step of the incremental projected subgradient method with positive stepsizes satisfies the fundamental inequality ‖x^{k+1} - xStar‖^2 ≤ ‖x^k - xStar‖^2 - 2 t_k (f(x^k) - fOpt) + t_k^2 m^2 L^2 for each optimal point xStar ∈ XStar, where f = ∑ i, f_i and L = h_incremental.L.
universe u
open InnerProductSpace (toDualMap)
open scoped BigOperators
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ}
variable {fi : Fin m → E → EReal} {C XStar : Set E} {fOpt : ℝ}
variable [h_problem : IsConstrainedConvexProblem (finite_sum_objective fi) C XStar fOpt]
variable (h_incremental : IncrementalProjectedSubgradientAssumptions fi C)
variable (g : ℕ → C → Fin m → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
incremental_projected_subgradient_method
C h_problem.feasible_nonempty h_problem.feasible_closed h_problem.feasible_convex t g x0 k
local notation "x[" k "," i "]" =>
incremental_projected_subgradient_inner_iterate
C h_problem.feasible_nonempty h_problem.feasible_closed h_problem.feasible_convex t g k x[k] i
include h_problem h_incremental
variable [FiniteDimensional ℝ E]
theorem incremental_projected_subgradient_method_fundamental_inequality
(h_subgrad :
∀ k (i : Fin m),
toDualMap ℝ E (g k x[k,i] i) ∈ strongDualSubdifferential (fi i) x[k,i])
(h_stepsize_pos : ∀ n, 0 < t n)
{xStar : E} (hxStar : xStar ∈ XStar) (k : ℕ) :
‖x[k + 1] - xStar‖ ^ (2 : ℕ) ≤
‖x[k] - xStar‖ ^ (2 : ℕ) -
2 * t k * ((finite_sum_objective fi x[k]).toReal - fOpt) +
(t k) ^ (2 : ℕ) * (m : ℝ) ^ (2 : ℕ) * h_incremental.L ^ (2 : ℕ)Theorem 8.40
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.40 (1): clause (a). Under Assumptions 8.7 and 8.38, if the incremental projected subgradient method uses positive stepsizes and the ratio (∑_{n=0}^k t_n^2) / (∑_{n=0}^k t_n) tends to 0, then the best objective value attained by the first k + 1 iterates converges to the optimal value fOpt.
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {m : ℕ}
variable {fi : Fin m → E → EReal} {C XStar : Set E} {fOpt Θ : ℝ}
variable [h_problem : IsConstrainedConvexProblem (finite_sum_objective fi) C XStar fOpt]
variable (h_incremental : IncrementalProjectedSubgradientAssumptions fi C)
variable (g : ℕ → C → Fin m → E) (t : ℕ → ℝ) (x0 : C)
local notation "x[" k "]" =>
incremental_projected_subgradient_method
C h_problem.feasible_nonempty h_problem.feasible_closed h_problem.feasible_convex t g x0 k
local notation "x[" k "," i "]" =>
incremental_projected_subgradient_inner_iterate
C h_problem.feasible_nonempty h_problem.feasible_closed h_problem.feasible_convex t g k x[k] i
include h_problem h_incremental
theorem incremental_projected_subgradient_best_value_tendsto_of_stepsize_ratio
(h_subgrad :
∀ k (i : Fin m),
toDualMap ℝ E (g k x[k,i] i) ∈ strongDualSubdifferential (fi i) x[k,i])
(h_stepsize_pos : ∀ n, 0 < t n)
(h_ratio :
Filter.Tendsto
(fun k ↦
(Finset.sum (Finset.range (k + 1)) fun n ↦ (t n) ^ (2 : ℕ)) /
Finset.sum (Finset.range (k + 1)) fun n ↦ t n)
Filter.atTop (nhds 0)) :
Filter.Tendsto
(fun k ↦
best_achieved_function_value
(fun y : E ↦ ((finite_sum_objective fi) y).toReal)
(fun n ↦ x[n]) k)
Filter.atTop (nhds fOpt)Assumption 8.41
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Assumption 8.41: clauses (A)-(F) hold for the convex inequality-constrained problem over X, namely X is convex, f and each g i are convex, XStar is the nonempty optimal set with finite optimal value fOpt, there is a strict feasible point in X, and every nonnegative-multiplier Lagrangian minimization over X attains a minimizer.
open scoped BigOperators
universe u
variable {E : Type u} [AddCommMonoid E] [Module ℝ E]
class IsDualProjectedSubgradientProblem {m : ℕ}
(X XStar : Set E) (f : E → ℝ) (g : Fin m → E → ℝ) (fOpt : ℝ) : Prop where
feasible_convex : Convex ℝ X
objective_convex : ConvexOn ℝ Set.univ f
constraint_convex (i : Fin m) : ConvexOn ℝ Set.univ (g i)
optimal_set_eq :
XStar = {x | IsMinOn f (dual_projected_subgradient_feasible_set X g) x}
optimal_set_nonempty : XStar.Nonempty
optimal_value_isGLB :
IsGLB (f '' dual_projected_subgradient_feasible_set X g) fOpt
slater_condition_on_X :
∃ x ∈ X, ∀ i : Fin m, g i x < 0
lagrangian_has_minimizer (lam : Fin m → NNReal) :
∃ x, IsMinOn (dual_projected_subgradient_lagrangian f g lam) X xTheorem 8.42
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.42: if xBar ∈ X is a strict feasible point, as supplied by Assumption 8.41(E), then every multiplier λ in the superlevel set S_μ of the dual objective satisfies the Euclidean-norm bound ‖λ‖ ≤ (f(xBar) - μ) / min_i {-g_i(xBar)}.
open scoped BigOperators
universe u
variable {E : Type u} {m : ℕ}
local notation "Λ" => EuclideanSpace ℝ (Fin m)
theorem norm_le_div_strict_feasibility_margin_of_mem_dual_objective_superlevel_set
[NeZero m]
(X : Set E) (f : E → ℝ) (g : Fin m → E → ℝ) (μ : ℝ) (xBar : E) (lam : Λ)
(hxBar : xBar ∈ X)
(hgBar : ∀ i : Fin m, g i xBar < 0)
(hLam : lam ∈ dual_objective_superlevel_set X f g μ) :
‖lam‖ ≤ (f xBar - μ) / strict_feasibility_margin g xBarCorollary 8.43
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Corollary 8.43: under Assumption 8.41, every optimal multiplier λ of the dual problem max {q(λ) : λ ∈ ℝ_+^m} satisfies the bound ‖λ‖ ≤ (f(xBar) - fOpt) / min_i {-g_i(xBar)} for any strict feasible point xBar ∈ X.
universe u
variable {E : Type u} [AddCommMonoid E] [Module ℝ E]
variable {m : ℕ} [NeZero m]
variable {X XStar : Set E} {f : E → ℝ} {g : Fin m → E → ℝ} {fOpt : ℝ}
local notation "Λ" => EuclideanSpace ℝ (Fin m)
local notation "q" => lagrangian_dual_objective X f (dual_constraint_vector g)
theorem norm_le_div_strict_feasibility_margin_of_dual_optimal_multiplier
(h_problem : IsDualProjectedSubgradientProblem X XStar f g fOpt)
{xBar : E} (hxBar : xBar ∈ X) (hgBar : ∀ i : Fin m, g i xBar < 0)
{lam : Λ}
(hLam : lam ∈ dual_problem_feasible_set m ∧ IsMaxOn q (dual_problem_feasible_set m) lam) :
‖lam‖ ≤ (f xBar - fOpt) / strict_feasibility_margin g xBarLemma 8.44
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.44: if xBar minimizes the Lagrangian f(x) + λ̄ᵀ g(x) over X for some nonnegative multiplier vector λ̄ and satisfies g(xBar) = 0, then xBar is feasible for the primal problem and minimizes f on the feasible set {x ∈ X | g_i(x) ≤ 0}.
open scoped BigOperators
universe u
variable {E : Type u} [AddCommMonoid E] [Module ℝ E]
variable {m : ℕ}
theorem primal_optimality_of_lagrangian_isMinOn_of_constraint_eq_zero
{X : Set E} {f : E → ℝ} {g : Fin m → E → ℝ} {lamBar : Fin m → NNReal} {xBar : E}
(hxBar : xBar ∈ X)
(hmin : IsMinOn (dual_projected_subgradient_lagrangian f g lamBar) X xBar)
(hzero : ∀ i : Fin m, g i xBar = 0) :
xBar ∈ dual_projected_subgradient_feasible_set X g ∧
IsMinOn f (dual_projected_subgradient_feasible_set X g) xBarLemma 8.45
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.45 (8.70): under Assumption 8.41, if the constraint vectors satisfy ‖g(x)‖₂ ≤ L on X, then for every k ≥ 2 the full-history averaged iterate generated by the dual projected subgradient method satisfies the source-faithful objective-plus-positive-constraint-violation bound (8.70).
universe u
open scoped BigOperators
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {m : ℕ}
local notation "Λ" => EuclideanSpace ℝ (Fin m)
variable {X XStar : Set E} {f : E → ℝ} {g : Fin m → E → ℝ} {fOpt L ρ : ℝ}
variable (xSel : (Fin m → NNReal) → {x // x ∈ X}) (γ : ℕ → ℝ) (lam0 : Fin m → NNReal)
local notation "lamSeq" =>
dual_projected_subgradient_method X g xSel γ lam0
local notation "xSeq" =>
dual_projected_subgradient_primal_iterate X g xSel γ lam0
local notation "constraintSeq" =>
fun n ↦ dual_projected_subgradient_constraint_vector g (xSeq n : E)
local notation "lamVecSeq" =>
fun n ↦ dual_projected_subgradient_multiplier_vector (lamSeq n)
local notation "gVec" => fun x i ↦ g i x
local notation "fullAvg" =>
dual_projected_subgradient_full_average_iterate (X := X) (g := g) xSel γ lam0
local notation "partialAvg" =>
dual_projected_subgradient_partial_average_iterate (X := X) (g := g) xSel γ lam0
theorem dual_projected_subgradient_full_average_gap_le
(h_problem : IsDualProjectedSubgradientProblem X XStar f g fOpt)
(h_admissible : dual_projected_subgradient_method_is_admissible X f g xSel γ)
(h_constraint_bound :
∀ x ∈ X, ‖dual_projected_subgradient_constraint_vector g x‖ ≤ L)
(hρ : 0 < ρ) {k : ℕ} (hk : 2 ≤ k) :
f (fullAvg k) - fOpt +
ρ * positive_constraint_violation gVec (fullAvg k) ≤
(L / 2) *
((‖dual_projected_subgradient_multiplier_vector lam0‖ + ρ) ^ (2 : ℕ) +
Finset.sum (Finset.range (k + 1)) fun n ↦ (γ n) ^ (2 : ℕ)) /
Finset.sum (Finset.range (k + 1)) γTheorem 8.46
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.46: under Assumption 8.41, if ‖g x‖ ≤ L on X and xBar is a strict feasible point, then the full-history averaged iterate generated by the dual projected subgradient method with stepsizes γ_k = 1 / √(k + 1) satisfies the O(log(k) / √k) bound on the maximum of the objective gap and the Slater-scaled positive-part constraint violation.
universe u
open scoped BigOperators
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {m : ℕ} [NeZero m]
variable {X XStar : Set E} {f : E → ℝ} {g : Fin m → E → ℝ} {fOpt L : ℝ}
variable (xSel : (Fin m → NNReal) → {x // x ∈ X}) (lam0 : Fin m → NNReal)
local notation "Λ" => EuclideanSpace ℝ (Fin m)
local notation "γ" => fun n : ℕ ↦ (1 : ℝ) / Real.sqrt ((n : ℝ) + 1)
local notation "xSeq" =>
dual_projected_subgradient_primal_iterate X g xSel γ lam0
local notation "constraintSeq" =>
fun n ↦ dual_projected_subgradient_constraint_vector g (xSeq n : E)
local notation "fullAvg" =>
dual_projected_subgradient_full_average_iterate (X := X) (g := g) xSel γ lam0
local notation "gVec" => fun x i ↦ g i x
theorem dual_projected_subgradient_full_average_rate_max_le_log_over_sqrt
(h_problem : IsDualProjectedSubgradientProblem X XStar f g fOpt)
(h_admissible :
dual_projected_subgradient_method_is_admissible X f g xSel γ)
(h_constraint_bound :
∀ x ∈ X, ‖dual_projected_subgradient_constraint_vector g x‖ ≤ L)
{xBar : E} (hxBar : xBar ∈ X) (hgBar : ∀ i : Fin m, g i xBar < 0)
{k : ℕ} (hk : 1 ≤ k) :
let α := (f xBar - fOpt) / strict_feasibility_margin g xBar
let rhs :=
(L / 2) *
((‖dual_projected_subgradient_multiplier_vector lam0‖ + 2 * α) ^ (2 : ℕ) +
1 + Real.log ((k : ℝ) + 1)) /
Real.sqrt ((k : ℝ) + 1)
max
(f (fullAvg k) - fOpt)
(α * positive_constraint_violation gVec (fullAvg k)) ≤
rhsLemma 8.47
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 8.47: under Assumption 8.41, if ‖g(x)‖₂ ≤ L on X and the dual projected subgradient method uses positive stepsizes bounded above by γ₀, then every multiplier iterate λ^k satisfies the uniform bound ‖λ^k‖₂ ≤ M, where M is the maximum in formula (8.83) built from the Slater margin at xBar, the primal optimal value fOpt, the dual optimal value qOpt, and the initial multiplier λ^0.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {m : ℕ} [NeZero m]
variable {X XStar : Set E} {f : E → ℝ} {g : Fin m → E → ℝ}
variable {fOpt qOpt L γ₀ : ℝ}
variable (xSel : (Fin m → NNReal) → {x // x ∈ X}) (γ : ℕ → ℝ) (lam0 : Fin m → NNReal)
local notation "Λ" => EuclideanSpace ℝ (Fin m)
local notation "q" => lagrangian_dual_objective X f (dual_constraint_vector g)
local notation "lamSeq" => dual_projected_subgradient_method X g xSel γ lam0
local notation "lamVecSeq" =>
fun n ↦ dual_projected_subgradient_multiplier_vector (lamSeq n)
local notation "xSeq" =>
dual_projected_subgradient_primal_iterate X g xSel γ lam0
local notation "constraintSeq" =>
fun n ↦ dual_projected_subgradient_constraint_vector g (xSeq n : E)
theorem dual_projected_subgradient_multiplier_norm_le_uniform_bound
(h_problem : IsDualProjectedSubgradientProblem X XStar f g fOpt)
(h_admissible : dual_projected_subgradient_method_is_admissible X f g xSel γ)
(h_constraint_bound :
∀ x ∈ X, ‖dual_projected_subgradient_constraint_vector g x‖ ≤ L)
(h_stepsize_le : ∀ k : ℕ, γ k ≤ γ₀)
(hdual_value : IsLUB (q '' dual_problem_feasible_set m) (qOpt : EReal))
{xBar : E} (hxBar : xBar ∈ X) (hgBar : ∀ i : Fin m, g i xBar < 0)
(k : ℕ) :
‖lamVecSeq k‖ ≤
dual_projected_subgradient_multiplier_norm_bound f fOpt qOpt g xBar L γ₀ lam0Theorem 8.48
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 8.48: for the partial averaging iterate generated by the dual projected subgradient method with stepsizes γ_k = 1 / √(k + 1), both the objective gap and the scaled constraint violation decay at rate O(1 / √k); equivalently, the maximum of f(x^(k)) - fOpt and α * positive_constraint_violation g (x^(k)) is bounded by the explicit constant built from the source quantities M and α.
universe u
open scoped BigOperators
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {m : ℕ} [NeZero m]
variable {X XStar : Set E} {f : E → ℝ} {g : Fin m → E → ℝ}
variable {fOpt qOpt L : ℝ}
variable (xSel : (Fin m → NNReal) → {x // x ∈ X}) (lam0 : Fin m → NNReal)
variable {xBar : E}
local notation "Λ" => EuclideanSpace ℝ (Fin m)
local notation "γ" => fun n : ℕ ↦ 1 / Real.sqrt ((n : ℝ) + 1)
local notation "q" => lagrangian_dual_objective X f (dual_constraint_vector g)
local notation "α" => (f xBar - fOpt) / strict_feasibility_margin g xBar
local notation "M" =>
dual_projected_subgradient_multiplier_norm_bound f fOpt qOpt g xBar L 1 lam0
local notation "C" =>
dual_projected_subgradient_partial_average_rate_constant f fOpt qOpt g xBar L lam0
local notation "lamSeq" => dual_projected_subgradient_method X g xSel γ lam0
local notation "xSeq" => dual_projected_subgradient_primal_iterate X g xSel γ lam0
local notation "constraintSeq" =>
fun n ↦ dual_projected_subgradient_constraint_vector g (xSeq n : E)
local notation "partialAvg" =>
dual_projected_subgradient_partial_average_iterate (X := X) (g := g) xSel γ lam0
local notation "gVec" => fun y i ↦ g i y
theorem dual_projected_subgradient_partial_average_rate_max_le
(h_problem : IsDualProjectedSubgradientProblem X XStar f g fOpt)
(h_admissible : dual_projected_subgradient_method_is_admissible X f g xSel γ)
(h_constraint_bound :
∀ x ∈ X, ‖dual_projected_subgradient_constraint_vector g x‖ ≤ L)
(hdual_value : IsLUB (q '' dual_problem_feasible_set m) (qOpt : EReal))
(hxBar : xBar ∈ X) (hgBar : ∀ i : Fin m, g i xBar < 0)
{k : ℕ} (hk : 2 ≤ k) :
max
(f (partialAvg k) - fOpt)
(α * positive_constraint_violation (fun y i ↦ g i y) (partialAvg k)) ≤
C / Real.sqrt ((k : ℝ) + 2)Corollary 8.49
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Corollary 8.49: under the hypotheses of Theorem 8.48, if k ≥ 2 satisfies the displayed O(1 / ε^2) iteration bound, then the partial averaging iterate x^(k) is an ε-optimal and feasible solution in the sense of Definition 8.23.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable {m : ℕ} [NeZero m]
variable {X XStar : Set E} {f : E → ℝ} {g : Fin m → E → ℝ}
variable {fOpt qOpt L ε : ℝ}
variable (xSel : (Fin m → NNReal) → {x // x ∈ X}) (lam0 : Fin m → NNReal)
variable {xBar : E}
local notation "γ" => fun n : ℕ ↦ 1 / Real.sqrt ((n : ℝ) + 1)
local notation "q" => lagrangian_dual_objective X f (dual_constraint_vector g)
local notation "α" => (f xBar - fOpt) / strict_feasibility_margin g xBar
local notation "C" =>
dual_projected_subgradient_partial_average_rate_constant f fOpt qOpt g xBar L lam0
local notation "xSeq" => dual_projected_subgradient_primal_iterate X g xSel γ lam0
local notation "constraintSeq" =>
fun n ↦ dual_projected_subgradient_constraint_vector g (xSeq n : E)
local notation "partialAvg" =>
dual_projected_subgradient_partial_average_iterate (X := X) (g := g) xSel γ lam0
local notation "gVec" => fun x i ↦ g i x
theorem dual_projected_subgradient_partial_average_is_epsilon_optimal_and_feasible_solution
(h_problem : IsDualProjectedSubgradientProblem X XStar f g fOpt)
(h_admissible : dual_projected_subgradient_method_is_admissible X f g xSel γ)
(h_constraint_bound :
∀ x ∈ X, ‖dual_projected_subgradient_constraint_vector g x‖ ≤ L)
(hdual_value : IsLUB (q '' dual_problem_feasible_set m) (qOpt : EReal))
(hxBar : xBar ∈ X) (hgBar : ∀ i : Fin m, g i xBar < 0)
(hε : 0 < ε)
(hα : 0 < α)
{k : ℕ} (hk : 2 ≤ k)
(hk_complexity :
C ^ (2 : ℕ) / (min (α ^ (2 : ℕ)) 1 * ε ^ (2 : ℕ)) - 2 ≤ (k : ℝ)) :
is_epsilon_optimal_and_feasible_solution f X gVec fOpt ε (partialAvg k)Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
DualConstraintVector.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
HalfSquaredDiameterBound.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.