Chapter 03 — Subgradients

Proofs omitted. Hover over highlighted terms to see their Lean types.

Definition 3.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 3.1: a vector g ∈ E* = Module.Dual ℝ E is a subgradient of f : E → EReal at x when x lies in the effective domain of f and the subgradient inequality f y ≥ f x + g (y - x) holds for every y.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] def is_subgradient_at (f : E → EReal) (x : E) (g : Module.Dual ℝ E) : Prop := x ∈ effective_domain f ∧ ∀ y : E, f y ≥ f x + (g (y - x) : EReal) -- Proof sketch: one implication is immediate by restriction. For the converse, if `y` is outside -- the effective domain then `¬ f y < ⊤`, hence `⊤ ≤ f y`; together with `f y ≤ ⊤` this gives -- `f y = ⊤`, so the inequality is automatic there.

Lemma 3.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

Lemma 3.1 is a bridge/view item in the chapter convex-analysis API: the owner theorem is is_convex_function_of_subdifferentiable_on_convex_effective_domain, whose owner hypothesis is the inclusion effective_domain f ⊆ subdifferential_domain f. This file keeps the source wording "there exists a subgradient" and rewrites it through the owner set subdifferential f x, equivalently membership in the owner domain subdifferential_domain f.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] {f : E → EReal} recall effective_domain

Proposition 3.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 3.1: the subdifferential of the norm at the origin is the closed unit ball of the dual norm on E*.

universe u open Metric variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] theorem strongDualSubdifferential_norm_zero_eq_closedBall : ∂ₛ(fun x : E ↦ (‖x‖ : EReal))((0 : E)) = closedBall (0 : StrongDual ℝ E) 1

Theorem 3.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 3.1 is a bridge/view item in the chapter subdifferential API. The owner declaration is subdifferential : Set (Module.Dual ℝ E) from Definition 3.2, while the closedness statement in this theorem lives on the topologized continuous-dual view. Owner-level convexity already lives in convex_subdifferential, so the only primitive data here is the canonical preimage of subdifferential along StrongDual ℝ E → Module.Dual ℝ E; membership lemmas are derived API.

universe u open Bornology variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] recall subdifferential

Definition 3.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 3.2: the subdifferential ∂ f(x) is the set of dual vectors g ∈ E* such that g is a subgradient of f at x in the sense of Definition 3.1. Consequently, when x ∉ dom(f), this set is empty by definition.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] def subdifferential (f : E → EReal) (x : E) : Set (Module.Dual ℝ E) := is_subgradient_at f x

Lemma 3.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 3.2 is a source-facing consequence in the chapter directional-derivative API. The owner objects are the Chapter 3 directional-derivative declarations has_directional_derivative_at/directional_derivative together with the Chapter 2 owners effective_domain, finite_domain, and is_convex_function. Unlike Theorem 3.11, this lemma does not assume an inner-product or finite-dimensional structure, so its main statement should remain a direct affine lower bound rather than being collapsed into a subdifferential-max formula. The reusable owner-side qualification in Chapter 3 is x ∈ interior (finite_domain f); the textbook h_ne_bot plus x ∈ interior (effective_domain f) formulation is kept below as a thin source-facing bridge.

universe u open Filter open scoped Topology variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] recall effective_domain

Proposition 3.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

Proposition 3.2: the subdifferential of the indicator function δ_S coincides with the normal cone of S at every point. In this bridge formulation, the textbook nonemptiness hypothesis on S is redundant because both sides are empty outside S.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] -- Proof sketch: unfold `subdifferential`, `extendedIndicator`, and `normal_cone`. If `x ∈ S`, then -- `extendedIndicator S x = 0`, and the subgradient inequality is equivalent to -- `g (z - x) ≤ 0` for every `z ∈ S`. If `x ∉ S`, then `x ∉ effective_domain (extendedIndicator S)`, -- so `subdifferential (extendedIndicator S) x = ∅`, and `normal_cone S x` is also empty by -- definition. theorem subdifferential_extended_indicator_eq_normal_cone (S : Set E) (x : E) : subdifferential (extendedIndicator S) x = normal_cone S x

Theorem 3.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

Theorem 3.2: supporting hyperplane theorem. A nonempty convex set and a point outside its interior admit a nonzero continuous linear functional whose value on the set is bounded above by its value at the point.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] theorem supporting_hyperplane_of_not_mem_interior {C : Set E} {y : E} (hC_nonempty : C.Nonempty) (hC_convex : Convex ℝ C) (hy : y ∉ interior C) : ∃ p : StrongDual ℝ E, p ≠ 0 ∧ ∀ x ∈ C, p x ≤ p y

Lemma 3.2.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

Lemma 3.2.1 is source-facing in the chapter directional-derivative API. The ambient owner objects already live upstream: directional_derivative from Chapter 3 and is_convex_function, together with its canonical source bridge is_convex_function_iff_segment_ineq, from Chapter 2. Under the present NormedSpace hypotheses the project has no stronger owner abstraction bundling convexity and positive homogeneity of directional_derivative f x, so the public API stays with these two atomic owner-level consequences instead of introducing a parallel wrapper. The primitive local hypothesis is the chapter owner x ∈ interior (finite_domain f), from which nearby finiteness is derived as needed; the earlier split effective_domain/≠ ⊥ assumptions are therefore not kept as public data.

universe u open Filter open scoped Topology variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable (f : E → EReal) (x : E) recall directional_derivative

Definition 3.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 3.3: the normal cone of a set S ⊆ E at x consists of the dual vectors that are nonpositive on every displacement z - x with z ∈ S; when x ∉ S, the normal cone is empty. This source-facing cone is the Chapter 2 owner polar_cone of the translated set S -ᵥ {x}.

universe u open scoped Pointwise variable {E : Type u} [AddCommGroup E] [Module ℝ E] def normal_cone (S : Set E) (x : E) : Set (Module.Dual ℝ E) := { y | x ∈ S ∧ y ∈ polar_cone (S -ᵥ ({x} : Set E)) }

Lemma 3.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

Lemma 3.3 is a bridge/view item in the perturbation-value-function API. The owner declarations are value_function and the derived antitonicity theorem value_function_antitone_u from Lemma_3_4, specialized to E = EuclideanSpace ℝ (Fin n) and to the matrix linear map A.toEuclideanLin. The source writes the affine constraint as A *ᵥ x = b + t, while the owner uses A x + c = t, so the faithful specialization here is obtained by taking c = -b.

open Matrix variable {m n p : ℕ} local notation "PrimalSpace" => EuclideanSpace ℝ (Fin n) local notation "IneqPerturbationSpace" => EuclideanSpace ℝ (Fin m) local notation "EqPerturbationSpace" => EuclideanSpace ℝ (Fin p) recall value_function

Proposition 3.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

Proposition 3.3: the subdifferential of the indicator of the closed unit ball is its normal cone.

universe u open Metric variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] -- Proof sketch: this is the closed-unit-ball specialization of the owner theorem -- `subdifferential_extended_indicator_eq_normal_cone`. theorem subdifferential_extended_indicator_closed_unit_ball_eq_normal_cone (x : E) : subdifferential (extendedIndicator (closedBall (0 : E) 1)) x = normal_cone (closedBall (0 : E) 1) x

Theorem 3.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

Theorem 3.3 is source-facing at the chapter owner subdifferential : Set (Module.Dual ℝ E). Its boundedness conclusion lives naturally on the normed continuous-dual view, so the file reuses the existing bridge strongDualSubdifferential instead of introducing a second StrongDual-valued owner. Domain sampling shows that the stronger chapter existence theorem is subdifferential_nonempty_at_relativeInterior_point; part (1) below is only its finite-dimensional interior specialization, while part (2) stays on the same owner/bridge surface.

universe u open Bornology variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] recall effective_domain

