Chapter 15 — Fenchel–Rockafellar Duality

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

Proposition 15.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.1: for f, g ∈ Γ₀(H), the Fenchel conjugate of the pointwise sum f + g is the Fenchel biconjugate of f* □ g*.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable (f g : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) theorem conjugate_pointwiseAdd_eq_biconjugate_infimalConvolution_conjugates : (f + g).asEReal∗ = (gammaZeroConjugate f hf □ gammaZeroConjugate g hg)∗∗

Proposition 15.2

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.2: if f and g belong to Γ₀(H) and 0 ∈ core (dom f - dom g), then the Fenchel conjugate of the pointwise sum f + g is f^* □ g^*, and the companion theorem shows that this infimal convolution is exact.

open Set open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem conjugate_pointwiseAdd_eq_infimalConvolution_conjugates_of_zero_mem_core_sub_effectiveDomain (f g : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) (hcore : (0 : H) ∈ core (effectiveDomain f - effectiveDomain g)) : (f + g).asEReal∗ = f.asEReal∗ □ g.asEReal∗

Theorem 15.3

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 15.3: (Attouch--Brézis) if f, g ∈ Γ₀(H) and 0 ∈ sri (effectiveDomain f - effectiveDomain g), then f + g ∈ Γ₀(H).

open Set open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} [TopologicalSpace H] [AddCommGroup H] [Module ℝ H] [SequentialSpace H] [IsTopologicalAddGroup H] [ContinuousSMul ℝ H] omit [SequentialSpace H] in -- Proof sketch: membership in `sri (effectiveDomain f - effectiveDomain g)` implies membership in -- `effectiveDomain f - effectiveDomain g`, so `0 = x - y` for some `x ∈ effectiveDomain f` and -- `y ∈ effectiveDomain g`; hence `x = y`, and the effective domains intersect. theorem pointwiseAdd_mem_gammaZero_of_zero_mem_sri_sub_effectiveDomain (f g : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) (hsri : (0 : H) ∈ sri (effectiveDomain f - effectiveDomain g)) : f + g ∈ Γ₀(H)

Remark 15.4

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Remark 15.4 (1): on the explicit ℝ² example, the conjugate-of-a-sum formula from Theorem 15.3 fails even though cone (dom f - dom g) is a closed cone; the missing hypothesis is that this cone be a closed linear subspace.

open Set open scoped InnerProductSpace Pointwise universe u namespace ERealFunction theorem attouchBrezis_counterexample_closedCone_not_closedLinearSubspace : let E := EuclideanSpace ℝ (Fin 2) let Q : Set E := {x | 0 ≤ x 0 ∧ 0 ≤ x 1} let L : Set E := {x | x 0 = 0} let f : E → EReal := fun x ↦ if x ∈ Q then (((-Real.sqrt (x 0 * x 1) : ℝ) : EReal)) else ⊤ let g : E → EReal := (ι[L]).asEReal let Rnonpos : Set E := {x | x 1 ≤ 0} let Rneg : Set E := {x | x 1 < 0} ((f + g)∗ = (ι[Rnonpos]).asEReal ∧ infimalConvolution f∗ g∗ = (ι[Rneg]).asEReal) ∧ (IsClosed (cone (dom f - dom g)) ∧ ¬ ∃ V : Submodule ℝ E, cone (dom f - dom g) = (V : Set E))

Proposition 15.5

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.5: if f and g belong to Γ₀(H) and one of the five regularity alternatives (i) through (v) holds, then the origin belongs to the strong relative interior of dom f - dom g. The source also lists dom f ∩ dom g ≠ ∅, but the Chapter 6 route for clauses (ii) through (v) makes that extra hypothesis redundant. Clause (i) is kept in the closed-span form from Definition 6.9.

open Set open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem zero_mem_strongRelativeInterior_sub_effectiveDomain_of_mem_gammaZero_of_regularity {f g : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) (hreg : effectiveDomainStrongRelativeInteriorRegularity f g) : (0 : H) ∈ sri (effectiveDomain f - effectiveDomain g)

