Chapter 04 — Conjugate Functions

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

Definition 4.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 4.1: the conjugate function f* of an extended-real-valued function f is the extended-real-valued function on the dual space E* = Module.Dual ℝ E sending y to the supremum of the values y x - f x over all x : E. This is the canonical EReal formulation of the textbook formula (4.1).

universe u open InnerProductSpace (toDualMap) variable {E : Type u} [AddCommGroup E] [Module ℝ E] noncomputable def conjugate_function (f : E → EReal) : Module.Dual ℝ E → EReal := fun y ↦ sSup (Set.range fun x : E ↦ (y x : EReal) - f x)

Lemma 4.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 4.1: the biconjugate of an extended-real-valued function is pointwise bounded above by the original function.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] -- Proof sketch: for fixed `x` and any dual vector `y`, the defining supremum formula for -- `conjugate_function f y` gives `y x - f x ≤ conjugate_function f y`. Rearranging yields -- `y x - conjugate_function f y ≤ f x`, and taking the supremum over `y` gives -- `biconjugate_function f x ≤ f x`. theorem biconjugate_function_apply_le (f : E → EReal) (x : E) : biconjugate_function f x ≤ f x

Proposition 4.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 4.1: equations (4.2) and (4.3) identify the Fenchel conjugate of the indicator function δ_C with the support function σ_C.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] theorem conjugate_function_extendedIndicator_eq_support_function (C : Set E) : conjugate_function (δ_ C) = σ_ C

Theorem 4.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 4.1 is source-facing in the chapter conjugacy API. Its primitive notions are the owner declarations is_convex_function from Definition 2.6 and conjugate_function from Definition 4.1; the canonical bridge/view owner is conjugate_function_primal, which specializes the dual-space conjugate to the primal inner-product space through toDualMap without reintroducing a local lambda wrapper.

universe u open InnerProductSpace variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] recall conjugate_function_primal

Definition 4.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 4.2: the biconjugate f** of an extended-real-valued function f is the extended-real-valued function on E obtained by applying the Chapter 4 owner conjugate_function from Definition 4.1 to f* on the dual space and then restricting along the canonical double-dual evaluation map E → E**. Equivalently, it is the supremum over the dual space E* = Module.Dual ℝ E of the values y x - f*(y).

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] noncomputable def biconjugate_function (f : E → EReal) : E → EReal := fun x ↦ conjugate_function (conjugate_function f) (Module.Dual.eval ℝ E x)

Proposition 4.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 4.2 is source-facing in the chapter conjugacy API. The core/canonical owners for properness and Fenchel conjugation are already Chapter 2's IsProperExtendedRealFunction and Definition 4.1's conjugate_function, so this file keeps only the source-facing inequality and reuses those owners directly.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] recall IsProperExtendedRealFunction

Theorem 4.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 4.2 is source-facing in the chapter conjugacy API: it states the biconjugate identity for a proper, closed, convex EReal-valued function. Chapter 2's IsProperExtendedRealFunction and is_convex_function together with Mathlib's LowerSemicontinuous and Definition 4.2's biconjugate_function (built on Definition 4.1's conjugate_function) provide the ambient notions. The textbook proper/closed/convex statement remains the unique labeled main entry in this item file: for general EReal-valued functions the properness hypothesis is semantically active, because allowing ⊥ changes the biconjugate.

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

Proposition 4.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 4.3 is source-facing: it identifies the conjugate of the support function with the indicator of the closed convex hull. The owner abstractions already live upstream: the indicator notation δ_ C in Chapter 2, the primal support-function owner σ[C] in Chapter 2, and Definition 4.1's owner pair conjugate_function / conjugate_function_primal. This file therefore keeps only the proposition itself.