Definition 3.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 3.4: the Lagrangian dual objective function of the constrained problem min {f x : g x ≤ 0, x ∈ X}. It is the infimum of the Lagrangian over X; the coordinatewise nonnegativity restriction on multipliers is imposed separately in the dual-domain layer.

universe u variable {E : Type u} {m : ℕ} variable (X : Set E) (f : E → ℝ) (g : E → EuclideanSpace ℝ (Fin m)) local notation "MultiplierSpace" => EuclideanSpace ℝ (Fin m) def lagrangian_dual_objective (multiplier : MultiplierSpace) : EReal := sInf ((fun x : E ↦ (lagrangian f g multiplier x : EReal)) '' X) -- Proof sketch: unfold `lagrangian_dual_objective`; the statement is exactly its defining -- infimum formula.

Lemma 3.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 3.4: if f and all constraint functions g i are convex and X is convex, then the perturbation value function is convex on ℝ^m × ℝ^p.

universe u variable {E : Type u} [AddCommMonoid E] [Module ℝ E] variable {m p : ℕ} local notation "inequalitySpace" => EuclideanSpace ℝ (Fin m) local notation "equalitySpace" => EuclideanSpace ℝ (Fin p) local notation "perturbationSpace" => inequalitySpace × equalitySpace theorem value_function_is_convex (X : Set E) (f : E → EReal) (g : Fin m → E → EReal) (A : E →ₗ[ℝ] equalitySpace) (b : equalitySpace) (hf_convex : is_convex_function f) (hg_convex : ∀ i : Fin m, is_convex_function (g i)) (hX_convex : Convex ℝ X) : is_convex_function (value_function X f g A b)

Proposition 3.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

Proposition 3.4 is source-facing in the chapter spectral-subdifferential API. The ambient owner object for the matrix variable is the canonical submodule symmetricMatrices n = 𝕊^n from Definition 1.30, while the spectral owner data comes from mathlib's Matrix.IsHermitian.eigenvalues. The public declarations below keep the book's maximum-eigenvalue function and rank-one symmetric matrix as the source-facing views derived from those owners.

open scoped Matrix Matrix.Norms.Frobenius RealInnerProductSpace open Matrix open Matrix.IsHermitian variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "𝕊" => symmetricMatrices n local notation "euclideanSubdifferentialAt" => fun f x ↦ euclideanSubdifferential (fun y ↦ (f y : EReal)) x recall euclideanSubdifferential -- Proof sketch: the project owner criterion `mem_symmetricMatrices_iff` identifies membership in -- `𝕊^n` with symmetry. The transpose of `vvᵀ` is again `vvᵀ` by `transpose_vecMulVec`.

Theorem 3.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

Theorem 3.4 in owner-set form: every real-valued convex function on E is subdifferentiable at each point.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] -- Proof sketch: view `f` as the everywhere-finite extended-real-valued function -- `y ↦ (f y : EReal)`. Its effective domain is all of `E`, so every `x` is an interior point. -- The owner theorem `subdifferential_nonempty_at_interior_point` yields an algebraic dual -- subgradient, and finite dimensionality upgrades that linear functional canonically to a -- continuous one via `LinearMap.toContinuousLinearMap`; this is exactly a point of -- `subdifferentialAt f x`. theorem subdifferentialAt_nonempty_of_convexOn {f : E → ℝ} (hf : ConvexOn ℝ Set.univ f) (x : E) : (subdifferentialAt f x).Nonempty

Definition 3.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 3.5 is a bridge/view item in the chapter convex-analysis API: the owner object is subdifferential f x, and the textbook phrase "f is subdifferentiable at x" is exactly the nonemptiness proposition on that owner set. The downstream owner set subdifferential_domain introduced in Definition 3.6 is derived from this same proposition, so this file only recalls it.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] {f : E → EReal} {x : E} #check (subdifferential f x).Nonempty

Lemma 3.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 3.5 is source-facing in the chapter's finite-family inequality-constrained optimization API. The relevant owner abstractions are: 1. mathlib's IsMinOn for minimizers on a set; 2. Chapter 3's coordinatewiseMax for the maximum of finitely many real quantities. The primitive source-facing data are therefore only: 1. the feasible set cut out by the inequality family g; 2. the (m + 1)-tuple consisting of the objective gap and the constraint values. The residual objective itself is derived from that tuple through the owner coordinatewiseMax, so the file no longer keeps a parallel ad hoc finite-maximum encoding.

universe u variable {E : Type u} {m : ℕ} recall inequality_feasible_set

Proposition 3.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

Proposition 3.5 is recall-only in the chapter subdifferential API. The primitive owner data is subdifferential : Set (Module.Dual ℝ E). Convexity belongs to that owner abstraction itself, while closedness is a topological bridge statement on strongDualSubdifferential; this file therefore reuses those upstream declarations directly and introduces no parallel local wrapper.

recall isClosed_subdifferential

Theorem 3.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

Theorem 3.5 is source-facing in the Chapter 3 convex-analysis API. Its owner declarations are already the project primitives effective_domain, is_convex_function, and the continuous-dual bridge ∂ₛ f(x) from Theorem 3.1; this file keeps the textbook compact-union boundedness statement directly on that owner API instead of introducing any parallel wrapper. The ambient properness hypotheses are split according to the two source conclusions: part (1) uses is_convex_function f, X.Nonempty, and X ⊆ interior (effective_domain f), while part (2) uses ∀ y ∈ effective_domain f, f y ≠ ⊥, is_convex_function f, IsCompact X, and X ⊆ interior (effective_domain f). In both cases, effective_domain f is derived rather than kept as a primitive public binder.

universe u open Bornology open scoped Topology variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] variable (f : E → EReal) (X : Set E) recall effective_domain

Theorem 3.5.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 3.5.1 is a core/canonical recall item in convex geometry. The owner notion is intrinsicInterior ℝ, and the exact owner theorem for the source statement is Set.Nonempty.intrinsicInterior.

recall Set.Nonempty.intrinsicInterior

Lemma 3.5.feasible.set

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

The feasible set of the inequality-constrained problem cut out by the family g.

universe u variable {E : Type u} {m : ℕ} def inequality_feasible_set (g : Fin m → E → ℝ) : Set E := {x | ∀ i, g i x ≤ 0}

Definition 3.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

Definition 3.6: the domain of the subdifferential dom(∂ f) is the set of points where the extended-real-valued function f is subdifferentiable, equivalently where ∂ f(x) is nonempty.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] def subdifferential_domain (f : E → EReal) : Set E := {x | (subdifferential f x).Nonempty} -- Proof sketch: unfold `subdifferential_domain`.

Proposition 3.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

Proposition 3.6: if an extended-real-valued function is subdifferentiable at every point of its convex effective domain, then the function is convex.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] theorem is_convex_function_of_subdifferentiable_on_convex_effective_domain {f : E → EReal} (hdom : Convex ℝ (effective_domain f)) (hsub : effective_domain f ⊆ subdifferential_domain f) : is_convex_function f

Theorem 3.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

Theorem 3.6 is a source-facing existence statement in the chapter convex-analysis API. Its owner notions are already provided earlier in the project by effective_domain, is_convex_function, subdifferential, subdifferential_domain, and intrinsicInterior ℝ, so this file reuses those declarations directly rather than restating local copies. The relative- interior hypothesis already forces effective_domain f to be nonempty, and for a convex extended-real-valued function any occurrence of ⊥ is either absent on the effective domain or makes every dual vector a subgradient there. Thus the theorem needs only the owner convexity and relative-interior hypotheses.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] recall effective_domain

Proposition 3.6.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 3.6.1 (2): the subdifferential of negative_sqrt_extension at 0 is empty, so the function is not subdifferentiable there.

theorem negative_sqrt_extension_subdifferential_zero : ∂ negative_sqrt_extension(0) = ∅

Definition 3.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 3.7: the book's relative interior is the canonical convex-geometry notion intrinsicInterior ℝ.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] recall intrinsicInterior

