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.
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.
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.
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.
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.
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.
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.
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 gCorollary 15.8
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.1Proposition 15.9
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 xDefinition 15.10
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 gProposition 15.12
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 gProposition 15.13
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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∗ uCorollary 15.15
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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) ≤ 0Corollary 15.16
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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 LProposition 15.21
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.2Fact 15.25
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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_adjointCorollary 15.35
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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)