universe u open InnerProductSpace (toDualMap) variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] recall conjugate_function_primal -- Semantic recall: `lean_leansearch` surfaced only general closed-convex-hull API, not a -- project-specific owner theorem for this exact conjugacy identity, so this file keeps the -- faithful source-facing statement directly on the chapter owners `σ[C]` and `f∗`. -- Proof sketch: combine Proposition 4.1 with the Chapter 2 support-function invariance under -- convex hull and closure, then use the finite-dimensional Euclidean biconjugation setup from the -- surrounding Chapter 4 results.

Theorem 4.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 4.3: if each coordinate function is proper, then the conjugate of the finite separable sum on the product space, evaluated at the canonical product dual LinearMap.lsum ℝ E ℝ y determined by the coordinate dual vectors, is the sum of the coordinatewise conjugates.

open Matrix open scoped BigOperators universe u variable {p : ℕ} variable {E : Fin p → Type u} variable [∀ i, AddCommGroup (E i)] variable [∀ i, Module ℝ (E i)] theorem conjugate_function_separable_sum_eq_sum_conjugate_function (f : ∀ i, E i → EReal) (h_proper : ∀ i, IsProperExtendedRealFunction (f i)) (y : ∀ i, Module.Dual ℝ (E i)) : conjugate_function (fun x : ∀ i, E i ↦ ∑ i, f i (x i)) (LinearMap.lsum ℝ E ℝ y) = ∑ i, conjugate_function (f i) (y i)

Definition 4.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 4.4: if A ∈ 𝕊_{++}^n and f(x) = (1 / 2) xᵀ A x + bᵀ x + c, then for every y the conjugate f*(y) is the maximum of the rewritten objective from equation (4.4.7), x ↦ -(1 / 2) xᵀ A x - (b - y)ᵀ x - c, and that maximum is attained.

open Matrix universe u variable {ι : Type u} [Fintype ι] [DecidableEq ι] local notation "E" => ι → ℝ theorem quadratic_affine_function_conjugate_attainsMaximum (A : Matrix ι ι ℝ) (hA : A.PosDef) (b y : E) (c : ℝ) : ∃ x : E, conjugate_function (fun z : E ↦ (quadratic_affine_function A b c z : EReal)) (dotProductEquiv ℝ ι y) = (((-(1 / 2 : ℝ)) * dotProduct x (A *ᵥ x) - dotProduct (b - y) x - c : ℝ) : EReal) ∧ IsGreatest (Set.range fun z : E ↦ (-(1 / 2 : ℝ)) * dotProduct z (A *ᵥ z) - dotProduct (b - y) z - c) ((-(1 / 2 : ℝ)) * dotProduct x (A *ᵥ x) - dotProduct (b - y) x - c)

Proposition 4.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 4.4: for the function f(x) = max {x_1, x_2, ..., x_n} on ℝ^n, the Fenchel conjugate, expressed on ℝ^n through the Euclidean pairing dotProductEquiv, is the indicator function of the standard simplex Δ_n.

open Matrix theorem conjugate_coordinatewiseMax_eq_extendedIndicator_stdSimplex {n : ℕ} [Nonempty (Fin n)] : (fun y : Fin n → ℝ ↦ conjugate_function (fun x : Fin n → ℝ ↦ (coordinatewiseMax x : EReal)) (dotProductEquiv ℝ (Fin n) y)) = extendedIndicator (stdSimplex ℝ (Fin n))

Theorem 4.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 4.4: for g(x) = f (A (x - a)) + ⟨b, x⟩ + c, the conjugate g* is the conjugate of f evaluated at the inverse transpose pullback A.dualMap.symm (y - b), shifted by the affine term y a - c - b a. This is the item's formula (4.13) in the chapter owner notation.

universe u v variable {V : Type u} {E : Type v} variable [AddCommGroup V] [Module ℝ V] variable [AddCommGroup E] [Module ℝ E] theorem conjugate_function_affine_change_of_variables (f : E → EReal) (A : V ≃ₗ[ℝ] E) (a : V) (b : Module.Dual ℝ V) (c : ℝ) : conjugate_function (fun x : V ↦ f (A (x - a)) + (b x : EReal) + (c : EReal)) = fun y ↦ conjugate_function f (A.dualMap.symm (y - b)) + ((y a - c - b a : ℝ) : EReal)