Proposition 3.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 3.7 is a bridge/view item in the chapter convex-analysis API: its source-facing codomain is the owner set subdifferential_domain, and the proof is obtained pointwise from subdifferential_nonempty_at_relativeInterior_point. Since the relative-interior hypothesis is already vacuous when effective_domain f is empty and convexity itself handles any ⊥ values at relative-interior points, this bridge theorem needs only the owner convexity hypothesis.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] recall effective_domain

Theorem 3.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

Theorem 3.7 is recall-only as a bridge/view item in the chapter convex-subdifferential API: the exact owner theorem is already subdifferential_unbounded_of_affineSpan_effective_domain_direction_finrank_lt, stated on the continuous-dual owner bridge strongDualSubdifferential rather than an expanded set-builder presentation. The necessary domain hypothesis is part of that proposition statement; the textbook omission is explained in the source file comments rather than encoded in the public name.

recall subdifferential_unbounded_of_affineSpan_effective_domain_direction_finrank_lt

Proposition 3.7.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 3.7.1 is a bridge/view item in the chapter convex-analysis API. The owner notions effective_domain, IsProperExtendedRealFunction, is_convex_function, and subdifferential_domain already live upstream; the chapter-level bridge theorem is relativeInterior_effective_domain_subset_subdifferential_domain. This file combines that owner theorem with the canonical convex-geometry nonemptiness theorem for intrinsicInterior ℝ. The owner-level result therefore uses only the primitive data needed for the argument: convexity of f and nonemptiness of effective_domain f. The textbook proper-convex formulation is kept only as a thin source-facing corollary, since properness contributes here solely through hf.effective_domain_nonempty.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] recall effective_domain

Definition 3.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 3.8: the directional derivative of an extended-real-valued function at x in the direction d is the right-hand limit of the difference quotient α ↦ (f (x + α • d) - f x) / α. The book introduces this at interior points of the effective domain of a proper function.

universe u open scoped Topology open Filter variable {E : Type u} [AddCommMonoid E] [Module ℝ E] noncomputable def directional_derivative (f : E → EReal) (x d : E) : EReal := limUnder (𝓝[>] (0 : ℝ)) (fun α : ℝ ↦ (f (x + α • d) - f x) / (α : EReal)) -- Proof sketch: if the difference quotient tends to `ℓ` along `𝓝[>] 0`, then Hausdorff -- uniqueness of limits identifies `limUnder` with that same value.

Proposition 3.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 3.8 is recall-only in the chapter convex-analysis API: the source-facing proper-convex nonemptiness statement is already provided by subdifferential_domain_nonempty_of_proper_convex, while Proposition 3.7.1 also exposes the owner-level convex-plus-nonempty-domain theorem and the textbook witness-in-effective_domain companion corollary.

recall subdifferential_domain_nonempty_of_proper_convex

Theorem 3.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

Theorem 3.8: if f is a proper convex extended-real-valued function and x lies in the interior of effective_domain f, then for every direction d there is a finite real number that is the directional derivative of f at x along d.

universe u open scoped Topology variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable (f : E → EReal) (x d : E) theorem exists_real_has_directional_derivative_at_of_proper_convex_interior_point [IsProperExtendedRealFunction f] (hconvex : is_convex_function f) (hx : x ∈ interior (effective_domain f)) : ∃ ℓ : ℝ, has_directional_derivative_at f x d ℓ

Definition 3.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

Definition 3.9: for a proper convex extended-real-valued function, the directional derivative at an interior point of the effective domain is the maximum of the subgradient pairings g d over all g ∈ ∂f(x), expressed as an IsGreatest statement on the image of ∂f(x) under g ↦ g d.

universe u open Filter open scoped Topology variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] theorem directional_derivative_isGreatest_subgradient_pairings_at_interior_point {f : E → EReal} [IsProperExtendedRealFunction f] {x d : E} (hconvex : is_convex_function f) (hx : x ∈ interior (effective_domain f)) : IsGreatest ((fun g : Module.Dual ℝ E ↦ (g d : EReal)) '' ∂f(x)) (directional_derivative f x d)

Proposition 3.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 3.9 is a bridge/view statement in the chapter convex-analysis API. Domain sampling against Definition 3.6, Theorem 3.1, and Theorem 3.3 shows that the relevant owner surface is already the pair subdifferential_domain / strongDualSubdifferential, built over the Chapter 2 owner effective_domain; there is no further upstream declaration with the same conclusion to recall here, so this file should state the proposition directly on that owner API instead of introducing a parallel wrapper. The literal textbook wording omits the domain condition x ∈ subdifferential_domain f, but that hypothesis is mathematically necessary: if x ∉ subdifferential_domain f, then the subdifferential is empty and hence bounded. The file keeps that necessary hypothesis explicit in the proposition statement and records the omission only here in comments.

universe u open Bornology variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] recall effective_domain

Theorem 3.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

Theorem 3.9: for a finite nonempty family of proper extended-real-valued functions, at a point x ∈ ⋂ i, interior (effective_domain (f i)), if every directional derivative at x along d exists as a finite real value, then the directional derivative of the pointwise maximum is the maximum of the directional derivatives over the active indices I(x) = {i | fᵢ x = max_j fⱼ x}.

universe u v open Filter open scoped Topology variable {E : Type u} {ι : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] variable [Finite ι] [Nonempty ι] theorem directional_derivative_iSup_eq_iSup_active_indices_of_proper (f : ι → E → EReal) (x d : E) (hproper : ∀ i : ι, IsProperExtendedRealFunction (f i)) (hx : x ∈ ⋂ i : ι, interior (effective_domain (f i))) (hdir : ∀ i : ι, ∃ ℓ : ℝ, has_directional_derivative_at (f i) x d (ℓ : EReal)) : directional_derivative (fun y ↦ ⨆ i : ι, f i y) x d = iSup (fun i : {i : ι // f i x = ⨆ j : ι, f j x} ↦ directional_derivative (f i) x d)

Definition 3.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 3.10: an extended-real-valued function is differentiable at x when x lies in the interior of its finite domain and the real-valued restriction y ↦ (f y).toReal is differentiable there.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] def is_differentiable_at (f : E → EReal) (x : E) : Prop := x ∈ interior (finite_domain f) ∧ DifferentiableAt ℝ (fun y ↦ (f y).toReal) x -- Proof sketch: Fréchet differentiability of `y ↦ (f y).toReal` is, by definition, existence of a -- continuous linear derivative. The chapter-specific content is only the common hypothesis -- `x ∈ interior (finite_domain f)`, so the witness theorem should expose the owner predicate -- `HasFDerivAt` directly rather than a parallel local wrapper.

Proposition 3.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

Proposition 3.10 is a bridge/view reformulation of the Chapter 3 max formula from Definition_3_9: the owner notions remain directional_derivative and subdifferential, while the support-function expression is the Chapter 2 canonical reformulation.

universe u open scoped Topology open Module.Dual variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] recall support_function

Theorem 3.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

Theorem 3.10 is recall-only in the chapter directional-derivative API. Its mathematical content is the bridge/view finite-index specialization of the owner theorem directional_derivative_iSup_eq_iSup_active_indices from Theorem_3_9; the choice of Fin m adds no new primitive data beyond the existing [Finite ι] [Nonempty ι] owner hypotheses. This file therefore reuses that exact theorem instead of keeping a duplicate local Fin m wrapper.

recall directional_derivative_iSup_eq_iSup_active_indices

Definition 3.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

Definition 3.11 is a source-facing item in the affine-constrained duality API. The core/canonical owners are Chapter 2's effective_domain for finite-valued loci and the chapter declarations lagrangianDualObjective and dualObjectiveValues from Theorem_3_24. This file therefore keeps only the source-facing dom (-q) and dual-value views, with dom (-q) defined through the owner effective_domain rather than storing the derived lower-finiteness condition as primitive data.

variable {m n p : ℕ} local notation "DualMultiplierSpace" => (Fin m → ℝ) × (Fin p → ℝ) recall effective_domain

