Chapter 06 — The Proximal Operator
Proofs omitted. Hover over highlighted terms to see their Lean types.
Definition 6.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.1: the proximal mapping of an extended-real-valued function sends x to the set of minimizers of the proximal objective u ↦ f u + (1 / 2) * ‖u - x‖^2. This source-facing set-valued formulation keeps the textbook arg min semantics without choosing a minimizer before existence and uniqueness are established.
universe u
variable {E : Type u} [NormedAddCommGroup E]
def prox (f : E → EReal) (x : E) : Set E :=
{u | IsMinOn (proximal_objective f x) Set.univ u}text 6.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
text 6.1: the weighted scalar ℓ₀ penalty t ↦ λ l₀(t) and the shifted penalty J from Example 6.10 have the same proximal mapping. This bridge is already owned by the source-facing penalty file.
recall prox_mul_l0Indicator_eq_hardThresholdPenaltyDefinition 6.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.2: the soft thresholding function with parameter λ is the map y ↦ (|y| - λ)⁺ * sign y.
open SignType
variable {α : Type*} [Ring α] [LinearOrder α]
def soft_thresholding (lam : α) : α → α :=
fun y ↦ (|y| - lam)⁺ * sign yExample 6.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.2 (1): the zero penalty is the specialization c = 0 of Proposition 6.2.1.
recall prox_const_eq_singleton
-- Proof sketch: this is exactly the owner-level hard-thresholding computation from Example 6.10.Text 6.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Text 6.2 is bridge/view in the proximal/projection domain. Domain sampling in the minimal semantic closure shows that the relevant owner-level declarations are: 1. Chapter 2's extendedIndicator, 2. Chapter 6's prox / prox[...], 3. Chapter 6's source-facing projection owner projection_mapping, 4. the bridge theorem prox_extendedIndicator_eq_projection_mapping. The target file therefore reuses the existing chapter owner P[C] rather than keeping a parallel squared-distance wrapper.
variable {E : Type*} [NormedAddCommGroup E]
recall projection_mappingProposition 6.2.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 6.2.1: if f is the constant function with value c, then the proximal mapping at x is the singleton {x}. Equivalently, the proximal operator of a constant function is the identity map.
universe u
variable {E : Type u} [NormedAddCommGroup E]
@[simp]
theorem prox_const_eq_singleton (c : ℝ) (x : E) :
prox[fun _ ↦ (c : EReal)] x = {x}Proposition 6.2.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 6.2.2: for the linear functional u ↦ ⟪a, u⟫_ℝ, the proximal mapping at x is the singleton {x - a}. Equivalently, the proximal operator of this rank-one functional translates x by -a.
universe u
open scoped RealInnerProductSpace
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem prox_inner_eq_singleton_sub (a x : E) :
prox[fun u ↦ ((⟪a, u⟫ : ℝ) : EReal)] x = {x - a}Proposition 6.2.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 6.2.3: for the Euclidean quadratic y ↦ (1 / 2) ⟪A.toEuclideanLin y, y⟫ + ⟪b, y⟫ on EuclideanSpace ℝ ι, hence on ℝ^n when ι = Fin n, the proximal mapping at x is the singleton obtained by applying the inverse Euclidean linear map ((A + 1)⁻¹).toEuclideanLin to x - b.
open Matrix
open scoped RealInnerProductSpace
variable {ι : Type*} [Fintype ι] [DecidableEq ι]
local notation "E" => EuclideanSpace ℝ ι
theorem prox_quadratic_affine_function_eq_singleton
(A : Matrix ι ι ℝ) (hA : A.PosSemidef) (b x : E) :
prox[fun y : E ↦ (((1 / 2 : ℝ) * ⟪A.toEuclideanLin y, y⟫ + ⟪b, y⟫ : ℝ) : EReal)] x =
{((A + 1)⁻¹).toEuclideanLin (x - b)}Definition 6.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.3: the soft-thresholding operator is the coordinatewise lift of the scalar owner 𝒯[λ] from Definition 6.2 to the canonical finite PiLp 2 product. For α = ℝ and ι = Fin n, this recovers the textbook vector operator T_λ on ℝ^n.
universe u v
variable {ι : Type u}
variable {α : Type v} [Ring α] [LinearOrder α]
local notation "E" => PiLp 2 (fun _ : ι ↦ α)
def softThreshold (lam : α) : E → E :=
WithLp.map 2 <| Pi.map fun _ ↦ 𝒯[lam]Text 6.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Text 6.3 is bridge/view: Definition 6.7 already owns the Moreau envelope M[μ, f], Chapter 2 already owns infimal_convolution together with the textbook notation □, and Definition 6.7 also owns the quadratic kernel ω_μ. The source only recalls that M_f^μ is the infimal convolution of f with ω_μ, so the canonical owner declarations are reused directly here instead of keeping a duplicate theorem wrapper.
recall infimal_convolutionTheorem 6.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.3: if f is a proper closed convex extended-real-valued function, then the proximal set prox[f] x is a singleton for every x. This is the chapter's set-valued rendering of the textbook point-valued proximal map prox_f(x). The ambient assumption [ProperSpace E] is the canonical abstraction replacing the explicit finite-dimensional Euclidean model from the textbook proof route.
universe u
open Set Filter EuclideanGeometry
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
theorem prox_eq_singleton_of_proper_closed_convex
(f : E → EReal) (hf_proper : IsProperExtendedRealFunction f)
(hf_closed : LowerSemicontinuous f) (hf_convex : is_convex_function f) (x : E) :
∃ y : E, prox[f] x = {y}Definition 6.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.4: the hard-thresholding operator with threshold a sends s to {0} when |s| < a, to {s} when a < |s|, and to {0, s} on the threshold |s| = a.
variable {α : Type*} [AddGroup α] [LinearOrder α]
def hard_thresholding (a : α) : α → Set α :=
fun s ↦
if |s| < a then
{0}
else if a < |s| then
{s}
else
{0, s}Theorem 6.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.4: if f is closed and the proximal objective at x, u ↦ f u + (1 / 2) * ‖u - x‖^2, is coercive, then the proximal set prox[f] x is nonempty. The ambient assumption [ProperSpace E] is the canonical abstraction capturing the finite-dimensional Euclidean setting used in the text, and the textbook properness hypothesis on f is redundant once this proximal objective is assumed coercive.
universe u
variable {E : Type u}
variable [NormedAddCommGroup E] [ProperSpace E]
theorem prox_nonempty_of_closed_and_proximal_objective_coercive
(f : E → EReal) (hf_closed : LowerSemicontinuous f) (x : E)
(hcoercive : IsCoerciveExtendedRealFunction (proximal_objective f x)) :
(prox[f] x).NonemptyDefinition 6.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.5: for a lower-threshold family ω : ι → NNReal and an upper-bound family α : ι → ENNReal, the two-sided soft-thresholding operator acts coordinatewise on the canonical L² product PiLp 2 (fun _ : ι ↦ ℝ); its value at i is the truncated magnitude obtained from |x i|, lower threshold ω i, and upper bound α i, multiplied by Real.sign (x i). Specializing to EuclideanSpace ℝ ι, and then to ι = Fin n, recovers the textbook operator on ℝ^n, with α i = ∞ allowed.
variable {ι : Type*} [Fintype ι]
local notation "E" => PiLp 2 (fun _ : ι ↦ ℝ)
def twoSidedSoftThreshold (ω : ι → NNReal) (α : ι → ENNReal) : E → ELemma 6.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 6.5 (1): for the penalty g₁(x) = μ x on [0, ∞) and ∞ on (-∞, 0), the proximal mapping is the singleton {(x - μ)⁺}.
theorem prox_nonnegative_linear_penalty_eq_singleton_posPart_sub (mu x : ℝ) :
prox[nonnegative_linear_penalty mu] x = {(x - mu)⁺}Definition 6.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.6: the weighted ℓ¹ box-constrained level set consists of the families x : EuclideanSpace ℝ ι such that ∑ i, ω_i |x_i| ≤ β and |x_i| ≤ α_i coordinatewise, equivalently -α ≤ x ≤ α; specializing to ι = Fin n recovers the textbook subset of ℝ^n.
open WithLp
open scoped BigOperators
variable {ι : Type*}
local notation "coord" => WithLp.equiv (2 : ENNReal) (ι → ℝ)
local notation "E" => EuclideanSpace ℝ ι
variable [Fintype ι]
def weighted_l1_box_constraint_set
(ω : ι → NNReal) (α : ι → ENNReal) (β : ℝ) : Set E :=
{x |
(∑ i, (ω i : ℝ) * |x i|) ≤ β ∧
x ∈
(coord ⁻¹' Box[fun i ↦ -((α i : EReal)), fun i ↦ (α i : EReal)] : Set E)}Theorem 6.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.6: for a separable extended-real-valued function on a finite Cartesian product, the proximal operator at x is the set of points whose i-th coordinate lies in the proximal operator of the i-th summand at x i. This is the textbook identity prox_f (x₁, …, x_m) = prox_{f₁} (x₁) × ⋯ × prox_{f_m} (x_m) expressed on PiLp (2 : ENNReal) E.
open scoped BigOperators
universe u v
variable {ι : Type v} [Fintype ι]
variable {E : ι → Type u}
variable [∀ i, NormedAddCommGroup (E i)]
theorem prox_separableSum_eq_coordinatewise
(f : ∀ i, E i → EReal) (hf_proper : ∀ i, IsProperExtendedRealFunction (f i))
(x : PiLp (2 : ENNReal) E) :
prox[PiLp.separableSum f] x = {y : PiLp (2 : ENNReal) E | ∀ i, y i ∈ prox[f i] (x i)}Definition 6.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.7: the Moreau envelope of f with positive smoothing parameter μ is the pointwise infimum of the penalized objective u ↦ f u + (1 / (2 * μ)) ‖x - u‖².
universe u
variable {E : Type u} [NormedAddCommGroup E]
@[inherit_doc] notation "ω(" μ ")" => moreau_quadratic_kernel μ
-- Proof sketch: unfold `moreau_quadratic_kernel`; the displayed formula is exactly the defining
-- quadratic penalty.
def moreau_envelope (μ : PosReal) (f : E → EReal) : E → EReal :=
f □ ω(μ)Remark 6.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Remark 6.7: for a separable function on a finite L² product, the set-valued proximal identity from Theorem 6.6 is equivalent to the singleton statement that the proximal point at x is the point whose i-th coordinate is the proximal point of the i-th summand f i at x i. Specializing to E i = ℝ, this gives the textbook vector formula on EuclideanSpace ℝ ι, and for ι = Fin n it is prox_f(x) = (prox_{f_i}(x_i))_{i=1}^n.
variable {ι : Type*} [Fintype ι]
variable {E : ι → Type*}
variable [∀ i, NormedAddCommGroup (E i)]
theorem prox_separableSum_eq_singleton_iff_coordinatewise
(f : ∀ i, E i → EReal) (hf_proper : ∀ i, IsProperExtendedRealFunction (f i))
(x y : PiLp (2 : ENNReal) E) :
prox[PiLp.separableSum f] x = {y} ↔
∀ i : ι, prox[f i] (x i) = {y i}Definition 6.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.8: for a positive smoothing parameter μ, the Huber function is the radial piecewise function that equals (1 / (2 * μ)) ‖x‖² on the closed ball ‖x‖ ≤ μ and ‖x‖ - μ / 2 outside that ball.
universe u
variable {E : Type u} [NormedAddCommGroup E]
def huber_function (μ : PosReal) : E → ℝ :=
fun x ↦ if ‖x‖ ≤ μ then (1 / (2 * μ)) * ‖x‖ ^ (2 : ℕ) else ‖x‖ - μ / 2Example 6.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.8: for the Euclidean ℓ¹ regularizer x ↦ λ ‖x‖₁ on a finite Euclidean product, specializing to ℝ^n when ι = Fin n, the proximal mapping at x is the singleton obtained by coordinatewise soft-thresholding.
open WithLp (toLp)
open scoped BigOperators
open scoped SoftThreshold
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
theorem prox_euclidean_l1_eq_singleton_softThreshold
{lam : ℝ} (hlam : 0 ≤ lam) (x : E) :
prox[fun y : E ↦ ((lam * ‖y‖₁ : ℝ) : EReal)] x =
{T_[lam] x}Definition 6.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.9: the textbook binary operation f □ g is the owner-level notation for Chapter 2's canonical infimal convolution infimal_convolution f g. This file is therefore bridge/view only at the source-text level: it recalls that established surface rather than introducing a second public owner or a notation-specific evaluation API.
recall infimal_convolutionExample 6.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.9: for λ > 0, the proximal mapping of the coordinatewise logarithmic barrier on a finite positive orthant is the singleton vector whose j-th coordinate is (x_j + √(x_j^2 + 4 λ)) / 2. For ι = Fin n, this is the textbook formula on ℝ^n.
open WithLp (toLp)
open scoped Pointwise
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
theorem prox_log_barrier_penalty_eq_singleton {lam : ℝ} (hlam : 0 < lam)
(x : E) :
prox[PiLp.separableSum (fun _ ↦ (lam : EReal) • negative_log_barrier)] x =
{toLp 2 (fun j ↦ (x j + Real.sqrt (x j ^ 2 + 4 * lam)) / 2)}Definition 6.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.10: if u is the unique proximal point of the scaled function μ f at x, then the gradient of the real-valued Moreau envelope at x is (1 / μ) • (x - u). This is the chapter's singleton-valued rendering of the textbook formula ∇ M_f^μ(x) = (1 / μ) (x - prox_{μ f}(x)).
open InnerProductSpace (toDualMap)
open scoped Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable (f : E → EReal) (μ : PosReal)
theorem moreau_envelope_gradient_formula_of_scaled_prox_eq_singleton
(hf_proper : IsProperExtendedRealFunction f) (hf_closed : LowerSemicontinuous f)
(hf_convex : is_convex_function f) (x u : E)
(hprox : prox[((μ : EReal) • f)] x = {u}) :
∇ (fun y ↦ (M[μ, f] y).toReal) x = (1 / μ : ℝ) • (x - u)Example 6.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.10: if 0 ≤ λ, then the proximal mapping of the shifted scalar ℓ₀ penalty J is exactly the hard-thresholding operator 𝓗[√(2 λ)].
theorem prox_hardThresholdPenalty_eq_hardThresholding (lam : ℝ) (hlam : 0 ≤ lam) (s : ℝ) :
prox[hardThresholdPenalty lam] s = 𝓗[Real.sqrt (2 * lam)] sDefinition 6.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.11: the extended-real quadratic-over-linear function φ : ℝ × ℝ → EReal given by φ(s, t) = s^2 / t for t > 0, φ(0, 0) = 0, and φ(s, t) = ∞ in all other cases.
def quadratic_over_linear : ℝ × ℝ → EReal :=
fun p ↦
if 0 < p.2 then
((p.1 ^ (2 : ℕ) / p.2 : ℝ) : EReal)
else if p.1 = 0 ∧ p.2 = 0 then
0
else
⊤Theorem 6.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.11: scaling and translation for the source-facing set-valued proximal mapping. For f x = g (lam • x + a), the proximal points of f at x are exactly the inverse affine image of the proximal points of z ↦ lam² g z at lam • x + a. The textbook properness hypothesis on g is redundant for this minimizer-set identity, so the canonical Lean statement omits it.
universe u
open scoped Pointwise
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem proximal_mapping_scaling_translation
(g : E → EReal) (lam : ℝ) (hlam : lam ≠ 0) (a x : E) :
prox[fun y ↦ g (lam • y + a)] x =
(fun z ↦ lam⁻¹ • (z - a)) ''
prox[((lam ^ 2 : ℝ) : EReal) • g] (lam • x + a)Definition 6.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 6.12: the set C_s = {x | ‖x‖₀ ≤ s} of s-sparse vectors, defined as the functions with at most s nonzero coordinates. The textbook ℝ^n formulation is the specialization ι = Fin n, α = ℝ, while the canonical Lean owner itself only needs a codomain with zero and uses Set.encard so the support count stays faithful even on infinite index types.
variable {ι : Type*}
variable {α : Type*} [Zero α]
def sSparseVectors (s : ℕ) : Set (ι → α) :=
{x | (Function.support x).encard ≤ s}Theorem 6.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.12: for the scaled pullback f y = λ g (λ⁻¹ • y), the proximal set of f at x is the scalar multiple by λ of the proximal set of z ↦ g z / λ at λ⁻¹ • x. This is the chapter's set-valued formulation of the textbook identity prox_f(x) = λ prox_{g / λ}(x / λ). The textbook properness hypothesis on g is redundant for this minimizer-set identity, so the canonical Lean statement omits it.
universe u
open scoped Pointwise
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem proximal_mapping_smul_precompose_inv_smul
(g : E → EReal) (lam : ℝ) (hlam : lam ≠ 0) (x : E) :
prox[fun y : E ↦ (lam : EReal) * g (lam⁻¹ • y)] x =
lam • prox[fun z : E ↦ g z / (lam : EReal)] (lam⁻¹ • x)Theorem 6.13
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.13: quadratic perturbation for the source-facing proximal mapping. For f u = g u + (c / 2) ‖u‖² + ⟪a, u⟫ with c > -1, the proximal points of f at x are exactly the proximal points of the scaled function u ↦ (1 / (c + 1)) g u at the shifted base point ((c + 1)⁻¹) • (x - a). The textbook properness hypothesis on g is redundant for this minimizer-set identity, the additive constant term is already covered upstream by prox_add_const, and the textbook condition c > 0 is stronger than needed: the completed-square argument only requires c + 1 > 0.
universe u
open scoped Pointwise RealInnerProductSpace
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem proximal_mapping_quadratic_perturbation
(g : E → EReal) (c : ℝ) (hc : -1 < c) (a x : E) :
prox[g + fun u ↦ (((c / 2 : ℝ) * ‖u‖ ^ 2 + ⟪a, u⟫ : ℝ) : EReal)] x =
prox[((c + 1)⁻¹ : EReal) • g] (((c + 1)⁻¹) • (x - a))Example 6.14
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.14: for the function f(x) = μ x on [0, α] ∩ ℝ and ∞ outside, where α ∈ [0, ∞], the proximal mapping at x is the singleton consisting of the projection of x - μ onto [0, α] ∩ ℝ.
theorem prox_truncated_linear_penalty_eq_singleton
(μ : ℝ) (α : ENNReal) (x : ℝ) :
prox[truncated_linear_penalty μ α] x =
{if α = ⊤ then max (x - μ) 0 else min (max (x - μ) 0) α.toReal}Theorem 6.15
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.15: composition with a continuous affine mapping. For f = g ∘ φ, if φ.contLinear ∘L φ.contLinear† = α • 1 with α > 0, then the proximal set of f at x is the image of the proximal set of (α : EReal) • g at φ x under the affine correction z ↦ x + α⁻¹ • φ.contLinear† (z - φ x). This is the chapter's set-valued formulation of the textbook proximal-point identity. For this bare minimizer-set equality, the semantically active hypothesis on g is properness: g must avoid ⊥ and have nonempty effective domain, excluding the degenerate g ≡ ⊤ case. The stronger closedness and convexity parts of the textbook assumptions are still not used at this transport level.
universe u v
open scoped InnerProduct Pointwise
variable {V : Type u} [NormedAddCommGroup V] [InnerProductSpace ℝ V] [CompleteSpace V]
variable {W : Type v} [NormedAddCommGroup W] [InnerProductSpace ℝ W] [CompleteSpace W]
theorem proximal_mapping_precompose_continuousAffineMap
(g : W → EReal) (hg_proper : IsProperExtendedRealFunction g)
(φ : V →ᴬ[ℝ] W) (α : ℝ) (hα : 0 < α)
(hφ : φ.contLinear ∘L φ.contLinear† = α • 1) (x : V) :
prox[g ∘ φ] x =
(fun z ↦ x + (α⁻¹ • φ.contLinear†) (z - φ x)) ''
prox[(α : EReal) • g] (φ x)Example 6.16
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.16: on the canonical finite L² product PiLp (2 : ENNReal), if f x = g (∑ i, x i), then the proximal set of f at x is obtained by choosing a proximal point z of (Fintype.card ι) g at ∑ i, x i and translating x by the constant tuple with common value (1 / Fintype.card ι) • (z - ∑ i, x i). The textbook m-tuple formula is the specialization ι = Fin m; the empty family case is included and both sides are the unique point of the empty product. The semantically active hypothesis is the canonical properness owner IsProperExtendedRealFunction g, whose effective-domain witness rules out the degenerate g ≡ ⊤ case; stronger textbook closedness and convexity assumptions remain unnecessary.
open scoped BigOperators InnerProduct
open WithLp (toLp)
universe u
variable {ι : Type u} [Fintype ι]
variable {E : Type u}
variable [NormedAddCommGroup E] [InnerProductSpace ℝ E]
local notation "Eι" => PiLp (2 : ENNReal) (fun _ : ι ↦ E)
theorem proximal_mapping_sum_precompose_eq_image
(g : E → EReal) (hg_proper : IsProperExtendedRealFunction g) (x : Eι) :
prox[fun y : Eι ↦ g (∑ i, y i)] x =
(fun z : E ↦
x + toLp 2 (fun _ : ι ↦ (1 / (Fintype.card ι : ℝ)) • (z - ∑ i, x i))) ''
prox[((Fintype.card ι : ℝ) : EReal) • g] (∑ i, x i)Example 6.17
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.17: on a real inner product space, for f = absolute_value_penalty 1 ∘ innerSL ℝ a, equivalently f(u) = |⟪a, u⟫|, if a ≠ 0, then the proximal mapping at x is the singleton containing the soft-thresholding correction x + ((𝒯[‖a‖^2] ⟪a, x⟫ - ⟪a, x⟫) / ‖a‖^2) a. Specializing to E = EuclideanSpace ℝ (Fin n) recovers the textbook formula for |aᵀ x| on ℝ^n. The nonzeroness hypothesis is mathematically active here because the displayed coefficient divides by ‖a‖^2; without it, the written source formula would rely on Lean's totalized division by zero rather than on the textbook expression itself.
universe u
open scoped RealInnerProductSpace
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem prox_abs_inner_eq_singleton_soft_thresholding_correction
(a x : E) (ha : a ≠ 0) :
prox[absolute_value_penalty 1 ∘ innerSL ℝ a] x =
{x + (((𝒯[‖a‖ ^ 2] ⟪a, x⟫ - ⟪a, x⟫) / ‖a‖ ^ 2) • a)}Theorem 6.18
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.18: norm composition. For the radial function f = g ∘ norm, the proximal set at x is the radial image of the scalar proximal set at ‖x‖ when x ≠ 0, and at the origin it is the set of vectors whose norm belongs to the scalar proximal set at 0, provided g is proper, closed, convex, and has effective domain contained in [0, ∞). The nontriviality hypothesis records the Euclidean-space assumption used in the textbook proof: at x = 0, every nonnegative optimal scalar radius must be realized as the norm of some vector. Without this, the statement is false in the zero-dimensional space.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable [Nontrivial E]
variable (g : ℝ → EReal) (hproper : IsProperExtendedRealFunction g)
variable (hclosed : LowerSemicontinuous g) (hconvex : is_convex_function g)
variable (hdom : ∀ t : ℝ, t < 0 → g t = ⊤)
include hproper hclosed hconvex hdom
theorem prox_norm_composition_eq_piecewise
(x : E) :
prox[g ∘ norm] x =
if x = 0 then
{u : E | ‖u‖ ∈ prox[g] 0}
else
(fun t : ℝ ↦ (t / ‖x‖) • x) '' prox[g] ‖x‖Example 6.19
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.19: in a real inner product space, for the norm penalty f(x) = λ ‖x‖ with 0 < λ, the proximal mapping at x is the singleton obtained by radial shrinkage: prox[f] x = {(1 - λ / max {‖x‖, λ}) • x}.
universe u
open Function
variable {E : Type u} [NormedAddCommGroup E]
variable [InnerProductSpace ℝ E]
theorem prox_norm_penalty_eq_singleton_shrinkage
(lam : ℝ) (hlam : 0 < lam) (x : E) :
prox[norm_penalty lam] x = {(1 - lam / max ‖x‖ lam) • x}Example 6.20
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.20: for the cubic norm penalty f(x) = λ ‖x‖^3 with 0 < λ, write f = nonnegative_cubic_penalty lam ∘ norm, equivalently g t = if 0 ≤ t then λ t^3 else ∞. Then the proximal mapping of f is given by the radial case split from Theorem 6.18 in the nontrivial case, with the same origin branch remaining valid in the trivial case: at x = 0, it is the set of vectors whose norm lies in prox[nonnegative_cubic_penalty lam] 0, and for x ≠ 0, it is the radial image of prox[nonnegative_cubic_penalty lam] ‖x‖.
universe u
variable {E : Type u} [NormedAddCommGroup E]
variable [InnerProductSpace ℝ E]
theorem prox_cubic_norm_penalty_eq_piecewise (lam : ℝ) (hlam : 0 < lam) (x : E) :
prox[cubic_norm_penalty lam] x =
if x = 0 then
{u : E | ‖u‖ ∈ prox[nonnegative_cubic_penalty lam] 0}
else
(fun t : ℝ ↦ (t / ‖x‖) • x) '' prox[nonnegative_cubic_penalty lam] ‖x‖Example 6.21
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.21 (prox of negative Euclidean norm): let f : E → ℝ be given by f x = -lam * ‖x‖, where 0 < lam. Then the proximal mapping prox[f] x is Metric.sphere 0 lam at the origin and the singleton {(1 + lam / ‖x‖) • x} away from the origin.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [Nontrivial E]
theorem prox_norm_penalty_neg_eq_piecewise (lam : ℝ) (hlam : 0 < lam) (x : E) :
prox[norm_penalty (-lam)] x =
if x = 0 then Metric.sphere 0 lam else {(1 + lam / ‖x‖) • x}Example 6.22
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.22: for the scalar penalty x ↦ λ |x| + δ_{[-α, α]}(x), the proximal mapping at x is the singleton containing the clipped soft-threshold value.
theorem prox_absolute_value_box_penalty_eq_singleton
(lam : NNReal) (α : ENNReal) (x : ℝ) :
prox[absoluteValueBoxPenalty lam α] x =
{if α = ⊤ then
𝒯[(lam : ℝ)] x
else
min |𝒯[(lam : ℝ)] x| α.toReal * Real.sign x}Example 6.23
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.23 (prox of weighted ℓ¹ over a box): the proximal mapping of the weighted ℓ¹ penalty on the symmetric box [-α, α] is the singleton containing the coordinatewise two-sided soft-thresholding point, i.e. the vector with i-th coordinate min (max (|x i| - ω i) 0) α i * Real.sign (x i), with α i = ∞ allowed.
open scoped TwoSidedSoftThreshold
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
theorem prox_weighted_l1_box_penalty_eq_singleton_twoSidedSoftThreshold
(ω : ι → NNReal) (α : ι → ENNReal) (x : E) :
prox[weighted_l1_box_penalty ω α] x =
{𝓢[ω, α] x}Theorem 6.24
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.24: for a nonempty set C, the proximal mapping of the indicator function δ_C coincides with the set-valued projection mapping P_C.
universe u
variable {E : Type u} [NormedAddCommGroup E]
notation "P[" C "]" => projection_mapping C
-- Proof sketch: unfold `projection_mapping`; membership in `P[C] x` is definitionally the
-- conjunction that `y ∈ C` and that `y` minimizes the distance from `x` over `C`.
theorem prox_extendedIndicator_eq_projection_mapping (C : Set E) (hC : C.Nonempty) (x : E) :
prox[extendedIndicator C] x = P[C] xTheorem 6.25
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.25: first projection theorem. If C is a nonempty closed convex subset of a complete real inner product space, then the projection set P[C] x is the singleton containing the canonical metric projection P_C(x).
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable (C : Set E) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C)
(hC_convex : Convex ℝ C)
local notation "Pₛ" => metricProjection C hC_nonempty hC_closed hC_convex
theorem projection_mapping_eq_singleton_of_nonempty_closed_convex
(x : E) : P[C] x = {Pp[C, hC_nonempty, hC_closed, hC_convex] x}Lemma 6.26
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 6.26 (1): the orthogonal projection onto the nonnegative orthant in ℝ^n, represented on the Euclidean owner EuclideanSpace ℝ ι, is the singleton containing the coordinatewise positive part of x.
open scoped Matrix
open scoped RealInnerProductSpace
open WithLp (toLp ofLp)
variable {ι : Type*} [Fintype ι]
local notation "X" => ι → ℝ
local notation "E" => EuclideanSpace ℝ ι
lemma projection_mapping_nonnegativeOrthant_eq_singleton_coordinatewisePosPart (x : E) :
P[((fun y : E ↦ y.ofLp) ⁻¹' Set.Ici (0 : X))] x =
{WithLp.toLp (p := (2 : ENNReal)) x.ofLp⁺}Theorem 6.27
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.27: Euclidean coordinate form of the projection formula for H_(a,b) ∩ Box[ℓ,u]. If the shifted box projection set already satisfies the hyperplane equation, then the projection of x onto the pulled-back hyperplane-box intersection equals the projection of x - μ a onto the pulled-back box.
open WithLp
variable {ι : Type*} [Fintype ι]
local notation "X" => ι → ℝ
local notation "E" => EuclideanSpace ℝ ι
theorem projection_mapping_hyperplane_inter_box_eq_shifted_box_projection_mapping
(a : X) (b : ℝ) (l u : ι → EReal) (x : E) (μ : ℝ)
(hμ : P[((fun y : E ↦ y.ofLp) ⁻¹' Box[l,u])] (x - μ • toLp 2 a) ⊆
((fun y : E ↦ y.ofLp) ⁻¹' coordinateHyperplane a b)) :
P[((fun y : E ↦ y.ofLp) ⁻¹' (coordinateHyperplane a b ∩ Box[l,u]))] x =
P[((fun y : E ↦ y.ofLp) ⁻¹' Box[l,u])] (x - μ • toLp 2 a)Corollary 6.29
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Corollary 6.29: on the intrinsic Euclidean product E = EuclideanSpace ℝ ι, the projection onto the transported standard simplex Δ = toLp 2 '' stdSimplex ℝ ι is the singleton {toLp 2 ((x.ofLp - μ • 1)⁺)} whenever the shifted positive-part point has coordinate sum 1. For ι = Fin n, this is the textbook Euclidean simplex projection formula on ℝ^n.
open WithLp (ofLp toLp)
open scoped RealInnerProductSpace
variable {ι : Type*} [Fintype ι]
local notation "X" => ι → ℝ
local notation "E" => EuclideanSpace ℝ ι
local notation "Δ" => (toLp 2 '' (stdSimplex ℝ ι : Set X) : Set E)
local notation "K" => (toLp 2 '' (Set.Ici (0 : X) : Set X) : Set E)
local notation "e" => (toLp 2 (1 : X) : E)
theorem projection_mapping_stdSimplex_eq_singleton_posPart_sub_smul_one
(x : E) (μ : ℝ) (hμ : ∑ i, ((x.ofLp - μ • (1 : X))⁺) i = 1) :
P[Δ] x = {toLp 2 ((x.ofLp - μ • (1 : X))⁺)}Theorem 6.30
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.30 (1): if the projection of x onto dom(f) exists and every such projection point satisfies f y ≤ α, then the projection onto the level set C = f ⁻¹' Set.Iic (α : EReal) agrees with the projection onto dom(f).
universe u
variable {E : Type u} [NormedAddCommGroup E]
theorem projection_mapping_sublevel_eq_projection_effective_domain_of_projection_mem_sublevel
(f : E → EReal) (α : ℝ) (x : E)
(hproj_nonempty : (P[effective_domain f] x).Nonempty)
(hproj_sublevel : P[effective_domain f] x ⊆ f ⁻¹' Set.Iic (α : EReal)) :
P[f ⁻¹' Set.Iic (α : EReal)] x = P[effective_domain f] xExample 6.32
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.32, feasible branch: if the box projection P[Box[ℓ,u]] x already lies in the coordinate closed half-space coordinateHalfSpace a b, then projecting onto the intersection with the box does not change the projected set. This is the finite-index owner-level form, matching the Chapter 1 half-space owner and the Chapter 6 box owner directly rather than a numbered-coordinate model.
open WithLp
variable {ι : Type*} [Fintype ι]
local notation "E" => ι → ℝ
theorem projection_mapping_halfSpace_inter_box_eq_box_projection_mapping_of_projection_subset
(a : E) (b : ℝ) (l u : ι → EReal)
(x : E)
(hfeas : P[Box[l,u]] x ⊆ coordinateHalfSpace a b) :
P[(coordinateHalfSpace a b ∩ Box[l,u])] x =
P[Box[l,u]] xExample 6.33
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.33: let C = B_{‖·‖₁}[0, α] = {x | ‖x‖₁ ≤ α} in a finite Euclidean product, specializing to ℝ^n when ι = Fin n. If a positive multiplier λ satisfies the textbook active-constraint equation ‖T_[λ] x‖₁ = α, then the set-valued projection onto C is the singleton {T_[λ] x}. The root condition already forces the active branch except in the degenerate feasible case x = 0, α = 0, where the same conclusion holds by projection_mapping_l1ClosedBall_eq_singleton_of_mem. Together with projection_mapping_l1ClosedBall_eq_singleton_of_mem, this gives the textbook piecewise formula for P_C(x).
open scoped SoftThreshold
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
notation "B₁[" α "]" => l1ClosedBall α
local notation "F" => fun y : E ↦ ((‖y‖₁ : ℝ) : EReal)
-- Proof sketch: unfold `l1ClosedBall`; membership is definitionally the inequality
-- `‖x‖₁ ≤ α`.
theorem projection_mapping_l1ClosedBall_eq_singleton_of_root
(α : ℝ) (x : E) (lam : PosReal)
(hroot : ‖T_[(lam : ℝ)] x‖₁ = α) :
P[B₁[α]] x = {T_[(lam : ℝ)] x}Example 6.34
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.34, feasible branch: if the residual at λ = 0 is nonpositive, then the clipped box projection already satisfies the weighted ℓ¹ constraint and is the unique projected point.
open scoped BigOperators TwoSidedSoftThreshold
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
variable (ω : ι → NNReal) (α : ι → ENNReal) (β : ℝ)
variable (x : E)
local notation "φ" => weightedL1BoxProjectionRootFunction ω α β x
local notation "C" => weighted_l1_box_constraint_set ω α β
theorem projection_mapping_weighted_l1_box_constraint_set_eq_singleton_of_residual_nonpos
(x : E) (hres : weightedL1BoxProjectionRootFunction ω α β x 0 ≤ 0) :
P[C] x =
{𝓢[(fun _ ↦ 0), α] x}Example 6.35
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.35: for C = {x ∈ (ℝ_{++})^ι | α ≤ ∏ i, x i}, specializing to the textbook ℝ_{++}^n when ι = Fin n, if positive reals α and λ satisfy the textbook active-constraint equation α = ∏ j, (x j + √(x j^2 + 4 λ)) / 2, then the set-valued orthogonal projection onto C is the singleton whose j-th coordinate is (x j + √(x j^2 + 4 λ)) / 2; the root condition already forces the active branch x ∉ C. The canonical residual formulation from Theorem 6.30 is kept as the companion bridge positiveProductProjectionResidual_eq. Together with projection_mapping_positiveProductSuperlevelSet_eq_singleton_of_mem, this gives the textbook piecewise formula for P_C(x).
open WithLp (toLp)
open scoped BigOperators
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
local notation "F" =>
(PiLp.separableSum (fun _ : ι ↦ negative_log_barrier) : E → EReal)
theorem projection_mapping_positiveProductSuperlevelSet_eq_singleton_of_root
(α : PosReal) (x : E)
(lam : PosReal)
(hroot :
(α : ℝ) =
∏ j, (x j + Real.sqrt (x j ^ (2 : ℕ) + 4 * (lam : ℝ))) / 2) :
P[positiveProductSuperlevelSet (α : ℝ)] x =
{toLp 2 fun j ↦ (x j + Real.sqrt (x j ^ (2 : ℕ) + 4 * (lam : ℝ))) / 2}Theorem 6.36
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.36 in the Euclidean product model: the projection onto the real epigraph of a convex function is the singleton {(x, s)} at feasible points, while on the infeasible branch it is obtained from the proximal set of λ g using any positive root λ of the epigraph residual equation.
universe u
variable {E : Type u}
variable [NormedAddCommGroup E]
variable {ι : Type u} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
local notation "EP" => EuclideanSpace ℝ (Option ι)
theorem projection_mapping_realEpigraph_eq_piecewise_lifted_scaled_prox
(g : E → ℝ) (hg_convex : ConvexOn ℝ Set.univ g) (x : E) (s : ℝ) (lam : ℝ)
(hactive : s < g x → 0 < lam ∧ epigraph_projection_residual g x s lam = 0) :
P[euclideanRealEpigraph g] (euclideanProductPoint x s) =
if hgxs : g x ≤ s then
{euclideanProductPoint x s}
else
(fun y : E ↦ euclideanProductPoint y (s + lam)) ''
prox[fun y : E ↦ (lam : EReal) * (g y : EReal)] xExample 6.37
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.37: for the Lorentz cone {(x, t) ∈ E × ℝ | ‖x‖ ≤ t} = realEpigraph (norm_penalty 1), the orthogonal projection of (x, s) onto that cone is the singleton given by the textbook piecewise formula: it is (((‖x‖ + s) / (2 ‖x‖)) • x, (‖x‖ + s) / 2) when |s| ≤ ‖x‖, (0, 0) when s < -‖x‖, and (x, s) when ‖x‖ ≤ s. This explicit formula is stated at the real inner-product-space level, with no finite-dimensional hypothesis in the public API.
universe u
variable {E : Type u} [NormedAddCommGroup E]
variable [InnerProductSpace ℝ E]
theorem projection_mapping_realEpigraph_norm_penalty_one_eq_singleton_piecewise
(x : E) (s : ℝ) :
P[realEpigraph (norm_penalty 1)] (x, s) =
{if hfeas : ‖x‖ ≤ s then
(x, s)
else if hzero : s < -‖x‖ then
(0, 0)
else
((((‖x‖ + s) / (2 * ‖x‖)) • x), (‖x‖ + s) / 2)}Example 6.38
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.38: let C = {(y, t) | ‖y‖₁ ≤ t} be represented by euclideanRealEpigraph (fun y : E ↦ ‖y‖₁) inside EuclideanSpace ℝ (Option ι), specializing to the textbook ℝ^n × ℝ with its Euclidean product norm when ι = Fin n. Then the set-valued orthogonal projection onto C is {(x, s)} when ‖x‖₁ ≤ s; otherwise, if λ is a positive root of the canonical residual epigraph_projection_residual l1NormFn x s, equivalently of the nonincreasing function φ(λ) = ‖T_[λ] x‖₁ - λ - s by epigraph_projection_residual_euclidean_l1_eq, then the projection is the singleton {(T_[λ] x, s + λ)} in the Euclidean product model.
open scoped SoftThreshold
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
local notation "l1NormFn" => (fun y : E ↦ ‖y‖₁)
theorem projection_mapping_euclidean_l1Epigraph_eq_singleton_piecewise
(x : E) (s lam : ℝ)
(hactive : s < ‖x‖₁ →
0 < lam ∧ epigraph_projection_residual l1NormFn x s lam = 0) :
P[euclideanRealEpigraph l1NormFn] (euclideanProductPoint x s) =
if hfeas : ‖x‖₁ ≤ s then
{euclideanProductPoint x s}
else
{euclideanProductPoint (T_[lam] x) (s + lam)}Theorem 6.39
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.39: second prox theorem. For a proper convex extended-real-valued function, the following are equivalent for fixed x and u: (i) the proximal set prox[f] x is the singleton {u}, (ii) the Riesz image of x - u belongs to the canonical strong-dual subdifferential of f at u, and (iii) the inequality ⟪x - u, y - u⟫ ≤ f(y) - f(u) holds for every y.
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem prox_eq_singleton_tfae_strongDualSubdifferential_inner_le
(f : E → EReal) (hf_proper : IsProperExtendedRealFunction f)
(hf_convex : is_convex_function f) (x u : E) :
List.TFAE
[prox[f] x = {u},
toDualMap ℝ E (x - u) ∈ strongDualSubdifferential f u,
∀ y, ((inner ℝ (x - u) (y - u) : ℝ) : EReal) ≤ f y - f u]Corollary 6.40
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Corollary 6.40: for a proper convex extended-real-valued function, a point x is a global minimizer of f if and only if x is a fixed point of the proximal mapping, expressed in the chapter's set-valued API as prox[f] x = {x}.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem isMinOn_univ_iff_prox_eq_singleton_self
(f : E → EReal) (hf_proper : IsProperExtendedRealFunction f)
(hf_convex : is_convex_function f) (x : E) :
IsMinOn f Set.univ x ↔ prox[f] x = {x}Theorem 6.41
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.41: second projection theorem. For a convex set C and a point u ∈ C, the equality P[C] x = {u} holds if and only if inner ℝ (x - u) (y - u) ≤ 0 for every y ∈ C. The usual nonempty and closed hypotheses are unnecessary for this variational characterization once a candidate point u ∈ C is fixed.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem projection_mapping_eq_singleton_iff_inner_le_zero
(C : Set E) (hC_convex : Convex ℝ C) (x : E) {u : E} (hu : u ∈ C) :
P[C] x = {u} ↔ ∀ y ∈ C, inner ℝ (x - u) (y - u) ≤ 0Theorem 6.42
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.42: (a) firm nonexpansivity of proximal points for a proper closed convex extended-real-valued function. If u and v are the unique proximal points of f at x and y, then ⟪x - y, u - v⟫ ≥ ‖u - v‖².
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable (f : E → EReal)
-- Proof sketch: apply the subgradient inequality defining `gᵤ ∈ ∂f(u)` to the point `v` and the
-- one defining `gᵥ ∈ ∂f(v)` to the point `u`. Adding the two inequalities gives
-- `(gᵤ - gᵥ) (u - v) ≥ 0`.
theorem prox_eq_singleton_firmly_nonexpansive
(x y u v : E)
(hf_proper : IsProperExtendedRealFunction f)
(hf_closed : LowerSemicontinuous f)
(hf_convex : is_convex_function f)
(hx : prox[f] x = {u}) (hy : prox[f] y = {v}) :
inner ℝ (x - y) (u - v) ≥ ‖u - v‖ ^ (2 : ℕ)Lemma 6.43
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 6.43: if C is a nonempty complete convex subset of a real inner product space and 0 ≤ λ, then the proximal mapping of the distance penalty y ↦ λ d_C(y) at x is the singleton given by the textbook piecewise formula, written in canonical projection-ray form: when λ < d_C(x) it is lineMap x (P_C x) (λ / d_C(x)), equivalently P_C(x) + (1 - λ / d_C(x)) (x - P_C(x)), and when d_C(x) ≤ λ it is P_C(x). Here d_C(x) is written as Metric.infDist x C, and P_C denotes the canonical metric projection onto a nonempty complete convex set. The textbook closed-subset-of-a-complete-space formulation is the downstream specialization obtained from IsClosed.isComplete. The endpoint λ = 0 is included canonically: if x ∉ C, then the first branch becomes lineMap x (P_C x) 0 = x, while if x ∈ C, then both branches reduce to x.
universe u
open Metric
open AffineMap
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable (C : Set E) (hC_nonempty : C.Nonempty) (hC_complete : IsComplete C)
(hC_convex : Convex ℝ C)
local notation "P" => metricProjectionOfComplete C hC_nonempty hC_complete hC_convex
-- Proof sketch: apply the second prox theorem to `f = fun y ↦ ((lam * infDist y C : ℝ) : EReal)`.
-- Proof sketch: the distance-penalty proximal objective is controlled by the residual
-- `y - P y`. The candidate point is obtained by applying the earlier norm-penalty shrinkage
-- formula to the residual `x - P x`, then translating back from `P x`. A projection-ray lemma
-- keeps `P x` as the projection of that candidate, and a lower-bound decomposition introduces a
-- nonnegative defect term measuring the motion of the projection point from `P x` to `P y`.
theorem prox_infDist_eq_singleton_piecewise_metricProjection
(lam : ℝ) (hlam : 0 ≤ lam) (x : E) :
prox[fun y : E ↦ ((lam * infDist y C : ℝ) : EReal)] x =
{if lam < infDist x C then
lineMap x (P x) (lam / infDist x C)
else
P x}Theorem 6.44
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.44 is source-facing in the proximal-operator chapter, but in the local Moreau-decomposition API the reusable owner theorem is the scaled identity prox_scaled_conjugate_sum_eq_singleton from Theorem 6.45. The present file should therefore keep only the exact textbook λ = 1 specialization on the canonical owners prox[...] and f∗, with the same proper-space owner assumptions rather than the stronger finite-dimensional proof model.
universe u
open scoped Pointwise
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
recall conjugate_function_primalTheorem 6.45
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.45 is source-facing in the proximal-operator chapter: it is also the reusable owner-level Moreau decomposition in the local API, with Theorem 6.44 as the exact λ = 1 specialization. Domain sampling in the chapter gives the owner chain: - prox[...] from Definition 6.1 as the core/canonical proximal owner, - conjugate_function/f∗ from Definition 4.1 as the core/canonical Fenchel owner and its primal-space surface, - prox_eq_singleton_of_proper_closed_convex from Theorem 6.3 as the chapter's existence/uniqueness owner for proximal points on the ambient space, - conjugate_function_primal_pos_real_mul from Proposition 4.7 and proximal_mapping_smul_precompose_inv_smul from Theorem 6.12 as the two scaling bridges. Primitive data: f, the proper/closed/convex hypotheses, the positive scale lam : PosReal, and x. Derived API: the scaled conjugate rewrite and the proximal transport needed to express the textbook λ-parameter formula directly on the owner surface. The textbook writes a single-valued identity, so the canonical chapter-level rendering is the singleton identity for the pointwise sum set.
universe u
open InnerProductSpace (toDualMap)
open scoped Pointwise
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
recall conjugate_function_primalTheorem 6.46
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.46: prox of support functions. If C is a nonempty complete convex subset of a real inner product space and lam : PosReal encodes a positive scalar λ, then the proximal set of the scaled support function λ σ_C at x is the singleton containing x - λ P_C(x / λ), written in Lean using the canonical owners σ[C] and metricProjectionOfComplete. The familiar closed-subset-in-a-complete-space statement is the direct specialization obtained from metricProjection. This is the chapter's set-valued rendering of the textbook identity prox_{λ σ_C}(x) = x - λ P_C(x / λ).
universe u
open InnerProductSpace (toDualMap)
open scoped Pointwise RealInnerProductSpace
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable (C : Set E) (hC_nonempty : C.Nonempty) (hC_complete : IsComplete C)
(hC_convex : Convex ℝ C)
-- Proof sketch: let `p = metricProjection C (x / λ)` and `u = x - λ • p`.
-- Proposition 3.12 gives the projection
-- variational inequality `⟪u, w - p⟫ ≤ 0` for every `w ∈ C`, so `p` realizes the support
-- function at `u`. This identifies the proximal objective of `λ σ_C` at `u` with the proximal
-- objective of the linear functional `y ↦ ⟪y, λ • p⟫`, whose proximal map is the singleton `{u}`
-- by Proposition 6.2.2. The same linear lower bound then forces every minimizer of `λ σ_C` to
-- equal `u`.
theorem prox_support_function_eq_singleton_sub_smul_metricProjection
(lam : PosReal) (x : E) :
prox[(((lam : ℝ) : EReal) • σ[C])] x =
{x - (lam : ℝ) •
(metricProjectionOfComplete C hC_nonempty hC_complete hC_convex
((lam : ℝ)⁻¹ • x) : E)}Example 6.47
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.47: let f(x) = λ ‖x‖_α for λ > 0, where the source norm ‖·‖_α on the ambient Euclidean space E is encoded by the canonical owner alpha : Seminorm ℝ E, and let C = {y ∈ E | ‖y‖_{α,*} ≤ 1} be its dual unit ball under the Riesz identification E ≃ E*. Then the proximal mapping of f is the affine image of the projection set P[alphaDualUnitBall alpha] (x / λ) under u ↦ x - λ • u. This is the chapter's set-valued rendering of the textbook identity prox_{λ ‖·‖_α}(x) = x - λ P_C(x / λ).
universe u
open InnerProductSpace (toDualMap)
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
-- Proof sketch: this is the dual-ball support-function identity from the earlier chapter,
-- specialized to the auxiliary norm `alpha` and transported back to `E` through `toDualMap ℝ E`.
variable (alpha : Seminorm ℝ E)
-- Proof sketch: evaluate both sides pointwise, rewrite the support function of the dual unit ball
-- using `support_function_alphaDualUnitBall_eq_alpha`, and identify the remaining scalar product.
theorem prox_alphaNormPenalty_eq_sub_smul_projection_mapping_alphaDualUnitBall
(lam : ℝ) (hlam : 0 < lam) (x : E) :
prox[alphaNormPenalty alpha lam] x =
Set.image (fun u : E ↦ x - lam • u) (P[alphaDualUnitBall alpha] (lam⁻¹ • x))Proposition 6.48
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 6.48: on a finite Euclidean product E = EuclideanSpace ℝ ι, specializing to ℝ^n when ι = Fin n, the proximal mapping of the scaled ℓ∞ norm y ↦ λ ‖y.ofLp‖ is the affine image of the projection set onto the closed ℓ¹ unit ball B₁[(1 : ℝ)]. This is the chapter's set-valued rendering of the textbook identity prox_{λ ‖·‖∞}(x) = x - λ P_{B_{‖·‖₁}[0,1]}(x / λ).
open WithLp (ofLp)
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
theorem prox_linftyNorm_eq_sub_smul_projection_mapping_l1ClosedUnitBall
(lam : ℝ) (hlam : 0 < lam) (x : E) :
prox[fun y : E ↦ ((lam * ‖y.ofLp‖ : ℝ) : EReal)] x =
Set.image (fun u : E ↦ x - lam • u)
(P[B₁[(1 : ℝ)]] (lam⁻¹ • x))Example 6.49
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.49: on the intrinsic Euclidean product EuclideanSpace ℝ (Fin n), hence on ℝ^n, the proximal mapping of y ↦ λ max_i y_i at x is the affine image of the projection set onto the transported standard simplex Δ = toLp 2 '' stdSimplex ℝ (Fin n) under u ↦ x - λ • u. This is the chapter's set-valued rendering of the textbook identity prox_{λ max(·)}(x) = x - λ P_{Δ_n}(x / λ).
open InnerProductSpace (toDualMap)
open WithLp (ofLp toLp)
open scoped Pointwise
variable {n : ℕ} [Nonempty (Fin n)]
local notation "E" => EuclideanSpace ℝ (Fin n)
local notation "Δ" => (toLp 2 '' (stdSimplex ℝ (Fin n) : Set (Fin n → ℝ)))
theorem prox_coordinatewiseMax_eq_sub_smul_projection_mapping_stdSimplex
(lam : ℝ) (hlam : 0 < lam) (x : E) :
prox[fun y : E ↦ (lam : EReal) * (coordinatewiseMax y.ofLp : EReal)] x =
Set.image (fun u : E ↦ x - lam • u) (P[Δ] (lam⁻¹ • x))Example 6.50
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.50: for k ≤ Fintype.card ι, if f(x) is the sum of the k largest values of x : EuclideanSpace ℝ ι, then the proximal set of λ f at x is the singleton containing x - λ P_C (x / λ), where C = {y | ∑ i, y i = k, 0 ≤ y i ≤ 1} and P_C is the metric projection onto C. Specializing to ι = Fin n recovers the textbook ℝ^n statement.
open InnerProductSpace (toDualMap)
open scoped BigOperators Pointwise
open WithLp (ofLp)
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
variable (ι)
variable {ι}
theorem prox_sum_of_k_largest_values_eq_singleton_sub_smul_metricProjection
{k : ℕ} (hk : k ≤ Fintype.card ι) (lam : ℝ) (hlam : 0 < lam) (x : E) :
prox[fun y : E ↦ (lam : EReal) * (sum_of_k_largest_values k y : EReal)] x
=
{x - lam •
(metricProjectionOfComplete
(sum_of_k_largest_constraint_set ι k)
(sum_of_k_largest_constraint_set_nonempty ι hk)
(sum_of_k_largest_constraint_set_closed ι k).isComplete
(sum_of_k_largest_constraint_set_convex ι k)
(lam⁻¹ • x) : E)}Example 6.51
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.51: if λ > 0, then the proximal set of the sum of the k largest coordinate absolute values is the singleton containing x - λ P_C(x / λ), where C = {y | ∑ i, |y i| ≤ k, |y i| ≤ 1} and P_C is the metric projection onto C. Specializing to ι = Fin n recovers the textbook ℝ^n statement.
open scoped BigOperators
open InnerProductSpace (toDualMap)
open WithLp (toLp)
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
local notation "unitWeights" => (fun _ : ι ↦ (1 : NNReal))
local notation "unitBox" => (fun _ : ι ↦ (1 : ENNReal))
variable (k : ℕ)
local notation "C" => weighted_l1_box_constraint_set unitWeights unitBox (k : ℝ)
local notation "P" => constraintProjectionPoint k
theorem prox_sum_k_largest_abs_eq_singleton_sub_smul_metricProjection
(lam : ℝ) (hlam : 0 < lam) (x : E) :
prox[fun y : E ↦ (lam : EReal) * (sum_k_largest_abs k y : EReal)] x =
{x - lam • P (lam⁻¹ • x)}Example 6.53
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.53 (1): in a complete real inner-product space, if C is nonempty, closed, and convex, then the Moreau envelope of δ_ C can be written pointwise using the metric projection P_C.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable (C : Set E)
theorem moreau_envelope_extendedIndicator_eq_indicator_metricProjection_add_sq_dist
(hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
(μ : PosReal) (x : E) :
M[μ, δ_ C] x =
(δ_ C) (Pp[C, hC_nonempty, hC_closed, hC_convex] x) +
((((1 / (2 * μ) : ℝ) * ‖x - Pp[C, hC_nonempty, hC_closed, hC_convex] x‖ ^
(2 : ℕ)) : ℝ) : EReal)Example 6.54
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.54 in owner form: in a real normed space, the Moreau envelope of the norm is the canonical Huber function viewed in EReal.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem moreau_envelope_norm_penalty_eq_huber_function (μ : PosReal) :
M[μ, norm_penalty 1] = fun x : E ↦ ((H[μ] x : ℝ) : EReal)Theorem 6.55
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.55: Definition 6.7 already states the textbook identity M[μ, f] = f □ ω(μ), so the canonical owner is reused directly here.
universe u
variable {E : Type u} [NormedAddCommGroup E]
recall moreau_envelopeCorollary 6.56
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Corollary 6.56 is source-facing in the chapter's Fenchel-conjugacy/Moreau-envelope domain. Domain sampling identifies the relevant owner-level declarations already present in the project: - conjugate_function from Definition 4.1, the chapter's core/canonical Fenchel-conjugate owner, used both on Module.Dual ℝ E and on StrongDual ℝ E through the canonical coercion; - M[μ, f] and ω(μ) from Definition 6.7 for the Moreau envelope and its quadratic kernel; - conjugate_function_infimal_convolution_eq_add from Theorem 4.7 for conjugates of infimal convolutions under the primitive hypothesis ∀ x, f x ≠ ⊥; - half_squared_norm_conjugate_eq_half_dualNorm_sq from Proposition 4.22 for the quadratic conjugate formula on Module.Dual ℝ E. Owner choice: the main corollary should stay on the source-facing primal-space surface f∗ x, while the continuous-dual statement is only a companion bridge. Primitive data: f, μ, the primal vector x, and the non-⊥ hypothesis on f. Derived API: the continuous-dual reformulation at y : StrongDual ℝ E, expressed by the same owner conjugate_function through the canonical coercion StrongDual ℝ E → Module.Dual ℝ E.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
recall conjugate_functionLemma 6.57
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 6.57: scaling the Moreau envelope by a positive scalar λ is the same as taking the Moreau envelope of the scaled function λ f with parameter μ / λ. The textbook proper, closed, and convex hypotheses on f are redundant for this scaling identity, and the owner-level equality itself does not need a separate positivity hypothesis on μ because that is already encoded by μ : PosReal.
universe u
open scoped Pointwise
variable {E : Type u} [NormedAddCommGroup E]
theorem smul_moreau_envelope_eq_moreau_envelope_scaled_function
(f : E → EReal) (μ lam : PosReal) :
(lam : EReal) • M[μ, f] =
M[μ / lam, (lam : EReal) • f]Theorem 6.58
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.58: the Moreau envelope of a finite separable sum on PiLp (2 : ENNReal) E is the sum of the coordinatewise Moreau envelopes. This is the product-space rendering of M_f^μ (x₁, …, x_m) = ∑ i, M_{f_i}^μ (x_i).
open scoped BigOperators
universe u v
variable {ι : Type v} [Fintype ι]
variable {E : ι → Type u}
variable [∀ i, NormedAddCommGroup (E i)]
theorem moreau_envelope_separableSum_eq_sum
(f : ∀ i, E i → EReal) (hdom : ∀ i, (effective_domain (f i)).Nonempty)
(μ : PosReal) (x : PiLp (2 : ENNReal) E) :
M[μ, PiLp.separableSum f] x = ∑ i, M[μ, f i] (x i)Example 6.59
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.59: for the finite-product ℓ¹ penalty f(x) = ‖x‖₁ = ∑ i |x_i|, the Moreau envelope at x is the sum of the scalar Huber values on the coordinates: M_f^μ(x) = ∑ i, M_{|·|}^μ(x_i) = ∑ i, H[μ] (x_i).
open scoped BigOperators
variable {ι : Type*} [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
theorem moreau_envelope_l1_sum_eq_sum_huber
(μ : PosReal) (x : E) :
M[μ, fun y : E ↦ (‖y‖₁ : EReal)] x = ∑ i, (H[μ] (x i) : EReal)Theorem 6.60
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.60 (1): if f is a proper closed convex extended-real-valued function and μ > 0, then the real-valued Moreau envelope x ↦ (M[μ, f] x).toReal is globally (1 / μ)-smooth.
universe u
open scoped Gradient
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
local notation:65 f " □r " ω => infimal_convolution f (fun z ↦ (ω z : EReal))
theorem moreau_envelope_toReal_is_inv_mu_smooth
(f : E → EReal) (hf_proper : IsProperExtendedRealFunction f)
(hf_closed : LowerSemicontinuous f) (hf_convex : is_convex_function f)
(μ : PosReal) :
is_l_smooth_on (fun x ↦ (M[μ, f] x).toReal) Set.univ (Real.toNNReal (1 / μ))Example 6.61
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.61 (1): for a convex set C, the half squared distance function x ↦ (1 / 2) d_C(x)^2 = (infDist x C)^2 / 2 is globally 1-smooth.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
recall half_sq_infDist_is_l_smooth
-- Proof sketch: combine the indicator/projection identification
-- `prox_extendedIndicator_eq_projection_mapping` with the singleton projection theorem
-- `projection_mapping_eq_singleton_of_nonempty_closed_convex`.Example 6.62
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.62: for a positive parameter μ, the Huber function H[μ] is globally (1 / μ)-smooth.
universe u
open Asymptotics
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem huber_function_is_inv_mu_smooth (μ : PosReal) :
is_l_smooth_on (H[μ] : E → ℝ) Set.univ (Real.toNNReal ((1 : ℝ) / μ))Theorem 6.63
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.63: if f is a proper closed convex extended-real-valued function, then at every point x there is a unique proximal point u of the scaled function (μ + 1) f, and the proximal set of the Moreau envelope M[μ, f] at x is the singleton containing lineMap x u (1 / (μ + 1)). This is the chapter's set-valued rendering of the textbook formula prox_{M_f^μ}(x) = x + (1 / (μ + 1)) (prox_{(μ + 1) f}(x) - x), stated without promoting a chosen proximal point to primitive data.
universe u
open scoped Pointwise
open AffineMap
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
variable (f : E → EReal) (μ : PosReal)
theorem prox_moreau_envelope_eq_singleton_of_proper_closed_convex
(hf_proper : IsProperExtendedRealFunction f) (hf_closed : LowerSemicontinuous f)
(hf_convex : is_convex_function f) (x : E) :
∃ u : E,
prox[((μ + 1 : ℝ) : EReal) • f] x = {u} ∧
prox[M[μ, f]] x = {lineMap x u (1 / (μ + 1) : ℝ)}Corollary 6.64
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Corollary 6.64: if f is a proper closed convex extended-real-valued function and μ, λ > 0, then at every point x there is a unique proximal point u of the scaled function (μ + λ) f, and the proximal set of the scaled Moreau envelope λ M[μ, f] at x is the singleton containing lineMap x u (λ / (μ + λ)). This is the chapter's set-valued rendering of the textbook formula prox_{λ M_f^μ}(x) = x + (λ / (μ + λ)) (prox_{(μ + λ) f}(x) - x).
universe u
open scoped Pointwise
open AffineMap
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
theorem prox_scaled_moreau_envelope_eq_singleton_of_proper_closed_convex
(f : E → EReal) (μ lam : PosReal) (hf_proper : IsProperExtendedRealFunction f)
(hf_closed : LowerSemicontinuous f) (hf_convex : is_convex_function f) (x : E) :
∃ u : E,
prox[(((μ + lam : ℝ) : EReal) • f)] x = {u} ∧
prox[(lam : EReal) • M[μ, f]] x =
{lineMap x u ((lam : ℝ) / (μ + lam : ℝ))}Example 6.65
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.65: if C is a nonempty complete convex subset of a real inner product space and λ ≥ 0, then the proximal set of y ↦ (λ / 2) d_C(y)^2 at x is the singleton containing lineMap x (P_C(x)) (λ / (λ + 1)), equivalently (λ / (λ + 1)) • P_C(x) + (1 / (λ + 1)) • x, where P_C denotes the canonical metric projection onto C. The textbook closed-subset-of-a- complete-space formulation is the downstream specialization obtained from IsClosed.isComplete. This is the chapter's set-valued rendering of prox_{(λ / 2) d_C^2}(x) = (λ / (λ + 1)) P_C(x) + (1 / (λ + 1)) x.
universe u
open Metric
open AffineMap
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable (C : Set E) (hC_nonempty : C.Nonempty) (hC_complete : IsComplete C)
(hC_convex : Convex ℝ C)
local notation "P" => metricProjectionOfComplete C hC_nonempty hC_complete hC_convex
theorem prox_half_sq_infDist_eq_singleton_metricProjection
(lam : ℝ) (hlam : 0 ≤ lam) (x : E) :
prox[fun y ↦ (((lam / 2) * infDist y C ^ 2 : ℝ) : EReal)] x =
{lineMap x (P x) (lam / (lam + 1))}Example 6.66
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.66: if μ is positive and λ ≥ 0, then the proximal set of the scaled Huber function λ H[μ] at x is the singleton obtained by radial shrinkage with denominator max ‖x‖ (μ + λ). This is the chapter's set-valued rendering of the textbook formula prox_{λ H_μ}(x) = (1 - λ / max {‖x‖, μ + λ}) x, including the endpoint λ = 0, in the real inner-product-space setting where Example 6.19 and Example 6.54 apply.
universe u
open scoped Pointwise
open AffineMap
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [ProperSpace E]
theorem prox_scaled_huber_function_eq_singleton_shrinkage
(μ : PosReal) (lam : ℝ) (hlam : 0 ≤ lam) (x : E) :
prox[fun y : E ↦ ((lam * H[μ] y : ℝ) : EReal)] x =
{(1 - lam / max ‖x‖ (μ + lam)) • x}Theorem 6.67
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 6.67 is source-facing in the chapter's Moreau-envelope/Fenchel-conjugacy domain. Domain sampling identifies the owner chain already fixed upstream: - M[μ, f] and ω(μ) from Definition 6.7 are the core/canonical owners for the Moreau envelope and its quadratic term; - the source-facing primal conjugate surface is the notation f∗ from Definition 4.1; - Theorem 6.3 supplies the canonical singleton proximal point for the scaled function μ f; - Theorem 6.45 is the owner-level Moreau decomposition for those two scaled proximal problems; - Theorem 4.10 provides the Fenchel--Young equality bridge at the resulting primal/dual pair. Primitive data: f, μ, x, and the source hypotheses hf_proper, hf_closed, hf_convex, with positivity carried by the parameter type. The proper/closed/convex hypotheses are semantically active because they produce the singleton proximal point of μ f needed to evaluate the Moreau envelope and to invoke the scaled Moreau-decomposition theorem. Derived API: the quadratic term should be stated through the chapter owner ω(μ), not by a duplicate inline formula.
universe u
open InnerProductSpace (toDualMap)
open scoped Pointwise
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
recall conjugate_function_primalLemma 6.68
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 6.68, active branch: if A A† is invertible and λ < ‖(A A†)⁻¹ (A x)‖, then there is a unique positive shift α solving ‖(A A† + α I)⁻¹ (A x)‖ = λ. This is the branch-local multiplier from the textbook KKT description; it is not promoted to a global chosen definition.
open scoped InnerProduct
universe u v
variable {V : Type u} [NormedAddCommGroup V] [InnerProductSpace ℝ V] [CompleteSpace V]
variable {W : Type v} [NormedAddCommGroup W] [InnerProductSpace ℝ W] [CompleteSpace W]
variable (A : V →L[ℝ] W)
local notation "G" => A ∘L A†
theorem existsUnique_linear_image_norm_prox_shift
(hG : (G).IsInvertible)
(lam : ℝ) (hlam : 0 < lam) (x : V)
(hlarge : lam < ‖(G).inverse (A x)‖) :
∃! α : ℝ,
0 < α ∧
‖(G + α • 1).inverse (A x)‖ = lamLemma 6.69
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 6.69: for a finite nonempty index type ι, the minimum over the standard simplex Δ = stdSimplex ℝ ι of the coordinate presentation λ ↦ ∑ j, φ(x_j, λ_j) of the separable variational objective is the squared ℓ¹ norm ‖x‖₁². Specializing to ι = Fin n recovers the textbook Δ_n ⊆ ℝ^n statement.
open scoped BigOperators
open WithLp (toLp)
variable {ι : Type*} [Fintype ι] [Nonempty ι]
local notation "Δ" => stdSimplex ℝ ι
local notation "E" => EuclideanSpace ℝ ι
theorem l1SquareVariationalObjective_sInf_eq_sq_l1_norm (x : E) :
sInf ((fun lam : ι → ℝ ↦ ∑ j, φ (x j, lam j)) '' Δ) =
((‖x‖₁ ^ (2 : ℕ) : ℝ) : EReal)Lemma 6.70
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 6.70: let f(x) = ‖x‖₁² and ρ > 0. If μ is a positive root of ψ(μ) = ∑ i [√ρ |x_i| / √μ - 2ρ]_+ - 1 whenever x ≠ 0, then the proximal mapping of ρ f at x is {0} for x = 0, and otherwise it is the singleton whose i-th coordinate is λ_i x_i / (λ_i + 2ρ) with λ_i = [√ρ |x_i| / √μ - 2ρ]_+.
open WithLp (toLp)
open scoped BigOperators SoftThreshold
variable {ι : Type*}
local notation "E" => EuclideanSpace ℝ ι
variable [Fintype ι]
theorem prox_squared_l1_norm_penalty_eq_singleton_piecewise
(ρ μ : ℝ) (hρ : 0 < ρ) (x : E)
(hμ : x ≠ 0 → 0 < μ ∧ l1SquareProxRootFunction ρ x μ = 0) :
prox[fun y : E ↦ ((ρ * ‖y‖₁ ^ (2 : ℕ) : ℝ) : EReal)] x =
if _hx : x = 0 then
{(0 : E)}
else
{toLp 2 (fun i ↦
(l1SquareProxWeight ρ μ x i * x i) /
(l1SquareProxWeight ρ μ x i + 2 * ρ))}Lemma 6.71
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Lemma 6.71: if s ≤ Fintype.card ι, then the Euclidean projection set onto the transported set toLp 2 '' C_s of s-sparse vectors is exactly the image of the optimal support sets under the transported masking map S ↦ toLp 2 ((↑S : Set ι).indicator x.ofLp), where S has cardinality s and captures the s largest absolute coordinates of x through the owner sum_k_largest_abs. Specializing to ι = Fin n recovers the textbook ℝ^n statement.
open scoped BigOperators
open InnerProductSpace (toDualMap)
open WithLp (toLp)
variable {ι : Type*} [Fintype ι] [DecidableEq ι]
local notation "E" => EuclideanSpace ℝ ι
theorem projection_mapping_sSparseVectors_eq_top_abs_coordinate_projections
{s : ℕ} (hs : s ≤ Fintype.card ι) (x : E) :
P[(toLp 2 '' (C_[s] : Set (ι → ℝ)) : Set E)] x =
(fun S : Finset ι ↦ toLp 2 ((↑S : Set ι).indicator x.ofLp)) ''
{S : Finset ι |
S.card = s ∧
S.sum (fun i ↦ |x i|) = sum_k_largest_abs s x}Example 6.72
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Example 6.72: when n = 4, the projection of (2, 3, -2, 1)^T onto the set C_2 of 2-sparse vectors consists exactly of the two vectors obtained by keeping the coordinates indexed by {0, 1} or {1, 2} and zeroing out the others.
open WithLp (toLp)
open scoped BigOperators
local notation "E" => EuclideanSpace ℝ (Fin 4)
local notation "x₀" => (!₂[2, 3, -2, 1] : E)
local notation "y₀" => (!₂[2, 3, 0, 0] : E)
local notation "z₀" => (!₂[0, 3, -2, 0] : E)
theorem projection_mapping_sSparseVectors_two_example_eq_two_point_set :
P[toLp 2 '' C_[2]] !₂[(2 : ℝ), 3, -2, 1] =
{!₂[(2 : ℝ), 3, 0, 0], !₂[(0 : ℝ), 3, -2, 0]}Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
EuclideanL1Norm.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
-
Lemma_6_26/Halfspace.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.