Proposition 4.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 4.5 is source-facing. Its owner abstractions already exist upstream: the indicator notation δ_ C / extendedIndicator in Chapter 2, the primal conjugate owner f∗ in Definition 4.1, and the distance-based potential in Example 2.5 as euclidean_distance_potential. This file therefore keeps the Fenchel-conjugacy identity specialized to that canonical project data, together with the pointwise companion theorem used to rewrite the identity at a chosen y. The real-valued distance potential is viewed as EReal-valued for conjugacy.

universe u open InnerProductSpace variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] recall conjugate_function_primal -- Semantic recall note: `lean_leansearch` did not surface a relevant project/mathlib owner theorem -- for this exact distance-potential conjugacy, so the file follows the local Chapter 4 precedent -- and states the proposition directly on the canonical primal conjugate surface `f∗`. -- Proof sketch: rewrite `euclidean_distance_potential C` as the supremum over `c ∈ C` of the -- affine functions `x ↦ ⟪x, c⟫ - 1/2 ‖c‖²`, identify the Euclidean pairing with the dual pairing -- through `toDualMap`, and then compute the conjugate by splitting into the cases `y ∈ C` and -- `y ∉ C`.

Theorem 4.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 4.5: the primal Fenchel conjugate of x ↦ exp x is y log y - y for y ≥ 0, and ⊤ for y < 0. The convention 0 log 0 = 0 is encoded by Real.log 0 = 0.

theorem exp_conjugate_function_eq (y : ℝ) : ((fun x : ℝ ↦ (Real.exp x : EReal))∗) y = if 0 ≤ y then ((y * Real.log y - y : ℝ) : EReal) else ⊤

Theorem 4.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 4.6 is source-facing in the chapter Fenchel-duality API. Its owner declarations are already upstream: effective_domain from Definition 2.1, IsProperExtendedRealFunction from Definition 2.5, is_convex_function from Definition 2.6, intrinsicInterior ℝ from Definition 3.7, and the Chapter 4 dual objects conjugate_function, fenchel_dual_objective, and fenchel_dual_problem_value from Definitions 4.1 and 4.8. This file therefore keeps only the duality and attainment statements, reusing those owners directly instead of repeating parallel local copies.

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

Proposition 4.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 4.7: the Fenchel conjugate intertwines positive scalar multiplication both for x ↦ α f x and for x ↦ α f ((1 / α) • x), yielding equations (4.14a) and (4.14b).

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] theorem conjugate_function_pos_real_scaling (f : E → EReal) (α : ℝ) (hα : 0 < α) : (conjugate_function (fun x ↦ (α : EReal) * f x) = fun y ↦ (α : EReal) * conjugate_function f ((1 / α) • y)) ∧ (conjugate_function (fun x ↦ (α : EReal) * f ((1 / α) • x)) = fun y ↦ (α : EReal) * conjugate_function f y)

Theorem 4.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 4.7: ruling out the value ⊥ for both summands is enough for the Fenchel conjugate of their infimal convolution to split as the pointwise sum of the conjugates.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] theorem conjugate_function_infimal_convolution_eq_add (h₁ h₂ : E → EReal) (hh₁_ne_bot : ∀ x, h₁ x ≠ ⊥) (hh₂_ne_bot : ∀ x, h₂ x ≠ ⊥) : conjugate_function (h₁ □ h₂) = conjugate_function h₁ + conjugate_function h₂