Proposition 3.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 3.11 is a bridge/view item on the chapter owner layer of finite nonempty index types: the owner max rule is directional_derivative_iSup_eq_iSup_active_indices, and the owner calculus bridges are has_directional_derivative_at_of_mem_interior_of_hasLineDerivAt and directional_derivative_eq_of_mem_interior_of_hasFDerivAt, organized around the chapter owner predicate is_differentiable_at. The active-indexed gradient pairing formula is therefore derived from those owner declarations rather than from a second local Fin-specific wrapper or a proof-artifact effective_domain/global-≠ ⊥ interface.

universe u v open Filter open InnerProductSpace (toDual) open scoped Topology RealInnerProductSpace Gradient variable {E : Type u} {ι : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable [Finite ι] [Nonempty ι] recall finite_domain

Theorem 3.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

Theorem 3.11 is recall-only in the chapter convex-analysis API. Its source-facing mathematical content is already owned by directional_derivative_isGreatest_subgradient_pairings_at_interior_point in Definition_3_9, stated at the chapter owner abstraction subdifferential; this file therefore reuses that exact theorem instead of keeping a second StrongDual-flavored wrapper API.

recall directional_derivative_isGreatest_subgradient_pairings_at_interior_point

Proposition 3.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 3.12: for a nonempty closed convex set C in a Euclidean space, the function x ↦ (Metric.infDist x C)^2 / 2 has gradient x - P_C(x) at x, where P_C is the metric projection onto C.

universe u open Metric variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable [CompleteSpace E] variable (C : Set E) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) local notation "P" => projectionPoint C hC_nonempty hC_closed hC_convex -- Proof sketch: unfold `metricProjection` as the chosen witness from -- `exists_norm_eq_iInf_of_complete_convex`; the chosen point satisfies the defining minimization -- property. variable [FiniteDimensional ℝ E] theorem hasGradientAt_half_sq_infDist (x : E) : HasGradientAt (fun y ↦ (infDist y C) ^ 2 / 2) (x - P x) x

Theorem 3.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

Theorem 3.12: if x lies in the interior of the finite domain and the real-valued restriction of f has Fréchet derivative g at x, then for every direction d the directional derivative of f at x along d is the pairing g d.

universe u open Filter open scoped Topology variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {f : E → EReal} {x : E} theorem directional_derivative_eq_of_mem_interior_of_hasFDerivAt {g : StrongDual ℝ E} (hx : x ∈ interior (finite_domain f)) (hg : HasFDerivAt (fun y ↦ (f y).toReal) g x) (d : E) : directional_derivative f x d = (g d : EReal)

Definition 3.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 3.13: median_set A is the set of real numbers β such that at least half of the elements of the finite nonempty set A lie below β and at least half lie above β.

def median_set (A : Finset ℝ) : Set ℝ := if A.Nonempty then {β | A.card ≤ 2 * (A.filter (fun a ↦ a ≤ β)).card} ∩ {β | A.card ≤ 2 * (A.filter (fun a ↦ β ≤ a)).card} else ∅

Proposition 3.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

Proposition 3.13: if the Fréchet derivative of f at x is represented by D through the standard Euclidean dot product on ℝ^m, then replacing the inner product by ⟪u, v⟫ = dotProduct u (H.mulVec v) for a positive definite matrix H changes the gradient to (H⁻¹).mulVec D.

open Matrix open scoped Gradient Matrix variable {m : ℕ} variable (H : Matrix (Fin m) (Fin m) ℝ) (hH : H.PosDef) theorem gradient_eq_inv_mulVec_of_posDef_matrix_inner {f : (Fin m → ℝ) → ℝ} {x D : Fin m → ℝ} (hD : HasFDerivAt f (LinearMap.toContinuousLinearMap (dotProductBilin ℝ ℝ D)) x) : H.qGradient hH f x = (H⁻¹).mulVec D

Theorem 3.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 3.13 is a bridge/view item in the chapter convex-analysis API. The source-facing owners remain effective_domain, finite_domain, is_convex_function, and the extended-real differentiability predicate is_differentiable_at from Definition 3.10, while the singleton conclusion naturally lives on the continuous-dual bridge strongDualSubdifferential, because toDual lands in StrongDual ℝ E. Here differentiability already supplies the interior finite-domain hypothesis, and for a convex extended-real-valued function that interior finite point forces the global no-⊥ property needed by the directional-derivative owner theorem, so that codomain restriction is derived API rather than primitive public data.

open InnerProductSpace (toDual) open Filter open scoped Topology Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] recall effective_domain

Definition 3.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

Definition 3.14: for weighted sites a i in a metric space, the Fermat-Weber objective is the weighted finite sum of the distances from x to the sites. In the Euclidean specialization this is the textbook formula x ↦ ∑ i, ω i * ‖x - a i‖. The textbook assumes positive weights; positivity is imposed only in later results, since it does not affect the function definition itself.

open scoped BigOperators variable {m : ℕ} {α : Type*} variable [PseudoMetricSpace α] def fermatWeberObjective (ω : Fin m → ℝ) (a : Fin m → α) : α → ℝ := fun x ↦ ∑ i, ω i * dist x (a i) -- Proof sketch: unfold `fermatWeberObjective`; the statement is exactly its defining formula.

Proposition 3.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

Proposition 3.14 (1): if a convex real-valued function on a finite-dimensional inner-product space is differentiable at x, then its Euclidean/vector-side subdifferential at x is the singleton containing the gradient ∇ f x.

open InnerProductSpace (toDual toDualMap) open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] theorem euclideanSubdifferentialAt_eq_singleton_gradient_of_differentiableAt {f : E → ℝ} (hf : ConvexOn ℝ Set.univ f) {x : E} (hdiff : DifferentiableAt ℝ f x) : euclideanSubdifferentialAt f x = {∇ f x}

Theorem 3.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

Theorem 3.14 is a source-facing theorem in the chapter convex-analysis API. Its owner declarations are already the chapter/project primitives effective_domain, is_subgradient_at, and subdifferential, so this file contributes only the positive-scaling calculus theorems.

universe u open scoped Pointwise variable {E : Type u} [AddCommGroup E] [Module ℝ E] recall effective_domain

Definition 3.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 3.15 is source-facing: it defines the constrained extended-real objective attached to f and C. The owner abstractions in this domain are the chapter declarations extendedIndicator for the set term, realEpigraph for the geometric owner view, and is_convex_function for the convexity predicate. Primitive data are only the original objective f, the feasible set C, and the source-facing rule "equal to f on C, equal to ⊤ off C". The identification with the canonical owner expression f + δ_C is derived bridge/view API only: it needs the extra hypothesis that f never takes the value ⊥ on Cᶜ, because x + ⊤ = ⊤ in EReal fails exactly at x = ⊥.

open Set universe u recall extendedIndicator

Proposition 3.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

Proposition 3.15: for the Euclidean norm on ℝ^n, the Euclidean/vector-side subdifferential is the singleton containing the normalized vector (1 / ‖x‖) • x away from the origin, and it is the closed Euclidean unit ball at the origin.

open InnerProductSpace (toDualMap) open Metric open scoped Gradient variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem euclidean_subdifferentialAt_l2_norm_eq_piecewise (x : E) : euclideanSubdifferentialAt (fun y : E ↦ ‖y‖) x = if x = 0 then closedBall (0 : E) 1 else {‖x‖⁻¹ • x}

Theorem 3.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

Theorem 3.15 is source-facing at the chapter owner subdifferential : Set (Module.Dual ℝ E). The continuous-dual object strongDualSubdifferential from Theorem 3.1 is only a bridge/view, so the main declarations here stay on the owner abstraction instead of restating the theorem after passing to StrongDual.

open Filter open scoped Pointwise Topology universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] recall subdifferential

Proposition 3.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