Remark 15.6

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Remark 15.6: the regularity conditions in Proposition 15.5 are not equivalent. In ℝ², for the domain pair ℝ × {0} and {0} × ℝ, the finite-dimensional set-level form of clause (iv), namely interior C ∩ D ≠ ∅, fails while clause (iii) holds. For the pair [0,1] × {0} and [0,1] × {0}, clause (ii) fails while (15.9) and clause (v) hold.

open Set open scoped Pointwise -- Proof sketch: compute the explicit difference sets in `ℝ²`. For the axis example, the -- difference is all of `ℝ²`, so clause (iii) holds, while the horizontal axis has empty interior, -- which is the finite-dimensional set-level rendering of clause (iv) via Corollary 8.39. For the -- segment example, the difference set is the horizontal segment `[-1,1] × {0}`, whose origin lies -- in its strong relative interior and whose relative interior is nonempty, while the core -- condition fails. theorem attouchBrezisRegularityConditions_not_equivalent : let horizontalAxis : Set (ℝ × ℝ) := (Set.univ : Set ℝ) ×ˢ ({0} : Set ℝ) let verticalAxis : Set (ℝ × ℝ) := ({0} : Set ℝ) ×ˢ (Set.univ : Set ℝ) let segment : Set (ℝ × ℝ) := Set.Icc (0 : ℝ) 1 ×ˢ ({0} : Set ℝ) (¬ (interior horizontalAxis ∩ verticalAxis).Nonempty ∧ (0 : ℝ × ℝ) ∈ interior (horizontalAxis - verticalAxis)) ∧ (¬ ((0 : ℝ × ℝ) ∈ core (segment - segment)) ∧ (0 : ℝ × ℝ) ∈ sri (segment - segment) ∧ (ri segment ∩ ri segment).Nonempty)

Proposition 15.7

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.7 (1): under any of the five source regularity alternatives, the infimal convolution f □ g is exact.

open Set open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] namespace InfimalConvolutionRegularity -- Proof sketch: use the fifth disjunct in the definition of -- `InfimalConvolutionRegularity`. theorem exact (f g : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) (hreg : InfimalConvolutionRegularity f g) : infimalConvolution.Exact f g

Corollary 15.8

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.8: if φ, ψ ∈ Γ₀(H × K) and 0 ∈ sri (Prod.fst '' (effectiveDomain φ - effectiveDomain ψ)), then the Fenchel conjugate of the second-variable fiberwise infimal convolution p ↦ ((z ↦ φ(x, z)) □ (z ↦ ψ(x, z))) y, where p = (x, y) in H × K, is obtained by taking the infimal convolution in the first variable of the conjugate slices with the second dual variable fixed.

open Set open scoped InnerProductSpace Pointwise universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem conjugate_secondVariableFiberwiseInfimalConvolution_eq_infimalConvolution_conjugateSlices (φ ψ : H × K → Set.Ioi (⊥ : EReal)) (hφ : φ ∈ Γ₀(H × K)) (hψ : ψ ∈ Γ₀(H × K)) (hsri : (0 : H) ∈ sri (Prod.fst '' (effectiveDomain φ - effectiveDomain ψ))) : (fun p : H × K ↦ ((fun z : K ↦ (φ (p.1, z) : EReal)) □ fun z ↦ (ψ (p.1, z) : EReal)) p.2)∗ = fun q : H × K ↦ ((fun u : H ↦ φ.asEReal∗ (u, q.2)) □ fun u ↦ ψ.asEReal∗ (u, q.2)) q.1

Proposition 15.9

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.9 (1): every primal value dominates the negative dual value, i.e. -fenchelDualObjective f g u ≤ primalObjective f g x.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: if either effective domain is empty, then the corresponding function is -- identically `+∞`, so the inequality is immediate. Otherwise apply the Fenchel--Young inequality -- to `f` at `(x, -u)` and to `g` at `(x, u)`, then add the resulting inequalities and simplify the -- pairing terms, which cancel. theorem primalObjective_ge_neg_dualObjective (f g : H → Set.Ioi (⊥ : EReal)) (x u : H) : -fenchelDualObjective f g u ≤ primalObjective f g x