Definition 4.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 4.8: for proper extended-real-valued functions, the dual objective is the infimum form q(y) = inf_{x,z} L(x, z; y) of the split Lagrangian.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] theorem fenchel_dual_objective_eq_sInf_split_lagrangian (f g : E → EReal) (hf_proper : IsProperExtendedRealFunction f) (hg_proper : IsProperExtendedRealFunction g) (y : Module.Dual ℝ E) : fenchel_dual_objective f g y = sInf (Set.range fun xz : E × E ↦ fenchel_split_lagrangian f g xz.1 xz.2 y)

Proposition 4.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 4.8 is source-facing in the Chapter 4 conjugacy API. The chapter owner abstraction for Fenchel conjugates is already conjugate_function from Definition 4.1, so this file keeps only the negative-log barrier and its conjugacy formulas rather than a parallel local copy of the owner definition.

recall conjugate_function_primal

Theorem 4.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 4.8: if h₁ is a proper convex extended-real-valued function and h₂ is a real-valued convex function, then the Fenchel conjugate of the pointwise sum h₁ + h₂ is the infimal convolution of the conjugates h₁* and h₂*, where the real-valued perturbation enters the extended-real calculus through the canonical bridge h₂.toEReal. The real-valued convexity of h₂ is encoded by ConvexOn ℝ Set.univ h₂.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] theorem conjugate_function_add_eq_infimal_convolution (h₁ : E → EReal) (h₂ : E → ℝ) (hh₁_proper : IsProperExtendedRealFunction h₁) (hh₁_convex : is_convex_function h₁) (hh₂_convex : ConvexOn ℝ Set.univ h₂) : conjugate_function (fun x ↦ h₁ x + h₂.toEReal x) = conjugate_function h₁ □ conjugate_function h₂.toEReal

Proposition 4.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 4.9 is source-facing: it computes the conjugate of the hinge loss on ℝ. The core/canonical owner abstractions already live upstream as the indicator δ_ C from Chapter 2 and the primal-space conjugate f∗ from Definition 4.1. This file therefore keeps only the hinge-loss integrand as primitive data, states the conjugacy formula in the chapter's canonical primal-space notation, and provides the dual-space toDualMap ℝ ℝ specialization as a thin bridge companion.

open InnerProductSpace (toDualMap) recall conjugate_function_primal_apply

Theorem 4.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 4.9 is source-facing in the chapter infimal-convolution/conjugacy calculus. Its ambient notions are already owned upstream by the project declarations is_convex_function, infimal_convolution, and conjugate_function. The textbook right-hand side (h₁^* + h₂^*)^* starts from a function on the dual space E*, so the source-facing bridge back to the primal space is the canonical bidual equivalence Module.evalEquiv ℝ E : E ≃ₗ[ℝ] E**, whose forward map is Module.Dual.eval ℝ E. This file therefore reuses the chapter owners directly, together with the Chapter 2 bridge Function.toEReal, instead of repeating parallel local copies.

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

Proposition 4.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 4.10 is source-facing: its main content is that the scalar Fenchel objective x ↦ x * y - |x|^p / p attains its maximum. The core/canonical owner abstraction for Chapter 4 conjugacy statements is conjugate_function, and the reusable scalar-facing bridge/view surface in this chapter is its primal notation f∗. There is no additional primitive data here beyond that source integrand; the conjugacy formula below is derived API for downstream reuse.

recall conjugate_function_primal

Theorem 4.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 4.10 is source-facing in the chapter Fenchel/subdifferential API. A semantic lean_leansearch recall did not expose a single direct Fenchel--Young/subdifferential owner, and local verification shows that the core/canonical owners are already upstream: IsProperExtendedRealFunction from Definition 2.5, is_convex_function from Definition 2.6, subdifferential from Definition 3.2, and conjugate_function from Definition 4.1, together with the bridge theorems self_eq_pairing_sub_conjugate_iff_isMaxOn_dual_of_proper_closed_convex from Theorem 4.11 and isProperExtendedRealFunction_conjugate_function from Theorem 4.15. The primitive data here are only f, x, y, and the source-active hypotheses; the subdifferential and conjugate expressions are derived views through those owners, so this file keeps only the equivalence theorems and no parallel local wrappers.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] recall IsProperExtendedRealFunction