Proposition 3.16 is a bridge/view item in the chapter real-valued subdifferential API. The owner abstraction is subdifferentialAt, and the source-facing scalar-slope statement is expressed through its canonical one-dimensional vector-side bridge euclideanSubdifferentialAt from Theorem 3.4 rather than through an ad hoc encoding of real slopes as elements of StrongDual ℝ ℝ.

open InnerProductSpace (toDualMap) open scoped Gradient recall euclideanSubdifferentialAt -- Proof sketch: split into the cases `x > 0`, `x < 0`, and `x = 0`. For `x ≠ 0`, the function -- `t ↦ |t|` is differentiable at `x`, so the supporting-line inequality forces the only possible -- slope to be `Real.sign x`, and that slope indeed works. At `x = 0`, the inequality becomes -- `|y| ≥ v * y` for all `y`; testing it on `1` and `-1` gives `-1 ≤ v ≤ 1`, and conversely every -- `v ∈ [-1, 1]` defines a valid supporting line at the origin. -- -- This is kept in the same piecewise shape used by nearby norm/subdifferential files, so later -- coordinatewise sum arguments can reuse it without re-splitting on `x = 0`.

Theorem 3.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 3.16 extends the Chapter 3 subdifferential calculus from Theorem 3.15 to finite families. The canonical owner-level weak and exact sum rules are the primary public statements, and the textbook proper/effective-domain formulations are kept only as source-facing companions obtained from the owner API.

open Filter open scoped BigOperators Pointwise open scoped Topology universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] variable {ι : Type u} [Fintype ι] recall subdifferential

Definition 3.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 3.17 is source-facing. In this finite-dimensional convex subdifferential domain, the chapter owner abstractions are is_differentiable_at for extended-real differentiability and subdifferential for the nonsmooth term. The vector -∇ f(x) enters only through the canonical Riesz functional -toDual ℝ E (∇ (fun y ↦ (f y).toReal) x), viewed in the owner subdifferential g x; the continuous-dual set strongDualSubdifferential is therefore only a derived bridge/view, not primitive public data here. This file keeps only that source-facing predicate and its atomic owner-style specification theorem, with no parallel wrapper around the upstream owners.

universe u open InnerProductSpace (toDual) open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] recall is_differentiable_at

Proposition 3.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

Proposition 3.17: for the ℓ₁ norm f(x) = ‖x‖₁ = ∑ i, |ofLp x i| on E = EuclideanSpace ℝ ι, the Euclidean/vector-side subdifferential consists exactly of the vectors in toLp 2 '' l1CoordinateSubgradientVectors (ofLp x), i.e. the vectors whose coordinate representatives equal Real.sign (ofLp x i) on the nonzero coordinates of x and lie in [-1, 1] on the zero coordinates.

open WithLp (ofLp toLp) open scoped BigOperators universe u variable {ι : Type u} [Fintype ι] open InnerProductSpace (toDualMap) local notation "E" => EuclideanSpace ℝ ι -- Proof sketch: write the `ℓ₁` norm on `ℝ^n` as the finite sum of the coordinate functions -- `y ↦ |y i|`, apply the finite-dimensional sum rule for subdifferentials, and use the -- callable scalar companion `mem_euclideanSubdifferentialAt_abs_iff_sign_or_bound` from -- Proposition 3.16 on each coordinate. The resulting statement is expressed directly through the -- chapter bridge -- `euclideanSubdifferentialAt`, with the objective written via the canonical Chapter 6 owner -- `EuclideanSpace.l1Norm`, i.e. `‖·‖₁`, on finite products. theorem subdifferentialAt_l1_norm_eq_coordinatewise_sign_constraints (x : E) : euclideanSubdifferentialAt (fun y : E ↦ ‖y‖₁) x = toLp 2 '' l1CoordinateSubgradientVectors (ofLp x)

Theorem 3.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 3.17 is a bridge/view item in the chapter convex-analysis API. Its owner abstraction is still the chapter strong-dual finite-sum rule from Theorem_3_18; this file keeps only the real-valued everywhere-finite specialization subdifferentialAt, rather than a parallel local sum-rule API.

open scoped BigOperators Pointwise universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] recall subdifferentialAt

Definition 3.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

Definition 3.18 is source-facing, but its owner notions already exist upstream: the dual normal cone normal_cone from Definition 3.3 and the composite stationary predicate is_stationary_point from Definition 3.17. This file therefore keeps only the constrained specialization together with the Euclidean bridge/view theorem that rewrites owner normal-cone membership into the textbook variational inequality.

universe u open InnerProductSpace (toDual toDual_apply_apply) open scoped Gradient RealInnerProductSpace variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] recall is_stationary_point

Proposition 3.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

Proposition 3.18: for f(x) = ∑ i, |x i| on ℝ^n, the coordinatewise sign vector sgn(x) viewed in the dual via the Euclidean identification belongs to the subdifferential ∂ f(x).

open WithLp (ofLp toLp) variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem sign_vector_mem_subdifferentialAt_l1_norm (x : E) : toLp 2 (sgn (ofLp x)) ∈ euclideanSubdifferentialAt (fun y : E ↦ ‖toLp 1 (ofLp y)‖) x

Theorem 3.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 3.18 is source-facing in the chapter subdifferential API. The owner notions effective_domain, is_convex_function, subdifferential, and intrinsicInterior ℝ already live upstream, so this file contributes only the relative-interior qualification for the existing finite-sum rule. Under the qualification hypothesis, nonemptiness of every effective domain is already forced, so the only primitive codomain restriction in the main theorem is that no summand takes the value ⊥. A strong-dual reformulation is kept below only as a private bridge on the same normed finite-dimensional ambient.

open Bornology open scoped BigOperators Pointwise universe u v variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] variable {ι : Type v} [Fintype ι] recall effective_domain

Definition 3.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 3.19 is source-facing: it defines the stationary-point predicate for the ℓ₁-regularized problem. The owner abstraction in this domain is the chapter composite stationarity predicate is_stationary_point; the ℓ₁ subdifferential expression only appears in the source-facing specification theorem below.

open InnerProductSpace (toDual toDualMap) open WithLp (ofLp toLp) open scoped Gradient Pointwise variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) recall is_differentiable_at

Proposition 3.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

Proposition 3.19 is a bridge/view item in the chapter real-valued subdifferential API. The core owner abstraction is subdifferentialAt, and the canonical vector-side bridge owner is euclideanSubdifferentialAt. The affine pullback is already owned upstream by subdifferential_precompose_affineMap_eq, while the source-facing ℓ₁ subgradient set is already packaged by l1CoordinateSubgradientVectors together with subdifferentialAt_l1_norm_eq_coordinatewise_sign_constraints. This file exposes the book's coordinate sign-cube description as the labeled statement and keeps the affine-chain-rule image formula as a companion.

open InnerProductSpace (toDual toDualMap) open scoped BigOperators open WithLp (ofLp toLp) variable {m n : ℕ} local notation "Em" => EuclideanSpace ℝ (Fin m) local notation "En" => EuclideanSpace ℝ (Fin n) recall euclideanSubdifferentialAt

Theorem 3.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

Theorem 3.19 is source-facing at the chapter owner subdifferential : Set (Module.Dual ℝ E), while the ambient affine geometry already has the canonical owner abstraction AffineMap. The pullback acts on subgradients through the linear part φ.linear.dualMap, so the public theorem stays at the algebraic-dual owner level and downstream StrongDual and Euclidean files should reuse it through the chapter bridge/view APIs rather than repackaging the affine map as primitive data (A, b).

universe u v variable {V : Type u} {E : Type v} variable [AddCommGroup V] [Module ℝ V] variable [AddCommGroup E] [Module ℝ E] recall subdifferential -- Proof sketch: if `g ∈ ∂ f(φ x)`, then `φ x ∈ effective_domain f` and the defining -- subgradient inequality for `g` applied to `φ y` gives -- `f (φ y) ≥ f (φ x) + g (φ.linear (y - x))`. Rewrite the last term as -- `(φ.linear.dualMap g) (y - x)` using `φ.linearMap_vsub` to obtain the subgradient inequality -- for `φ.linear.dualMap g` at `x`.

