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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 ↦ (γ : ℝ)⁻¹ • x

Remark 14.4

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

Source header · Attribution source

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)).asEReal

Example 14.5

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

Source header · Attribution source

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.

Source header · Attribution source

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 g

Proposition 14.7

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

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.asEReal

Proposition 14.10

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

Source header · Attribution source

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.

Source header · Attribution source

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ᵒ⊙]).asEReal

Corollary 14.13

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

Source header · Attribution source

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 = C

Proposition 14.14

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

Source header · Attribution source

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.asEReal

Proposition 14.15

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

Source header · Attribution source

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 ≤ M

Proposition 14.16

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

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.asEReal

Proposition 14.19

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

Source header · Attribution source

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.

Source header · Attribution source

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∗))