Proposition 4.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 4.11 is source-facing: its primitive data is the scalar integrand negative_rpow_extension. The chapter core/canonical owner for Fenchel conjugates is conjugate_function from Definition 4.1, and its scalar bridge/view owner is the primal-space notation f∗. The conjugacy formulas below therefore use that canonical scalar surface instead of reintroducing an explicit toDualMap ℝ ℝ wrapper.

recall conjugate_function_primal

Theorem 4.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 4.11 is source-facing: it rewrites Fenchel--Young equality in the textbook's argmax language. The owner abstractions are already upstream: conjugate_function from Definition 4.1 and Mathlib's IsMaxOn. This file is therefore only a bridge/view layer and reuses those owners directly instead of repeating local copies of the same convex-analysis data.

universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] recall conjugate_function -- Proof sketch: unfold `conjugate_function`; by `isMaxOn_univ_iff`, saying that `x` maximizes the -- affine-minus-`f` objective over `E` is exactly the statement that the value at `x` attains the -- supremum defining `conjugate_function f y`.

Proposition 4.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 4.12 is source-facing: its primitive data are the quadratic coefficients A, b, and c, and its main content is the explicit maximizer/value of the quadratic Fenchel objective on ℝ^n. The core/canonical owners are already Chapter 4's quadratic_affine_function for the primal quadratic and conjugate_function_primal / f∗ for its Euclidean Fenchel conjugate, so this file should reuse those owners rather than restating the same quadratic formula under anonymous functions.

universe u open Matrix open InnerProductSpace (toDualMap) variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) variable (A : Matrix (Fin n) (Fin n) ℝ) (b y : E) (c : ℝ) recall quadratic_affine_function

Theorem 4.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 4.12 is source-facing in the chapter Fenchel-conjugacy API. Its owner declarations are already upstream: IsProperExtendedRealFunction and is_convex_function from Chapter 2, the notation owner ∂ f(x) from Chapter 3, conjugate_function from Chapter 4, and the bridge/view theorems pairing_eq_add_conjugate_iff_eval_mem_subdifferential_conjugate, conjugate_function_eq_iff_isMaxOn_pairing_sub_function, and self_eq_pairing_sub_conjugate_iff_isMaxOn_dual_of_proper_closed_convex from the preceding theorem files. The only extra view language used here is Mathlib's IsMaxOn/IsMinOn over Set.univ, so this file states only the textbook argmax/argmin characterizations on top of those owners instead of introducing parallel local set wrappers. The nonempty-effective-domain part of properness is semantically active for parts (1) and (3): without it, f ≡ ⊤ gives an empty subdifferential ∂ f(x) but every dual vector is an argmax/minimizer on the right-hand side. For parts (2) and (4), properness is also semantically active because the owner bridge pairing_eq_add_conjugate_iff_eval_mem_subdifferential_conjugate requires IsProperExtendedRealFunction f: if f ≡ ⊥, then ∂ (conjugate_function f)(y) is empty while the primal argmax/image set is nonempty. Lower semicontinuity and convexity are still needed there to identify f** with f.

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

Proposition 4.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 4.13 is source-facing: the genuine new content here is the affine-range description of the conjugate of a positive-semidefinite quadratic together with the source-facing range witness for the finite branch. The core/canonical owners for the quadratic itself and for the Euclidean Fenchel conjugate on ℝ^n are already quadratic_affine_function and conjugate_function_primal / f∗, so this file stays on the canonical EuclideanSpace ℝ (Fin n) owner surface instead of introducing local identity-matrix instance plumbing or a choice-built pseudoinverse wrapper.

universe u open Matrix open Matrix.PosDef variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) recall quadratic_affine_function