Definition 3.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 3.20: Slater's condition for the inequality-constrained problem with constraint family g means that there exists a point strictly satisfying every inequality g_i(x) < 0.

universe u variable {E : Type u} {m : ℕ} variable {g : Fin m → E → ℝ} def slaters_condition (g : Fin m → E → ℝ) : Prop := (strict_inequality_feasible_set g).Nonempty

Proposition 3.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

Proposition 3.20 is a bridge/view item in the chapter real-valued subdifferential API. Its core owner abstraction is the canonical subdifferentialAt from Theorem 3.4, and its Euclidean bridge/view owner is euclideanSubdifferentialAt. The affine pullback step is governed upstream by the source-facing owner theorem subdifferential_precompose_affineMap_eq from Theorem 3.19, while the concrete norm-side case split already belongs to Proposition 3.15. The primitive data here are just the affine map y ↦ A y + b and the owner Euclidean-norm subdifferential; the transpose-image and piecewise singleton/ball formulas are derived API.

open InnerProductSpace open Metric variable {m n : ℕ} local notation "Em" => EuclideanSpace ℝ (Fin m) local notation "En" => EuclideanSpace ℝ (Fin n) recall euclideanSubdifferentialAt

Theorem 3.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 3.20 lives at the one-variable calculus owner layer. Its main statement is already the canonical mathlib chain rule HasDerivAt.comp_hasDerivWithinAt; the textbook right-endpoint formula for derivWithin is only a thin bridge/view consequence of that owner theorem together with HasDerivWithinAt.derivWithin and uniqueDiffWithinAt_Ici.

open Set recall HasDerivAt.comp_hasDerivWithinAt

Proposition 3.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

Proposition 3.21: if C is a nonempty closed convex subset of a complete real inner product space, then every point on the ray P_C x + λ (x - P_C x) with λ ≥ 0 has the same metric projection onto C as x.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (C : Set E) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) local notation "Pₛ" => metricProjection C hC_nonempty hC_closed hC_convex local notation "P" => fun x ↦ (Pₛ x : E) theorem metricProjection_add_smul_sub_metricProjection_eq (x : E) (lam : ℝ) (hlam : 0 ≤ lam) : P (P x + lam • (x - P x)) = P x

Theorem 3.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 3.21 is source-facing in the Chapter 3 convex-analysis API. Its core/canonical owner is the real-valued strong-dual subdifferential subdifferentialAt from Theorem 3.4, so this file keeps only the composition rule for that owner set-valued map and does not introduce any parallel wrapper or auxiliary packaged notion.

open scoped Pointwise open Filter open scoped Topology universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] variable {f : E → ℝ} {g : ℝ → ℝ} {x : E} recall subdifferentialAt

Proposition 3.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

Proposition 3.22 is a bridge/view item for the chapter owner subdifferentialAt. Semantic recall was inconclusive, and local Chapter 3 precedent fixes the public surface: use euclideanSubdifferentialAt on the left and the point-valued projection projectionPoint from Proposition 3.12 for P_C. On the feasible branch, the main source-facing statement uses the Euclidean feasible-displacement inequality equivalent to the chapter owner N[C](x); the translated polar_cone formula remains a companion reformulation.

universe u open Metric open InnerProductSpace (toDual toDualMap) open scoped Pointwise RealInnerProductSpace variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable (C : Set E) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) local notation "P" => projectionPoint C hC_nonempty hC_closed hC_convex recall euclideanSubdifferentialAt

Theorem 3.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

Theorem 3.22: max rule of subdifferential calculus. For a nonempty finite family of convex functions that never attain -∞, the owner subdifferential ∂ (fun y ↦ ⨆ i, f i y)(x) at an interior point is the convex hull of the union of the active subdifferentials ∂ (f i)(x).