Definition 15.10

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 15.10: the duality gap attached to the primal objective x ↦ f(x) + g(x) and the dual objective u ↦ f^*(-u) + g^*(u) is 0 in the exceptional case μ = -μ* ∈ {±∞}, and otherwise it is the sum μ + μ* of the primal and dual optimal values.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] def dualityGap (f g : H → Set.Ioi (⊥ : EReal)) : EReal := if primalOptimalValue f g = -dualOptimalValue f g ∧ (primalOptimalValue f g = (⊥ : EReal) ∨ primalOptimalValue f g = ⊤) then 0 else primalOptimalValue f g + dualOptimalValue f g

Proposition 15.12

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.12 (1): the primal optimal value μ is at least the negative of the dual optimal value μ*.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: Proposition 15.9 (2) is already the indexed-infimum inequality for the canonical -- primal and dual objectives. Rewrite those indexed infima as `primalOptimalValue f g` and -- `dualOptimalValue f g` using the owner API from Definition 15.10. theorem primalOptimalValue_ge_neg_dualOptimalValue (f g : H → Set.Ioi (⊥ : EReal)) : primalOptimalValue f g ≥ -dualOptimalValue f g

Proposition 15.13

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.13: if f, g ∈ Γ₀(H) and 0 ∈ sri (dom f - dom g), then the primal optimal value is the negative of the minimum of the Fenchel dual objective u ↦ f^*(-u) + g^*(u).

open Set open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem exists_mem_argmin_fenchelDualObjective_eq_neg_primalOptimalValue_of_zero_mem_sri_sub_effectiveDomain (f g : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) (hsri : (0 : H) ∈ sri (effectiveDomain f - effectiveDomain g)) : ∃ u ∈ Argmin (fenchelDualObjective f g), primalOptimalValue f g = -(fenchelDualObjective f g u)

Corollary 15.14

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.14: if f ∈ Γ₀(H) and K is a closed convex cone with 0 ∈ sri (effectiveDomain f - K), then the infimum of f over K is the negative of the minimum of the Fenchel conjugate over the dual cone Kᵒ⊕.