Theorem 4.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 4.13: for a convex real-valued function, the following are equivalent for the given Lipschitz bound L: (i) f is globally L-Lipschitz, (ii) every subgradient of f has norm at most L, and (iii) the effective domain of the conjugate f* is contained in the closed dual ball of radius L.

universe u open Metric variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] theorem convex_lipschitz_tfae_subdifferential_norm_le_conjugate_domain_subset_closedBall (f : E → ℝ) (hf : ConvexOn ℝ Set.univ f) (L : NNReal) : List.TFAE [LipschitzWith L f, ∀ x : E, ∀ g ∈ subdifferentialAt f x, ‖g‖ ≤ L, effective_domain (fun y : StrongDual ℝ E ↦ conjugate_function (fun x ↦ (f x : EReal)) y) ⊆ closedBall (0 : StrongDual ℝ E) L]

Proposition 4.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 4.14: the conjugate of the coordinatewise negative entropy on ℝ^n is the sum of the exponentials exp (y_i - 1) over the coordinates.

open Matrix open scoped BigOperators variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem negative_entropy_function_conjugate_eq_sum_exp (y : E) : ((negative_entropy_function n)∗) y = ∑ i, ((Real.exp (y i - 1) : ℝ) : EReal)

Proposition 4.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 4.15: the Fenchel conjugate of the separable sum of the scalar negative-log barrier, equivalently by [sum_negative_log_barrier_apply] the textbook barrier x ↦ -∑ i, log (x i) on positiveOrthant n and ∞ outside, is -n - ∑ i, log (-y i) on the negative orthant and ∞ otherwise. The dual argument is expressed through the Euclidean pairing dotProductEquiv.

open Matrix open scoped BigOperators variable {n : ℕ} local notation "E" => Fin n → ℝ theorem sum_negative_log_barrier_conjugate_eq (y : E) : conjugate_function (sum_negative_log_barrier n) (dotProductEquiv ℝ (Fin n) y) = if ∀ i : Fin n, y i < 0 then ((-(n : ℝ) - ∑ i : Fin n, Real.log (-y i) : ℝ) : EReal) else ⊤

Theorem 4.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 4.15 is source-facing in the Chapter 4 conjugacy API. Its primitive data are the owner predicates IsProperExtendedRealFunction and is_convex_function, while the conjugate is the Chapter 4 owner conjugate_function on the dual space from Definition 4.1.

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

Proposition 4.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 4.16: the Fenchel conjugate of the negative entropy on the unit simplex is the log-sum-exp function.

open Matrix open scoped BigOperators variable {n : ℕ} variable [NeZero n] theorem negative_entropy_on_stdSimplex_conjugate_eq_log_sum_exp (y : Fin n → ℝ) : conjugate_function (negative_entropy_on_stdSimplex n) (dotProductEquiv ℝ (Fin n) y) = ((Real.log (∑ j, Real.exp (y j)) : ℝ) : EReal)

Proposition 4.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 4.17: the Fenchel conjugate of the log-sum-exp function on ℝ^n, evaluated via the Euclidean pairing dotProductEquiv, is the simplex-constrained negative entropy negative_entropy_on_stdSimplex n. Equivalently, this is the entropy expression ∑ i, y_i log y_i on the standard simplex Δ_n = stdSimplex ℝ (Fin n) and ∞ outside the simplex.

open Matrix open scoped BigOperators variable {n : ℕ} local notation "E" => Fin n → ℝ variable [NeZero n] theorem log_sum_exp_function_conjugate : (fun y : E ↦ conjugate_function log_sum_exp_function (dotProductEquiv ℝ (Fin n) y)) = negative_entropy_on_stdSimplex n

Proposition 4.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 4.18 is source-facing in the chapter norm-conjugacy API. The owner abstractions already live upstream: Chapter 2 owns the indicator function extendedIndicator, and the continuous-dual Fenchel conjugate on normed spaces is already present upstream in Chapter 4 as conjugate_function. The primitive data here are therefore only the norm objective and the dual closed unit ball; the proposition itself is the source-facing identification between those owner objects.

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

