Chapter 14 — Further Conjugation Results
Proofs omitted. Hover over highlighted terms to see their Lean types.
Proposition 14.1
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 14.1: for f ∈ Γ₀(H) and γ ∈ ℝ_{++}, if q(x) = (1 / 2) ‖x‖^2, then the Fenchel conjugate of f + γ q is the γ-Moreau envelope of f*; equivalently, (f + γ q)^* = f* □ (γ⁻¹ q) = {}^γ(f^*), and this infimal convolution is exact.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: apply Corollary 13.38 to identify the biconjugate of `f` with `f`, combine
-- Proposition 13.24(2) with the quadratic-kernel conjugacy from Proposition 13.24(3), and then
-- use that `gammaZeroConjugate f hf` belongs to `Γ₀(H)` so its Moreau envelope is the exact
-- infimal convolution with `γ⁻¹ q`.
theorem conjugate_add_scaledQuadratic_eq_moreauEnvelope_gammaZeroConjugate
(f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (γ : Set.Ioi (0 : ℝ)) :
(f.asEReal + (((γ : ℝ) : EReal) • halfSquaredNorm.asEReal))∗ =
{}^[γ] (gammaZeroConjugate f hf)Proposition 14.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 14.2: for a continuous convex real-valued function f on a real Hilbert space and γ ∈ ℝ_{++}, the shifted conjugate f* - γ⁻¹ q with q(x) = ‖x‖² / 2 is convex if and only if γ q - f is convex.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: for `(i) → (ii)`, apply the Fenchel--Moreau identities from Chapter 13 to the
-- convex function `f* - γ⁻¹ q` and identify `γ q - f` with a Moreau-envelope expression, whose
-- convexity follows from Proposition 12.15. For `(ii) → (i)`, write `f = γ q - g` with `g`
-- convex, use Proposition 13.29 to rewrite `f* - γ⁻¹ q` as a positive multiple of a conjugate,
-- and conclude by convexity of Fenchel conjugates.
theorem conjugateSubInvHalfSquaredNorm_convex_iff_halfSquaredNorm_sub_convex
(f : H → ℝ) (hcont : Continuous f) (hconv : _root_.ConvexOn ℝ Set.univ f)
(γ : Set.Ioi (0 : ℝ)) :
ConvexOn (conjugateSubInvHalfSquaredNorm f γ)
(effectiveDomain (conjugateSubInvHalfSquaredNorm f γ)) ↔
_root_.ConvexOn ℝ Set.univ (fun x : H ↦ ((γ : ℝ) / 2) * ‖x‖ ^ (2 : ℕ) - f x)Theorem 14.3
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Theorem 14.3 (1): for f ∈ Γ₀(H) and γ ∈ ℝ_{++}, equation (14.3) states that the quadratic kernel γ⁻¹ q is the sum of the γ-Moreau envelope of f and the γ⁻¹-Moreau envelope of f* composed with γ⁻¹ Id.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: combine Proposition 14.1 with Example 13.6 and apply the reciprocal-parameter
-- form of Moreau regularization to `f*`.
theorem moreauQuadraticKernel_eq_moreauEnvelope_add_conjugateMoreauEnvelope
(f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (γ : PosReal) :
(moreauQuadraticKernel γ).asEReal =
{}^[γ] f + ({}^[(γ⁻¹ : PosReal)] (f.asEReal∗)) ∘
fun x ↦ (γ : ℝ)⁻¹ • xRemark 14.4
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Remark 14.4 (1): for f ∈ Γ₀(H) and q = (1 / 2) ‖·‖², Moreau's decomposition gives (f □ q) + (f^* □ q) = q, written here as an identity between the unit Moreau envelopes of f and f^* and the unit quadratic kernel.
open scoped Gradient InnerProductSpace Pointwise Set
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: specialize Theorem 14.3 (1) to the unit parameter `γ = 1`, so that both Moreau
-- envelopes are regularized by the kernel `q = (1 / 2) ‖·‖²`.
theorem moreauEnvelope_add_conjugateMoreauEnvelope_eq_unitMoreauQuadraticKernel
(f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) :
({}^[1] f) + ({}^[1] (gammaZeroConjugate f hf)) =
(halfSquaredNorm : H → Set.Ioi (⊥ : EReal)).asERealExample 14.5
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 14.5: for the scaled-norm kernel f = ρ ‖·‖ with ρ ∈ ℝ_{++}, the proximal operator Prox_f is the soft thresholder with threshold ρ.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: use Moreau's decomposition with `(ρ ‖·‖)^* = ι_{B(0;ρ)}`, identify the proximity
-- operator of that indicator with the metric projection onto `B(0;ρ)`, and then invoke the
-- Chapter 4 owner `softThresholder`.
theorem proximityOperator_scaledNorm_eq_softThresholder
(ρ : Set.Ioi (0 : ℝ)) :
Prox[scaledNormKernelOfPos ρ, scaledNormKernelOfPos_mem_gammaZero ρ] =
(softThresholder (ρ : ℝ) : H → H)Definition 14.6
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Definition 14.6: the proximal average is the infimal postcomposition of the textbook kernel along the midpoint map. The single-variable infimum formula is the companion evaluation theorem below.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [Module ℝ H]
def proximalAverage (f g : H → Set.Ioi (⊥ : EReal)) : H → EReal :=
proximalAverageMidpointMap ▷ proximalAverageKernel f gProposition 14.7
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 14.7 (1): the proximal average is symmetric in its two arguments.
open scoped Pointwise
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [Module ℝ H]
theorem proximalAverage_comm (f g : H → Set.Ioi (⊥ : EReal)) :
pav(f, g) = pav(g, f)Corollary 14.8
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 14.8 (1): if f, g ∈ Γ₀(H), then the proximal average pav(f, g), viewed as a ]-∞, +∞]-valued function, also belongs to Γ₀(H).
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [Module ℝ H]
-- Proof sketch: Corollary 14.8(ii) identifies the conjugate of `pav(f, g)` with the proximal
-- average of two `Γ₀(H)` functions, so taking the conjugate again and using
-- Corollary 13.38 gives `(pav(f, g))** = pav(f, g)`. Proposition 14.7(4) and Proposition 13.13
-- then show that its canonical Chapter 9 representative `properIoi (pav(f, g))
-- (isProper_proximalAverage f g hf hg)` lies in `Γ₀(H)`.
theorem proximalAverage_mem_gammaZero
(f g : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) :
properIoi (pav(f, g)) (isProper_proximalAverage f g hf hg) ∈ Γ₀(H)Proposition 14.9
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 14.9: the proximal average is bounded above by the half-sum of f and g.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [Module ℝ H]
-- Proof sketch: evaluate the defining infimum of `pav(f, g)` at the diagonal choice `y = x`.
theorem proximalAverage_upper_bound
(f g : H → Set.Ioi (⊥ : EReal)) :
pav(f, g) ≤
((1 / 2 : ℝ) : EReal) • f.asEReal + ((1 / 2 : ℝ) : EReal) • g.asERealProposition 14.10
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 14.10: on H × H, transpose ᵀ commutes with the proximal average computed in the textbook ℓ² product geometry.
universe u
namespace ERealFunction
open WithLp
variable {H : Type u}
variable [NormedAddCommGroup H] [Module ℝ H]
theorem proximalAverage_transpose
(F G : (H × H) → Set.Ioi (⊥ : EReal)) :
(pav(F, G))ᵀ = pav(Fᵀ, Gᵀ)Proposition 14.12
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 14.12: if C is convex and contains 0, then the Fenchel conjugate of the Minkowski gauge m[C] is the indicator of the polar set Cᵒ⊙.
open scoped InnerProductSpace Pointwise Set
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
-- Proof sketch: the canonical owner here is the support function `σ`. For a convex set containing
-- `0`, the gauge `m[C]` agrees with the support function of the polar set `σ[Cᵒ⊙]`; this is the
-- bridge from the source-facing gauge to the Chapter 7 owner abstraction. Proposition 14.12 then
-- identifies the conjugate of that source-facing gauge with the indicator of the same polar set.
theorem conjugate_minkowskiGauge_eq_indicator_polarSet
(C : Set H) (hC_convex : Convex ℝ C) (h0C : (0 : H) ∈ C) :
(m[C])∗ = (ι[Cᵒ⊙]).asERealCorollary 14.13
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 14.13 (1): clause (i). If C is closed, convex, and contains 0, then C is exactly the lower level set {x | m[C] x ≤ 1} of its Minkowski gauge.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H]
-- Proof sketch: the inclusion `C ⊆ lowerLevelSet (m[C]) 1` comes from the defining infimum of the
-- gauge. For the reverse inclusion, separate a point `x ∉ C` from the closed convex set `C` by a
-- continuous linear functional and use the resulting strict supporting inequality to force
-- `m[C] x > 1`.
theorem lowerLevelSet_minkowskiGauge_one_eq_of_isClosed_of_convex_of_zero_mem
(C : Set H) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (h0C : (0 : H) ∈ C) :
lowerLevelSet (m[C]) 1 = CProposition 14.14
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 14.14 (1): if f ∈ Γ₀(H) and the liminf of f(x) / ‖x‖ at infinity is strictly larger than α, then f admits a global affine lower bound of slope α.
open scoped InnerProductSpace
open Metric
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable [CompleteSpace H]
-- Proof sketch: the strict liminf inequality at infinity yields a radius beyond which
-- `f x / ‖x‖` stays above `α`, hence `f x ≥ α ‖x‖` outside a large ball. On the complementary
-- closed ball, properness of a `Γ₀(H)` function gives a finite real lower bound, which can be
-- absorbed into a global affine-norm minorant.
theorem exists_affine_norm_lowerBound_of_liminf_div_norm_gt
(f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (α : ℝ)
(hliminf :
(α : EReal) <
Filter.liminf (fun x : H ↦ f.asEReal x / ‖x‖)
(Filter.comap (fun x : H ↦ ‖x‖) Filter.atTop)) :
∃ β : ℝ,
(fun x : H ↦ ((α * ‖x‖ + β : ℝ) : EReal)) ≤ f.asERealProposition 14.15
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 14.15 (1): for f ∈ Γ₀(H), supercoercivity of f is equivalent to the Fenchel conjugate f* being bounded above on every bounded subset of H.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
-- Proof sketch: for `(i) → (ii)`, combine supercoercive growth with the Fenchel conjugate formula
-- to get a uniform real upper bound on each bounded set. For `(ii) → (i)`, apply the bounded-set
-- hypothesis to large closed balls in the dual space and use the standard dual characterization of
-- supercoercivity for functions in `Γ₀(H)`.
theorem supercoercive_iff_conjugate_boundedOnEveryBoundedSet
(f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) :
Supercoercive f.asEReal ↔
∀ B : Set H, Bornology.IsBounded B →
∃ M : ℝ, ∀ u ∈ B, f.asEReal∗ u ≤ MProposition 14.16
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 14.16: for f ∈ Γ₀(H), the following are equivalent: f is coercive; every real lower level set of f is bounded; the asymptotic quotient f(x) / ‖x‖ has strictly positive liminf at infinity; f admits a global affine lower bound of the form α ‖x‖ + β with α > 0; the Fenchel conjugate f* is bounded above on some closed ball around 0 (equivalently, on some neighborhood of 0); and 0 belongs to the interior of its domain.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: use Proposition 11.12 for `(i) ↔ (ii)`. For `(ii) → (iii)`, argue by contradiction:
-- if the asymptotic quotient has nonpositive liminf, convexity lets one interpolate a bounded
-- lower-level sequence with norms tending to `+∞`. The implication `(iii) → (i)` is immediate.
-- Proposition 14.14 gives `(iii) ↔ (iv)` and the canonical equivalence between affine lower bounds
-- and boundedness of the Fenchel conjugate `f*` on closed balls around `0`, while the standard
-- local boundedness criterion for convex functions identifies boundedness of `f*` on a
-- neighborhood of `0` with `0 ∈ interior (dom f*)`.
theorem coercive_tfae_lowerLevelSet_asymptoticSlope_affineLowerBound_conjugate
(f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) :
List.TFAE
[Coercive f.asEReal,
∀ ξ : ℝ, Bornology.IsBounded (lowerLevelSet f.asEReal ξ),
((0 : ℝ) : EReal) <
Filter.liminf (fun x : H ↦ f.asEReal x / ‖x‖)
(Filter.comap (fun x : H ↦ ‖x‖) Filter.atTop),
∃ α : Set.Ioi (0 : ℝ), ∃ β : ℝ,
(scaledNormKernelOfPos α).asEReal + (fun _ : H ↦ (β : EReal)) ≤ f.asEReal,
∃ ε : Set.Ioi (0 : ℝ), ∃ γ : ℝ,
∀ u : H, u ∈ Metric.closedBall (0 : H) (ε : ℝ) →
f.asEReal∗ u ≤ (γ : EReal),
(0 : H) ∈ interior (dom f.asEReal∗)]Theorem 14.17
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Theorem 14.17: the Moreau--Rockafellar coercivity criterion says that for f ∈ Γ₀(H) and u ∈ H, the linear perturbation x ↦ f x - ⟪x, u⟫ is coercive exactly when u lies in the interior of the domain of the Fenchel conjugate f*.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable [CompleteSpace H]
-- Proof sketch: Proposition 14.16 identifies coercivity of an element of `Γ₀(H)` with
-- membership of `0` in the interior of the domain of its Fenchel conjugate. Apply this to the
-- linear perturbation `x ↦ f x - ⟪x, u⟫`, then use Proposition 13.23 (iii) with zero translation
-- and constant term to rewrite its conjugate as the translate
-- `v ↦ f^*(v + u)`, which moves the interior-domain condition from `0` to `u`.
theorem coercive_sub_inner_iff_mem_interior_dom_conjugate
(f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (u : H) :
Coercive (f.asEReal - fun x ↦ ((⟪x, u⟫_ℝ : ℝ) : EReal)) ↔
u ∈ interior (dom f.asEReal∗)Corollary 14.18
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 14.18 (1): if f, g ∈ Γ₀(H) and f is supercoercive, then the infimal convolution f □ g is coercive if and only if g is coercive.
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))
variable (hsuper : Supercoercive f.asEReal)
theorem coercive_infimalConvolution_iff_coercive_of_left_supercoercive
(f g : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H))
(hsuper : Supercoercive f.asEReal) :
Coercive (f □ g) ↔ Coercive g.asERealProposition 14.19
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 14.19: if h ∈ Γ₀(H), then the Fenchel conjugate of the piecewise function from (14.23), equal to g - h on effectiveDomain g and +∞ outside it, satisfies `(x ↦ if x ∈ effectiveDomain g then g x - h x else +∞)* u = sup_{v ∈ dom h*} (g* (u + v) - h* v)for everyu`.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: use Corollary 13.38 to rewrite `h` as its Fenchel biconjugate, expand
-- the conjugate of the piecewise map
-- `x ↦ if x ∈ effectiveDomain g then g x - h x else +∞` as a supremum over the effective domain
-- of `g`, insert the
-- supremum formula for `h = h**`, interchange the two suprema, and identify the inner supremum as
-- `g* (u + v)`.
theorem conjugate_sub_on_effectiveDomain_eq_sSup_conjugate_add_sub_conjugate
(g h : H → Set.Ioi (⊥ : EReal)) (hh : h ∈ Γ₀(H)) (u : H) :
(fun x ↦ if x ∈ effectiveDomain g then g.asEReal x - h.asEReal x else ⊤)∗ u =
sSup
((fun v : H ↦
g.asEReal∗ (u + v) - h.asEReal∗ v) ''
dom (h.asEReal∗))Corollary 14.20
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 14.20: if g, h ∈ Γ₀(H), then the infimum of g - h over dom g equals the infimum of h* - g* over dom h*.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: apply the preceding conjugation identity for the piecewise function equal to
-- `g - h` on `effectiveDomain g` and `+∞` outside it at `u = 0`, then use the canonical origin
-- formula for Fenchel conjugates to rewrite both sides as negative infima. Finally unfold that
-- piecewise expression on the primal side and `dom` on the dual side to recover the displayed
-- source-facing infima.
theorem toland_singer_inf_sub_eq_inf_conjugate_sub
(g h : H → Set.Ioi (⊥ : EReal)) (hg : g ∈ Γ₀(H)) (hh : h ∈ Γ₀(H)) :
sInf ((fun x ↦ g.asEReal x - h.asEReal x) '' effectiveDomain g) =
sInf
((fun v ↦ h.asEReal∗ v - g.asEReal∗ v) '' dom (h.asEReal∗))