open Set open scoped InnerProductSpace Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem exists_mem_argminOn_conjugate_dualCone_eq_neg_sInf_image_of_zero_mem_sri_sub_effectiveDomain (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (K : Set H) (hK_closed : IsClosed K) (hK_convex : Convex ℝ K) (hK_cone : IsCone K) (hsri : (0 : H) ∈ sri (effectiveDomain f - K)) : ∃ u ∈ Argmin[Kᵒ⊕] f.asEReal∗, sInf (f.asEReal '' K) = -f.asEReal∗ u

Corollary 15.15

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.15: if f, g ∈ Γ₀(H), if 0 ∈ sri (dom f - dom g), if f + g ≥ 0, and if g^* = g ∘ L for a bounded linear operator L, then there exists v ∈ H such that f^*(-v) + g(Lv) ≤ 0.

open Set open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem exists_dual_vector_le_zero_of_pointwiseAdd_nonneg_and_conjugate_eq_comp (f g : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) (hsri : (0 : H) ∈ sri (effectiveDomain f - effectiveDomain g)) (L : H →L[ℝ] H) (hfg_nonneg : ∀ x : H, (0 : EReal) ≤ primalObjective f g x) (hg_conj : g.asEReal∗ = g.asEReal ∘ L) : ∃ v : H, f.asEReal∗ (-v) + (g (L v) : EReal) ≤ 0

Corollary 15.16

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.16: if f, g ∈ Γ₀(H), if 0 ∈ sri (dom f - dom g), if g^* = gᵛ, and if f + g ≥ 0, then there exists v ∈ H such that for every x ∈ H, f(x) + g(x) ≥ g(x) + ⟪x, v⟫ + g(v) ≥ 0.

open Set open scoped InnerProductSpace Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable [CompleteSpace H] -- Proof sketch: apply Corollary 15.15 with `L = -ContinuousLinearMap.id ℝ H`; the -- reflected-conjugate hypothesis rewrites its conclusion to `f.asEReal∗ v + g(v) ≤ 0`. Then -- combine the two explicit-inequality lemmas and rewrite `primalObjective f g x` as -- `f(x) + g(x)`. theorem exists_dual_vector_with_explicit_bounds_of_primalObjective_nonneg_and_conjugate_eq_reflection (f g : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) (hsri : (0 : H) ∈ sri (effectiveDomain f - effectiveDomain g)) (hg_reflected : g.asEReal∗ = g.asERealᵛ) (hfg_nonneg : ∀ x : H, (0 : EReal) ≤ primalObjective f g x) : ∃ v : H, ∀ x : H, (g x : EReal) + (((⟪x, v⟫_ℝ : ℝ) : EReal) + (g v : EReal)) ≤ (f x : EReal) + (g x : EReal) ∧ (0 : EReal) ≤ (g x : EReal) + (((⟪x, v⟫_ℝ : ℝ) : EReal) + (g v : EReal))

Corollary 15.17

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.17: if f ∈ Γ₀(H) and f + (1/2)‖·‖² is pointwise nonnegative, then some translate of the quadratic function is pointwise dominated by f + (1/2)‖·‖².

open Set open scoped InnerProductSpace Pointwise universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem exists_halfSquaredNorm_sub_le_pointwiseAdd (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (h_nonneg : ∀ x : H, (0 : EReal) ≤ (f x : EReal) + (halfSquaredNorm x : EReal)) : ∃ w : H, ∀ x : H, (halfSquaredNorm (x - w) : EReal) ≤ (f x : EReal) + (halfSquaredNorm x : EReal)

Proposition 15.18

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.18 (1): every primal value f(x) + g(Lx) dominates the negative of the corresponding adjoint-based composite dual objective.

open scoped InnerProductSpace universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] -- Proof sketch: apply the Fenchel--Young inequality to `f` at `(x, -L.adjoint v)` and to `g` at -- `(L x, v)`, then rewrite the first pairing with `ContinuousLinearMap.adjoint_inner_right` so the -- two pairings cancel. This is the composite-objective analogue of Proposition 15.9 in the -- source-facing adjoint form from Definition 15.19. theorem compositePrimalObjective_ge_neg_compositeDualObjective (f : H → Set.Ioi (⊥ : EReal)) (g : K → Set.Ioi (⊥ : EReal)) (L : H →L[ℝ] K) (x : H) (v : K) : compositePrimalObjective f g L x ≥ -(compositeDualObjective f g L v)

Definition 15.19

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 15.19: for the primal problem min_x f(x) + g(Lx) and the dual problem min_v f^*(-L^*v) + g^*(v), the duality gap is 0 in the exceptional case μ = -μ* ∈ {±∞} and otherwise equals μ + μ*.

universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] variable [CompleteSpace H] [CompleteSpace K] def compositeDualityGap (f : H → Set.Ioi (⊥ : EReal)) (g : K → Set.Ioi (⊥ : EReal)) (L : H →L[ℝ] K) : EReal := if compositePrimalOptimalValue f g L = -compositeDualOptimalValue f g L ∧ (compositePrimalOptimalValue f g L = (⊥ : EReal) ∨ compositePrimalOptimalValue f g L = ⊤) then 0 else compositePrimalOptimalValue f g L + compositeDualOptimalValue f g L

Proposition 15.21

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.21 (1): the weak duality inequality for the composite primal-dual pair is exactly the owner theorem already established in Proposition 15.18.

universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] variable (f : H → Set.Ioi (⊥ : EReal)) (g : K → Set.Ioi (⊥ : EReal)) (L : H →L[ℝ] K) recall compositePrimalOptimalValue_ge_neg_compositeDualOptimalValue -- Proof sketch: unfold `compositeDualityGap`; in the exceptional branch the gap is `0`, and in -- the non-exceptional branch it is `μ + μ*`, which is nonnegative by clause (1).

Proposition 15.22

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.22: if f ∈ Γ₀(H), g ∈ Γ₀(K), and 0 ∈ core (effectiveDomain g - L '' effectiveDomain f), then the infimum of the composite primal objective x ↦ f x + g (L x) equals the negative of the minimum of the dual objective v ↦ f^*(-L^* v) + g^*(v).