Proposition 4.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 4.19: for the function equal to -√(1 - ‖x‖²) on the closed unit ball and ∞ outside it, the Fenchel conjugate at a dual vector y ∈ E* is √(‖y‖_*² + 1).

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] theorem conjugate_negative_sqrt_one_sub_norm_sq_extension_eq_sqrt_dualNorm_sq_add_one (y : Module.Dual ℝ E) : conjugate_function negative_sqrt_one_sub_norm_sq_extension y = ((Real.sqrt (dualNorm y ^ (2 : ℕ) + 1) : ℝ) : EReal)

Proposition 4.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 4.20: for α > 0, if f_α is the function equal to -√(α² - ‖x‖²) on the closed ball of radius α and ∞ outside, then its Fenchel conjugate at y ∈ E* is α √(1 + ‖y‖_*²).

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] omit [FiniteDimensional ℝ E] in -- Proof sketch: for `α > 0`, the bound `‖x‖ ≤ α` is equivalent to -- `‖(1 / α) • x‖ ≤ 1`, and the radical rescales as -- `α * √(1 - ‖(1 / α) • x‖²) = √(α² - ‖x‖²)`. Thus evaluating the radius-`α` barrier at `x` -- agrees with the positive scalar multiple/precomposition of the unit-ball owner from -- Proposition 4.19. theorem conjugate_negative_sqrt_alpha_sq_sub_norm_sq_extension_eq_alpha_mul_sqrt_one_add_dualNorm_sq (α : ℝ) (hα : 0 < α) (y : Module.Dual ℝ E) : conjugate_function (negative_sqrt_alpha_sq_sub_norm_sq_extension α) y = ((α * Real.sqrt (1 + dualNorm y ^ (2 : ℕ)) : ℝ) : EReal)

Proposition 4.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 4.21 is source-facing in the chapter conjugacy API. The owner abstractions for the conjugate and the dual norm already live upstream as conjugate_function and dualNorm, so the only primitive data local to this file are the specific model function x ↦ √(α² + ‖x‖²) and the source-facing conjugacy formula for that function.

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

Proposition 4.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 4.22 (prop:4.22): for f(x) = (1 / 2) * ‖x‖ ^ 2, the Fenchel conjugate f* is y ↦ (1 / 2) * ‖y‖_* ^ 2.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E] theorem half_squared_norm_conjugate_eq_half_dualNorm_sq (y : Module.Dual ℝ E) : conjugate_function (fun x : E ↦ ((((1 / 2 : ℝ) * ‖x‖ ^ (2 : ℕ)) : ℝ) : EReal)) y = ((((1 / 2 : ℝ) * dualNorm y ^ (2 : ℕ)) : ℝ) : EReal)

Proposition 4.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 4.23 is source-facing: it states the textbook formula h₁ + h₂ = (h₁^* □ h₂^*)^* for a proper closed convex extended-real-valued function plus an everywhere-finite convex perturbation. The core/canonical owners are already upstream: Chapter 2's IsProperExtendedRealFunction, is_convex_function, and infimal_convolution, Mathlib's LowerSemicontinuous, and Chapter 4's conjugate_function and biconjugate_function. The explicit infimal-convolution/conjugate formula is therefore the main source-facing declaration here, while the pure owner-form biconjugation equality is only a thin companion view. Primitive data: the functions h₁, h₂ and the source hypotheses hh₁_proper, hh₁_closed, hh₁_convex, hh₂_convex. Derived API: the explicit conjugate/infimal-convolution identity and its owner-form biconjugation companion. The first theorem reuses the chapter owner conjugate_function_add_eq_infimal_convolution, while the companion theorem below is the thin proper/closed/convex owner view on the summed function and therefore uses the repository theorem biconjugate_function_eq_self_of_proper_closed_convex.

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