universe u v open scoped Topology variable {E : Type u} {ι : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] variable [Finite ι] [Nonempty ι] theorem subdifferential_pointwise_max_eq_convexHull_iUnion_active_subdifferential (f : ι → E → EReal) (x : E) (h_ne_bot : ∀ i : ι, ∀ y : E, f i y ≠ ⊥) (hconvex : ∀ i : ι, is_convex_function (f i)) (hx : x ∈ ⋂ i : ι, interior (effective_domain (f i))) : ∂ (fun y ↦ ⨆ i : ι, f i y)(x) = convexHull ℝ (⋃ i : {i : ι // f i x = ⨆ j : ι, f j x}, ∂ (f i)(x))

Proposition 3.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

Proposition 3.23 [Subdifferential of the max function]: the Euclidean/vector-side subdifferential of the coordinatewise maximum on ℝ^n is exactly the face of the standard simplex supported on the active coordinates.

open WithLp (toLp ofLp) open scoped BigOperators open InnerProductSpace (toDualMap) universe u variable {ι : Type u} [Fintype ι] local notation "E" => EuclideanSpace ℝ ι variable [Nonempty ι] theorem euclidean_subdifferentialAt_coordinatewiseMax_eq_activeCoordinateFace (x : E) : euclideanSubdifferentialAt (fun y : E ↦ coordinatewiseMax (ofLp y)) x = toLp 2 '' activeCoordinateFace (ofLp x)

Theorem 3.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

Theorem 3.23: weak maximum rule of subdifferential calculus. If every branch fᵢ lies below F, then the convex hull of the subdifferentials of the branches active at x is contained in the subdifferential of F at x.

universe u v variable {E : Type u} {ι : Type v} variable [AddCommGroup E] [Module ℝ E] theorem convexHull_iUnion_active_subdifferential_subset_subdifferential_iSup (F : E → EReal) (f : ι → E → EReal) (x : E) (hupper : ∀ y : E, ∀ i : ι, f i y ≤ F y) : convexHull ℝ (⋃ i : {i : ι // F x = f i x}, ∂(f i)(x)) ⊆ ∂ F(x)

Proposition 3.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

Proposition 3.24: for f(x) = ‖x‖∞ = ‖x‖ on ℝ^n = Fin n → ℝ, the Euclidean/vector-side subdifferential is the ℓ₁ unit ball {z | ‖z‖₁ ≤ 1} at the origin, and away from the origin it is the set of convex combinations ∑_{i ∈ I(x)} λ_i sign (x_i) e_i supported on the active coordinates I(x) = {i | |x i| = ‖x‖∞}.

open WithLp (toLp ofLp) open scoped BigOperators open InnerProductSpace (toDualMap) universe u variable {ι : Type u} [Fintype ι] local notation "E" => EuclideanSpace ℝ ι theorem euclidean_subdifferentialAt_linf_eq_piecewise (x : E) : euclideanSubdifferentialAt (fun y : E ↦ ‖ofLp y‖) x = if x = 0 then {z : E | ‖z‖₁ ≤ 1} else (fun coeff : ι → ℝ ↦ toLp 2 fun i ↦ coeff i * Real.sign (ofLp x i)) '' activeCoordinateFace (fun i ↦ |ofLp x i|)

Theorem 3.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

Theorem 3.24 is source-facing in the affine-constrained perturbation/duality API. Its core/canonical owners are already the earlier chapter declarations effective_domain, IsProperExtendedRealFunction, is_convex_function, the continuous-dual bridge strongDualSubdifferential, and the perturbation owner value_function from Lemma_3_4. The source theorem takes the constraint family g₁, …, gₘ to be extended-real-valued convex functions, so this file keeps that owner-compatible surface directly instead of inserting a real-valued coercion layer.

open InnerProductSpace (toDualMap) open Matrix open WithLp (ofLp toLp) open scoped BigOperators variable {m n p : ℕ} local notation "PerturbationSpace" => EuclideanSpace ℝ (Fin m) × EuclideanSpace ℝ (Fin p) recall effective_domain

Proposition 3.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

Proposition 3.25: for the piecewise linear function x ↦ max_i (a_i^T x + b_i) on ℝ^n, the subdifferential at x is the image of the active face of the standard simplex under the map sending a simplex coefficient vector to the corresponding convex combination of the active slope vectors a_i, viewed through the coordinate-space dot-product identification.

open Matrix open WithLp (toLp ofLp) open InnerProductSpace (toDualMap) open scoped BigOperators variable {m n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Em" => EuclideanSpace ℝ (Fin m) theorem subdifferentialAt_piecewiseLinearMax_eq_image_activeCoordinateFace (hm : 0 < m) (a : Fin m → (Fin n → ℝ)) (b : Fin m → ℝ) (x : Fin n → ℝ) : subdifferentialAt (piecewiseLinearMax a b) x = ((dotProductEquiv ℝ (Fin n)).trans LinearMap.toContinuousLinearMap) '' ((fun coeff : Fin m → ℝ ↦ (∑ i : Fin m, coeff i • a i : Fin n → ℝ)) '' activeCoordinateFace (fun i : Fin m ↦ a i ⬝ᵥ x + b i))

Proposition 3.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

Proposition 3.26 is a bridge/view item in the chapter's coordinate ℓ∞ subdifferential API. The owner abstractions already live upstream: Theorem 3.19 gives the affine-map pullback rule on subdifferential, and Proposition 3.24 gives the vector-side owner formula through euclideanSubdifferentialAt for the residual ℓ∞ norm on Fin m → ℝ. The only primitive data here are the affine matrix map A.toEuclideanLin and the offset b; the transpose-image formula is derived from those owners.

open InnerProductSpace (toDualMap) open WithLp (toLp ofLp) variable {m n : ℕ} local notation "Em" => EuclideanSpace ℝ (Fin m) local notation "En" => EuclideanSpace ℝ (Fin n) recall euclideanSubdifferentialAt

Theorem 3.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

Theorem 3.26 is source-facing in the affine-constrained perturbation/penalty API. Its core/canonical owner abstraction is IsDualOptimalSolution; the chapter perturbation owner value_function and the bridge theorem isDualOptimalSolution_iff_neg_pair_mem_subdifferential_valueFunction_zero from Theorem_3_24 explain why this owner is canonical. This file keeps only the source-facing penalty estimates and does not add a parallel local owner API on top of those declarations.

open Matrix open WithLp (toLp) open scoped BigOperators variable {m n p : ℕ} variable {f : (Fin n → ℝ) → EReal} {g : Fin m → (Fin n → ℝ) → EReal} {A : Matrix (Fin p) (Fin n) ℝ} {b : Fin p → ℝ} {xTilde : Fin n → ℝ} {fOpt rho1 rho2 delta : ℝ} local notation "IneqSpace" => EuclideanSpace ℝ (Fin m) local notation "EqSpace" => EuclideanSpace ℝ (Fin p) variable {X : Set (Fin n → ℝ)} {yStar : Fin m → ℝ} {zStar : Fin p → ℝ} recall IsDualOptimalSolution

Proposition 3.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

Proposition 3.27 is recall-only in the Chapter 3 subdifferential-calculus API. The primary mathematical domain is the weak max rule for subdifferentials of pointwise suprema. In this domain, the owner abstraction is the Chapter 3 owner set subdifferential; the active-index family {i : ι // f i x = ⨆ j, f j x} is derived data, and the convex-hull inclusion is the canonical source-facing statement. Sampling the nearby owner declarations: * directional_derivative_iSup_eq_iSup_active_indices in Theorem_3_9 identifies the active indices for pointwise suprema. * subdifferential_pointwise_max_eq_convexHull_iUnion_active_subdifferential in Theorem_3_22 is the stronger equality under finite-family convexity/interior hypotheses. * convexHull_iUnion_active_subdifferential_subset_subdifferential_iSup in Theorem_3_23 is the weak inclusion with the exact source-facing semantics of Proposition 3.27. This file therefore reuses the owner theorem from Theorem_3_23 directly and introduces no parallel local wrapper.

recall convexHull_iUnion_active_subdifferential_subset_subdifferential_iSup

Theorem 3.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

Theorem 3.27 is source-facing in the Chapter 3 convex-analysis API. Its owner declarations are already the project primitives effective_domain, is_convex_function, and the continuous-dual bridge strongDualSubdifferential, together with mathlib's owner LipschitzOnWith. The textbook hypothesis is the pointwise norm bound ∀ g ∈ ∂ₛ f(x), ‖g‖ ≤ L; the closed-ball reformulation is kept only as a thin companion bridge for metric-owner API.

universe u open Metric variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] recall effective_domain

Proposition 3.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

Proposition 3.28: the coefficient vector (yᵀ A₁ y, yᵀ A₂ y, ..., yᵀ A_m y) is a Euclidean subgradient of x ↦ λ_max (A₀ + ∑ i, xᵢ Aᵢ) at x whenever y is a normalized eigenvector for the largest eigenvalue of A₀ + ∑ i, xᵢ Aᵢ.

open scoped BigOperators Matrix Matrix.Norms.Frobenius open Matrix InnerProductSpace open WithLp (toLp) variable {m n : ℕ} local notation "Em" => EuclideanSpace ℝ (Fin m) local notation "En" => EuclideanSpace ℝ (Fin n) local notation "𝕊" => symmetricMatrices n variable [NeZero n] theorem affineSpectralSubgradientVector_mem_euclideanSubdifferentialAt_affineSymmetricMaxEigenvalue (A0 : 𝕊) (A : Fin m → 𝕊) (x : Em) (y : En) (hy_norm : ‖y‖ = 1) (hy_eigen : (A0 + ∑ i, x i • A i) *ᵥ y = symmetricMaxEigenvalue (A0 + ∑ i, x i • A i) • y) : affineSpectralSubgradientVector A y ∈ euclideanSubdifferentialAt (fun z : Em ↦ symmetricMaxEigenvalue (A0 + ∑ i, z i • A i)) x

Corollary 3.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

Corollary 3.29 is a bridge/view compactness upgrade in the chapter convex-analysis API. Its owner abstractions are already Chapter 2's effective_domain, is_convex_function, and the canonical real-valued owner ConvexOn ℝ (effective_domain f) (fun x ↦ (f x).toReal). The compact-set conclusion is derived from mathlib's owner-level local-Lipschitz API on the interior of a convex domain and the standard compactness upgrade from LocallyLipschitzOn to LipschitzOnWith.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] recall effective_domain

Proposition 3.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

Proposition 3.30: for the max-affine function f(x) = max_i (a_i^T x + b_i) on ℝ^n, the vector-side subdifferential at x is exactly the set of convex combinations of the active slope vectors a_i, equivalently the image of the active face of the standard simplex under the barycentric combination map.

open Matrix open scoped BigOperators variable {m n : ℕ} recall isMinOn_univ_iff_zero_mem_subdifferentialAt

Theorem 3.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 3.30: Fermat's optimality condition for the chapter's extended-real subdifferential. If the effective domain of an extended-real-valued function is nonempty, then a point is a global minimizer exactly when the zero dual vector belongs to its subdifferential.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] theorem isMinOn_univ_iff_zero_mem_subdifferential {f : E → EReal} (hdom : (effective_domain f).Nonempty) {x : E} : IsMinOn f Set.univ x ↔ 0 ∈ subdifferential f x

Proposition 3.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

Proposition 3.31 is source-facing at the possible-median predicate for an indexed finite sample and the unit-weight one-dimensional Fermat-Weber objective. The public owner for that objective is already fermatWeberObjective from Definition 3.14, so the textbook sum x ↦ ∑ i, |x - a i| is only a bridge/view description here rather than a second objective wrapper. The core/canonical owner in this domain is IsMinOn for global minimizers. On the median side, the primitive counting predicate remains local here, because the earlier chapter owner median_set is defined on Finset ℝ and would erase sample multiplicities through Finset.image; a named set-valued companion is still useful for downstream reuse of the indexed notion.

open scoped BigOperators variable {n : ℕ} recall IsMinOn

Theorem 3.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 3.31: necessary and sufficient optimality conditions for convex constrained optimization. If f is a proper convex extended-real-valued function, C is convex, and ri(dom f) ∩ ri(C) ≠ ∅, then a feasible point xStar ∈ C minimizes f on C if and only if there exists a subgradient g ∈ ∂ f(xStar) whose negation belongs to the normal cone N[C](xStar).

open scoped BigOperators Pointwise universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] theorem isMinOn_iff_exists_subgradient_neg_mem_normal_cone {f : E → EReal} (hf : IsProperExtendedRealFunction f) (hconv : is_convex_function f) {C : Set E} (hC : Convex ℝ C) (hri : (intrinsicInterior ℝ (effective_domain f) ∩ intrinsicInterior ℝ C).Nonempty) {xStar : E} (hxStar : xStar ∈ C) : IsMinOn f C xStar ↔ ∃ g : Module.Dual ℝ E, g ∈ ∂ f(xStar) ∧ -g ∈ N[C](xStar)

Corollary 3.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

Corollary 3.32 is a bridge/view reformulation in the chapter convex-analysis API. The core/canonical owner theorem is isMinOn_iff_exists_subgradient_neg_mem_normal_cone from Theorem 3.31, and the textbook feasible-displacement inequality is the owner normal-cone membership criterion mem_normal_cone. This file keeps only the source-facing variational-inequality restatement.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] recall effective_domain

Proposition 3.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

Proposition 3.32: the Euclidean subdifferential of the Fermat-Weber objective fun x ↦ ∑ i, ω i * ‖x - a i‖ is the finite Minkowski sum of the single-term subdifferentials, so each summand contributes the normalized vector ω i • ((‖x - a i‖)⁻¹ • (x - a i)) away from its site and the closed Euclidean ball closedBall (0 : E) (ω i) at its site; this remains valid for nonnegative weights, with ω i = 0 giving the singleton {0} in both cases.

open scoped BigOperators Pointwise open InnerProductSpace open Metric variable {m d : ℕ} local notation "E" => EuclideanSpace ℝ (Fin d) theorem euclidean_subdifferentialAt_fermatWeberObjective_eq_finset_sum_piecewise (ω : Fin m → ℝ) (hω : ∀ i, 0 ≤ ω i) (a : Fin m → E) (x : E) : euclideanSubdifferentialAt (fermatWeberObjective ω a) x = ∑ i : Fin m, if x = a i then closedBall (0 : E) (ω i) else {ω i • ((‖x - a i‖)⁻¹ • (x - a i))}

Corollary 3.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

Corollary 3.33 is a source-facing simplex specialization of the owner constrained-optimality criterion isMinOn_iff_exists_subgradient_neg_mem_normal_cone from Theorem 3.31, together with the simplex normal-cone bridge neg_dotProductEquiv_mem_normal_cone_stdSimplex_iff_exists_multiplier from Proposition 3.34. This file therefore keeps only the simplex-specific statement and reuses the upstream convex-analysis API directly.

variable {n : ℕ} local notation "Δ" => stdSimplex ℝ (Fin n) recall effective_domain

Proposition 3.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

Proposition 3.33: for pairwise distinct sites and nonnegative weights, a point globally minimizes the Fermat--Weber objective if and only if either it is not one of the sites and the weighted normalized displacement vectors sum to zero, or it equals a site a_j and the norm of the corresponding residual sum over the remaining sites is at most ω_j.

open scoped BigOperators Pointwise variable {m d : ℕ} local notation "E" => EuclideanSpace ℝ (Fin d) theorem isMinOn_fermatWeberObjective_iff_balance_or_site_bound (ω : Fin m → ℝ) (a : Fin m → E) (ha : Function.Injective a) (hω : ∀ i, 0 ≤ ω i) (x : E) : IsMinOn (fermatWeberObjective ω a) Set.univ x ↔ (x ∉ Set.range a ∧ ∑ i, fermatWeberBalanceTerm ω a x i = 0) ∨ ∃ j : Fin m, x = a j ∧ ‖fermatWeberResidualBalance ω a j‖ ≤ ω j

Proposition 3.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

Proposition 3.34 is a bridge/view item in the simplex-constrained optimality API. The chapter owner abstraction for feasible-displacement inequalities is the normal cone N[Δ](xStar); at a feasible point this is Definition 3.3's source-facing cone, built from the translated-set polar cone polar_cone (Δ -ᵥ {xStar}). The primitive data are only the simplex point xStar, the coordinate vector g, and the scalar μ; the raw inequality ∀ x ∈ Δ_n, 0 ≤ gᵀ (x - xStar) is derived from this owner cone-membership condition rather than treated as a second root notion.

variable {n : ℕ} variable {xStar g : Fin n → ℝ} local notation "Δ" => stdSimplex ℝ (Fin n) recall normal_cone

Proposition 3.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

Proposition 3.35: if xstar is a strictly positive minimizer of entropy_linear_objective y, equivalently x ↦ ∑ i, x i * log (x i) - ∑ i, y i * x i, on the unit simplex Δ_n = stdSimplex ℝ (Fin n), then xstar is the softmax point softmax_point y.

open scoped BigOperators variable {n : ℕ} theorem eq_softmax_of_isMinOn_stdSimplex_entropyLinearObjective (y xstar : Fin n → ℝ) (hxstar_mem : xstar ∈ stdSimplex ℝ (Fin n)) (hxstar_pos : ∀ i, 0 < xstar i) (hmin : IsMinOn (entropy_linear_objective y) (stdSimplex ℝ (Fin n)) xstar) : xstar = softmax_point y

Theorem 3.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 3.35 is source-facing for composite first-order optimality. Its primitive convex-analysis notions are already owned upstream by effective_domain and is_convex_function, while the source-facing stationarity condition itself is already owned in Definition 3.17 by is_stationary_point. The continuous-dual set strongDualSubdifferential is only the bridge/view used inside that owner predicate, so this file states its conclusions in terms of is_stationary_point instead of duplicating the defining condition. For this item, the primitive source data is the properness of f, the properness and convexity of g, the qualification effective_domain g ⊆ interior (finite_domain f), the feasibility point xStar ∈ effective_domain g, the chapter differentiability owner is_differentiable_at f xStar, and the corresponding local or global optimality statement for the composite problem fun x ↦ f x + g x.

open InnerProductSpace (toDual) open Filter open scoped Pointwise Topology Gradient -- Declarations for this item will be appended below by the statement pipeline. universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] recall effective_domain