open Set open scoped Pointwise universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem exists_mem_argmin_compositeDualObjective_of_zero_mem_core_sub_image_effectiveDomain (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (g : K → Set.Ioi (⊥ : EReal)) (hg : g ∈ Γ₀(K)) (L : H →L[ℝ] K) (hcore : (0 : K) ∈ Set.core (effectiveDomain g - L '' effectiveDomain f)) : ∃ v ∈ Argmin (compositeDualObjective f g L), compositePrimalOptimalValue f g L = -(compositeDualObjective f g L v)

Theorem 15.23

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 15.23: if f ∈ Γ₀(H), g ∈ Γ₀(K), and 0 ∈ sri (effectiveDomain g - L '' effectiveDomain f), then the composite primal optimal value is the negative of the minimum of the owner dual objective compositeDualObjective f g L, i.e. of v ↦ f^*(-L^* v) + g^*(v).

open Set open scoped Pointwise universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem exists_mem_argmin_compositeDualObjective_eq_neg_compositePrimalOptimalValue_of_zero_mem_sri_sub_image_effectiveDomain (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (g : K → Set.Ioi (⊥ : EReal)) (hg : g ∈ Γ₀(K)) (L : H →L[ℝ] K) (hsri : (0 : K) ∈ sri (effectiveDomain g - L '' effectiveDomain f)) : ∃ v ∈ Argmin (compositeDualObjective f g L), compositePrimalOptimalValue f g L = -(compositeDualObjective f g L v)

Proposition 15.24

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.24: let f ∈ Γ₀(H), let g ∈ Γ₀(K), and let L : H →L[ℝ] K. If one of the ten source regularity alternatives holds, then `0 ∈ sri (effectiveDomain g - L '' effectiveDomain f)`.

open Set open scoped Pointwise Topology universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem zero_mem_strongRelativeInterior_sub_image_effectiveDomain_of_regularity {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) {g : K → Set.Ioi (⊥ : EReal)} (hg : g ∈ Γ₀(K)) (L : H →L[ℝ] K) (hregular : effectiveDomainSubImageStrongRelativeInteriorRegularity f g L) : (0 : K) ∈ sri (effectiveDomain g - L '' effectiveDomain f)

Definition 15.24.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 15.24.1 (1): a subset of H is polyhedral when it is a finite intersection of closed half-spaces.

universe u namespace Set variable {H : Type u} [SeminormedAddCommGroup H] [NormedSpace ℝ H] def IsPolyhedral (C : Set H) : Prop := ∃ t : Finset ((H →L[ℝ] ℝ) × ℝ), C = ⋂ p ∈ t, closedHalfspace p.1 p.2

Fact 15.25

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Fact 15.25: if f ∈ Γ₀(H), g ∈ Γ₀(K), K is finite-dimensional, g is polyhedral, and either (i) effectiveDomain g meets ri (L '' effectiveDomain f) or (ii) H is finite-dimensional, f is polyhedral, and effectiveDomain g meets L '' effectiveDomain f, then the composite primal optimal value is the negative of the minimum of the dual objective v ↦ f^*(-L^* v) + g^*(v).

open Set open scoped Pointwise universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem exists_mem_argmin_compositeDualObjective_eq_neg_compositePrimalOptimalValue_of_polyhedral_regularity (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (g : K → Set.Ioi (⊥ : EReal)) (hg : g ∈ Γ₀(K)) (L : H →L[ℝ] K) [FiniteDimensional ℝ K] (hg_polyhedral : Polyhedral g.asEReal) (hregular : (effectiveDomain g ∩ ri (L '' effectiveDomain f)).Nonempty ∨ (FiniteDimensional ℝ H ∧ Polyhedral f.asEReal ∧ (effectiveDomain g ∩ L '' effectiveDomain f).Nonempty)) : ∃ v ∈ Argmin (compositeDualObjective f g L), compositePrimalOptimalValue f g L = -(compositeDualObjective f g L v)

Proposition 15.26

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 15.26 (1): if f ∈ Γ₀(H) and g ∈ Γ₀(K) with effectiveDomain g ∩ L '' effectiveDomain f ≠ ∅, then the conjugate of the composite primal objective is the Fenchel biconjugate of f* □ (L* ▷ g*).

open scoped InnerProductSpace universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] -- Proof sketch: combine the Chapter 13 formula for the conjugate of a sum with linear -- precomposition and the biconjugacy identity for `Γ₀` functions, then identify the resulting -- right-hand side with the canonical `EReal`-valued dual infimal convolution -- `f.asEReal∗ □ (L.adjoint ▷ g.asEReal∗)`. theorem conjugate_pointwiseAddComp_eq_biconjugate_dualInfimalConvolution (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (g : K → Set.Ioi (⊥ : EReal)) (hg : g ∈ Γ₀(K)) (L : H →L[ℝ] K) (hdom : (effectiveDomain g ∩ L '' effectiveDomain f).Nonempty) : (compositePrimalObjective f g L)∗ = (f.asEReal∗ □ (L.adjoint ▷ g.asEReal∗))∗∗

Theorem 15.27

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 15.27: if f ∈ Γ₀(H), g ∈ Γ₀(K), and either (i) 0 ∈ sri (effectiveDomain g - L '' effectiveDomain f), or (ii) K is finite-dimensional, g is polyhedral, and effectiveDomain g ∩ ri (L '' effectiveDomain f) is nonempty, or (iii) H and K are finite-dimensional, f and g are polyhedral, and effectiveDomain g ∩ L '' effectiveDomain f is nonempty, then (compositePrimalObjective f g L)∗ = f^* □ (L^* ▷ g^*).

open Set open scoped Pointwise InnerProductSpace universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] variable (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (g : K → Set.Ioi (⊥ : EReal)) (hg : g ∈ Γ₀(K)) (L : H →L[ℝ] K) (hregular : (0 : K) ∈ sri (effectiveDomain g - L '' effectiveDomain f) ∨ (FiniteDimensional ℝ K ∧ Polyhedral g.asEReal ∧ (effectiveDomain g ∩ ri (L '' effectiveDomain f)).Nonempty) ∨ (FiniteDimensional ℝ K ∧ Polyhedral g.asEReal ∧ FiniteDimensional ℝ H ∧ Polyhedral f.asEReal ∧ (effectiveDomain g ∩ L '' effectiveDomain f).Nonempty)) -- Proof sketch: combine Proposition 15.26 with the source-facing regularity split. Branch `(i)` -- uses Theorem 15.23, while branches `(ii)` and `(iii)` route through Fact 15.25. theorem conjugate_addComp_eq_dualInfimalConvolution_of_regular : (compositePrimalObjective f g L)∗ = f.asEReal∗ □ (L.adjoint ▷ g.asEReal∗)

Corollary 15.28

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.28 reuses the Chapter 13 owner identity conjugate_comp_eq_adjointInfimalPostcomposition; the Chapter 15 regularity package is only needed for the attainment/exactness conclusion below.

open Set open scoped Pointwise InnerProductSpace universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] variable (g : K → Set.Ioi (⊥ : EReal)) (hg : g ∈ Γ₀(K)) (L : H →L[ℝ] K) #check conjugate_comp_eq_adjointInfimalPostcomposition -- Proof sketch: evaluate the Chapter 13 owner identity -- `conjugate_comp_eq_adjointInfimalPostcomposition` at `u` and unfold `infimalPostcomposition`.

Example 15.29

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 15.29: if C ⊆ H and D ⊆ K are closed convex and 0 ∈ sri (D - L '' C), then the primal value inf_{x ∈ C} sup_{v ∈ D} ⟪Lx, v⟫ equals the attained dual value max_{v ∈ D} inf_{x ∈ C} ⟪Lx, v⟫, written here as sInf ((fun x ↦ σ[D] (L x)) '' C) and a maximizer of v ↦ innerInfimumOn C (L.adjoint v) on D.

open Set open scoped InnerProductSpace Pointwise universe u v namespace ERealFunction variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem exists_dualMaximizer_inf_inner_eq_inf_supportFunction_of_zero_mem_sri_sub_image (C : Set H) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (D : Set K) (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) (L : H →L[ℝ] K) (hsri : (0 : K) ∈ sri (D - L '' C)) : ∃ v ∈ D, IsMaxOn (fun w : K ↦ innerInfimumOn C (L.adjoint w)) D v ∧ sInf ((fun x : H ↦ σ[D] (L x)) '' C) = innerInfimumOn C (L.adjoint v)

Corollary 15.30

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.30: the bilinear minimax equality min_{x ∈ C} max_{v ∈ D} ⟪Lx, v⟫ = max_{v ∈ D} min_{x ∈ C} ⟪Lx, v⟫ is attained by some x ∈ C and v ∈ D when C and D are nonempty bounded closed subsets of real Hilbert spaces.

universe u v open scoped InnerProductSpace Pointwise namespace ERealFunction variable {E : Type u} {F : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable [NormedAddCommGroup F] [InnerProductSpace ℝ F] [CompleteSpace F] variable {C : Set E} {D : Set F} variable (L : E →L[ℝ] F) -- Proof sketch: pass from `C` and `D` to their closed convex hulls, which preserve the direct -- bilinear slice-value functions via the support-function and inner-infimum invariance results -- from Chapters 7 and 11 together with the image rewrites from Example 15.29. Then use the -- attained owner equality on the closed convex hulls and weak compactness of bounded closed convex -- sets to recover a primal minimizer and a dual maximizer for the original bilinear payoff. theorem vonNeumann_minimax_inner_eq (hC_nonempty : C.Nonempty) (hC_bounded : Bornology.IsBounded C) (hC_closed : IsClosed C) (hD_nonempty : D.Nonempty) (hD_bounded : Bornology.IsBounded D) (hD_closed : IsClosed D) : ∃ x ∈ C, ∃ v ∈ D, IsMinOn (fun y : E ↦ sSup ((fun w : F ↦ (⟪L y, w⟫_ℝ : EReal)) '' D)) C x ∧ IsMaxOn (fun w : F ↦ sInf ((fun y : E ↦ (⟪L y, w⟫_ℝ : EReal)) '' C)) D v ∧ sInf ((fun y : E ↦ sSup ((fun w : F ↦ (⟪L y, w⟫_ℝ : EReal)) '' D)) '' C) = sSup ((fun w : F ↦ sInf ((fun y : E ↦ (⟪L y, w⟫_ℝ : EReal)) '' C)) '' D) ∧ sSup ((fun w : F ↦ (⟪L x, w⟫_ℝ : EReal)) '' D) = sInf ((fun y : E ↦ (⟪L y, v⟫_ℝ : EReal)) '' C)

Corollary 15.31

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.31 (1): the polar cone of C ∩ L ⁻¹' D is the closure of the sum of the polar cone of C and the adjoint image of the polar cone of D.

open scoped InnerProductSpace Pointwise universe u v namespace Set variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] -- Proof sketch: apply Proposition 6.35 to the closed convex cones `C` and `L ⁻¹' D`. The -- preimage cone is again nonempty, closed, convex, and a cone because both cones contain `0`. -- Then identify `(L ⁻¹' D)ᵒ⊖` with `closure (L.adjoint '' (Dᵒ⊖))` via Theorem 6.37(1), and absorb -- the extra closure inside the outer closure of the sum. theorem polarCone_inter_preimage_eq_closure_add_adjoint_image_polarCone (C : Set H) (D : Set K) (L : H →L[ℝ] K) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (hC_cone : IsCone C) (hD_nonempty : D.Nonempty) (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) (hD_cone : IsCone D) : (C ∩ L ⁻¹' D)ᵒ⊖ = closure (Cᵒ⊖ + L.adjoint '' (Dᵒ⊖))

Corollary 15.32

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.32: if D is a closed convex cone and D - Set.range L is a closed linear subspace, then the polar cone of L ⁻¹' D is exactly the adjoint image of the polar cone of D.

open scoped InnerProductSpace Pointwise universe u v namespace Set variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] variable (D : Set K) (L : H →L[ℝ] K) -- Proof sketch: specialize Corollary 15.31(2) to `C = univ`, rewrite `L '' univ` as `Set.range L`, -- and simplify the added term `univᵒ⊖` to `{0}` so the pointwise sum collapses to the adjoint -- image alone. theorem polarCone_preimage_eq_adjoint_image_polarCone_of_closed_subspace_sub_range (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) (hD_cone : IsCone D) (hsubspace : D - Set.range L = (Submodule.span ℝ (D - Set.range L) : Set K)) (hsubspace_closed : IsClosed (D - Set.range L)) : (L ⁻¹' D)ᵒ⊖ = L.adjoint '' (Dᵒ⊖)

Corollary 15.33

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.33: for closed linear subspaces C and D, the subspace sum corresponding to L(C) + D is closed if and only if the orthogonal-complement sum Cᗮ + L^*(Dᗮ) is closed.

open ContinuousLinearMap open scoped InnerProductSpace Pointwise universe u v variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem isClosed_map_sup_iff_isClosed_orthogonal_sup_adjoint_map_orthogonal (C : Submodule ℝ H) (D : Submodule ℝ K) (L : H →L[ℝ] K) (hC_closed : IsClosed (C : Set H)) (hD_closed : IsClosed (D : Set K)) : IsClosed (((C.map L.toLinearMap) ⊔ D : Submodule ℝ K) : Set K) ↔ IsClosed (((Cᗮ) ⊔ (Dᗮ).map L.adjoint.toLinearMap : Submodule ℝ H) : Set H)

Corollary 15.34

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.34: for a bounded linear operator L ∈ 𝓑(𝓗, 𝓚), the range of L is closed if and only if the range of its adjoint L* is closed. This is exactly the earlier project owner theorem ContinuousLinearMap.isClosed_range_iff_isClosed_range_adjoint from Fact 2.26.

recall ContinuousLinearMap.isClosed_range_iff_isClosed_range_adjoint

Corollary 15.35

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.35: for closed linear subspaces U and V of a real Hilbert space, the sum U + V is closed if and only if the sum of the orthogonal complements Uᗮ + Vᗮ is closed.

open scoped InnerProductSpace universe u variable {H : Type u} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: specialize Corollary 15.33 to the identity operator on `H`; then `U.map id = U` -- and the adjoint of the identity is the identity, so the criterion becomes exactly the -- equivalence between closedness of `U ⊔ V` and of `Uᗮ ⊔ Vᗮ`. theorem isClosed_sup_iff_isClosed_orthogonal_sup_orthogonal (U V : Submodule ℝ H) (hU_closed : IsClosed (U : Set H)) (hV_closed : IsClosed (V : Set H)) : IsClosed ((U ⊔ V : Submodule ℝ H) : Set H) ↔ IsClosed (((Uᗮ) ⊔ Vᗮ : Submodule ℝ H) : Set H)

Corollary 15.36

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 15.36: if L has closed range and V is a closed linear subspace, then L(V) is closed if and only if V + ker L is closed.

open ContinuousLinearMap open scoped InnerProductSpace universe u v variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] -- Proof sketch: specialize Corollary 15.33 to `D = ⊥`, so closedness of `L(V)` is equivalent to -- closedness of `Vᗮ + range L*`. For closed-range operators, the Chapter 3 bridge -- `orthogonal_ker_eq_adjoint_range` identifies `range L*` with `(\ker L)ᗮ`. Corollary 15.35 then -- converts closedness of `Vᗮ + (\ker L)ᗮ` to closedness of `V + \ker L`. theorem isClosed_map_iff_isClosed_sup_ker_of_isClosed_range (L : H →L[ℝ] K) (hL_range : IsClosed (L.range : Set K)) (V : Submodule ℝ H) (hV_closed : IsClosed (V : Set H)) : IsClosed ((V.map L.toLinearMap : Submodule ℝ K) : Set K) ↔ IsClosed ((V ⊔ L.ker : Submodule ℝ H) : Set H)