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.

Source header · Attribution source

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) : ℕ → E

Definition 8.1

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 ℝ E

Proposition 8.1

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 i

Theorem 8.1

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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) C

Algorithm 8.2

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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) : ℕ → E

Definition 8.2

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 x

Algorithm 8.3

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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) : ℕ → C

Definition 8.3

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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) : ℕ → E

Lemma 8.6

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.1

Proposition 8.7

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 f

Algorithm 8.9

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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) : ℕ → E

Proposition 8.9

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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) m

Algorithm 8.10

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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) : ℕ → Ω → C

Definition 8.10

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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) : ℕ → C

Lemma 8.11

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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])‖ ^ 2

Proposition 8.11

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 strongDualSubdifferential

Algorithm 8.12

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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) x0

Assumption 8.12

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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_f

Definition 8.12

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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) : ℕ → C

Definition 8.13

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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‖ ^ 2

Algorithm 8.14

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 → NNReal

Algorithm 8.15

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 → NNReal

Definition 8.15

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 → NNReal

Definition 8.16

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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_objective

Example 8.19

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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)}) 0

Definition 8.20

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 i

Theorem 8.37

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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‖ ≤ L

Lemma 8.39

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 x

Theorem 8.42

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 xBar

Corollary 8.43

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 xBar

Lemma 8.44

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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) xBar

Lemma 8.45

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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)) ≤ rhs

Lemma 8.47

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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 γ₀ lam0

Theorem 8.48

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.

Source header · Attribution source