Theorem 3.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

Theorem 3.36 is source-facing in the chapter's inequality-constrained convex-optimality API. Its core/canonical owner notions already exist upstream: 1. subdifferentialAt from Theorem 3.4 for real-valued subgradients; 2. inequality_feasible_set from Lemma 3.5 for the feasible set; 3. optimality_residual from Lemma 3.5 for the canonical finite-maximum residual objective. The primitive source-facing data here are only the scalar/vector multipliers together with the textbook Fritz-John conditions they satisfy, so this file keeps those conditions as a plain predicate and reuses the owner declarations directly.

open scoped BigOperators Pointwise universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] recall subdifferentialAt

Theorem 3.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 3.37 is a bridge/view item in the same inequality-constrained convex-optimality domain as Theorem 3.36. Its owner abstractions are the chapter slaters_condition from Definition 3.20, the strict/weak feasible-set owners strict_inequality_feasible_set and inequality_feasible_set, and the source-facing Fritz-John multiplier predicate from Theorem 3.36. This file therefore keeps the textbook KKT wording only as a thin specialization of IsFritzJohnMultiplier f g xstar 1 lambda, instead of reintroducing parallel existential wrappers for strict feasibility or KKT data.

open scoped BigOperators Pointwise universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] recall subdifferentialAt