Chapter 19 — Duality in Convex Optimization
Proofs omitted. Hover over highlighted terms to see their Lean types.
Theorem 19.1
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Theorem 19.1: for f ∈ Γ₀(ℋ) and g ∈ Γ₀(𝒦), the following are equivalent for x ∈ ℋ and v ∈ 𝒦: (i) x minimizes z ↦ f z + g (L z), v minimizes w ↦ f^*(-L^* w) + g^*(w), and the primal infimum equals the negative of the dual infimum; (ii) -L^* v ∈ ∂ f(x) and v ∈ ∂ g(Lx); (iii) x ∈ ∂ f^*(-L^* v) ∩ L⁻¹(∂ g^*(v)), with f^* and g^* represented by f∗[hf] and g∗[hg].
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K]
theorem primal_dual_solution_tfae_for_composite_objective
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H))
{g : K → Set.Ioi (⊥ : EReal)} (hg : g ∈ Γ₀(K))
(L : H →L[ℝ] K)
(x : H) (v : K) :
List.TFAE
[x ∈ Argmin (compositePrimalObjective f g L) ∧
v ∈ Argmin (compositeDualObjective f g L) ∧
compositePrimalOptimalValue f g L = -compositeDualOptimalValue f g L,
-L.adjoint v ∈ (∂ f) x ∧
v ∈ (∂ g) (L x),
x ∈ (∂ (f∗[hf])) (-L.adjoint v) ∩
L ⁻¹' ((∂ (g∗[hg])) v)]Corollary 19.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 19.2: if f ∈ Γ₀(ℋ) and g ∈ Γ₀(𝒦), if the primal infimum of x ↦ f x + g (L x) is the negative of the minimum of the dual objective v ↦ f^*(-L^* v) + g^*(v), and if v is a dual solution, then the primal solution set is ∂ f^*(-L^* v) ∩ L⁻¹(∂ g^*(v)), represented by the canonical Γ₀ conjugates f∗[hf] and g∗[hg].
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K]
-- Proof sketch: for any `x`, combine dual optimality of `v` with the strong-duality equality to
-- rewrite clause (i) of Theorem 19.1 as `x ∈ Argmin (f + g ∘ L)`. Then use the equivalence
-- between clause (i) and clause (iii) from `primal_dual_solution_tfae_for_composite_objective`,
-- whose conjugate terms already use the canonical packaged owners `f∗[hf]` and `g∗[hg]`, and
-- conclude the set equality by extensionality.
theorem argmin_add_comp_eq_conjugateSubdifferential_inter_preimage_of_dual_solution
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H))
{g : K → Set.Ioi (⊥ : EReal)} (hg : g ∈ Γ₀(K))
(L : H →L[ℝ] K) (v : K)
(hstrong : compositePrimalOptimalValue f g L = -compositeDualOptimalValue f g L)
(hv : v ∈ Argmin (compositeDualObjective f g L)) :
Argmin (compositePrimalObjective f g L) =
(∂ (f∗[hf])) (-L.adjoint v) ∩
L ⁻¹' ((∂ (g∗[hg])) v)Example 19.3
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 19.3: the textbook perturbation is the specialization of the canonical composite perturbation to f = h - ⟪·, z⟫ and g = ⨁ i, gᵢ(· - rᵢ).
open scoped BigOperators ERealFunction InnerProductSpace
universe u v
namespace ERealFunction
open ContinuousLinearMap
variable {I : Type v}
variable {H : Type u} {K : I → Type u}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable [∀ i, NormedAddCommGroup (K i)] [∀ i, InnerProductSpace ℝ (K i)]
-- Proof sketch: `h x` lies in `]-∞,+∞]`, and subtracting the finite linear term `⟪x, z⟫`
-- preserves the strict inequality above `⊥`.
@[simp] theorem compositePerturbationFunction_linearTilt_shiftedHilbertSum_apply
(z : H) (h : H → Set.Ioi (⊥ : EReal)) (r : lp K 2)
(g : ∀ i, K i → Set.Ioi (⊥ : EReal)) (L : H →L[ℝ] lp K 2) (x : H) (y : lp K 2) :
(compositePerturbationFunction (linearTilt z h) (shiftedHilbertSum r g) L (x, y) : EReal) =
(h x : EReal) - ((⟪x, z⟫_ℝ : ℝ) : EReal) +
(⨁ i, fun yi ↦ (g i (yi - r i) : EReal)) (L x + y)Proposition 19.4
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 19.4: if f ∈ Γ₀(ℋ) and g ∈ Γ₀(𝒦), if the primal infimum of x ↦ f x + g (L x) equals the negative minimum of the dual objective v ↦ f^*(-L^* v) + g^*(v), and if v is a dual solution at which f^* has Gâteaux gradient xstar at -L^* v, then every primal solution is xstar.
open InnerProductSpace
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K]
theorem eq_of_mem_argmin_add_comp_of_dual_solution_and_hasGateauxDerivativeAt_conjugate
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H))
{g : K → Set.Ioi (⊥ : EReal)} (hg : g ∈ Γ₀(K))
(L : H →L[ℝ] K) (v : K) (xstar : H)
(hstrong : compositePrimalOptimalValue f g L = -compositeDualOptimalValue f g L)
(hv : v ∈ Argmin (compositeDualObjective f g L))
(hgrad :
HasGateauxDerivativeAt
(fun y : H ↦ (f∗[hf] y : EReal).toReal)
(toDual ℝ H xstar) (-L.adjoint v))
(x : H) (hx : x ∈ Argmin (compositePrimalObjective f g L)) :
x = xstarProposition 19.5
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 19.5: if φ ∈ Γ₀(ℋ), ψ ∈ Γ₀(𝒦), and r ∈ sri (L (dom φ) - dom ψ), then the dual problem v ↦ (1 / 2) ‖z - L^* v‖² - {}¹φ(z - L^* v) + ψ^*(v) + ⟪v, r⟫ has a solution. Moreover, for every dual solution v, the unique minimizer of x ↦ φ(x) + ψ(Lx - r) + (1 / 2) ‖x - z‖² is Prox_φ (z - L^* v). The companion bridge theorem perturbationDualObjective_proximalCompositePerturbationFunction records the equivalent dual formula (19.9) with the canonical conjugate surface ψ∗[hψ].
open Set
open scoped InnerProductSpace Pointwise
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K]
-- Proof sketch: specialize Proposition 19.20 (3) to the perturbation above, then rewrite the
-- conjugate of the regularized factor as the unit Moreau envelope of `φ*` and the conjugate of
-- the translated factor as `ψ* + ⟪·, r⟫`, using the canonical packaged conjugate `ψ∗[hψ]`.
theorem
argmin_proximalCompositeDual_nonempty_and_argmin_primal_eq_singleton_proximityOperator
{φ : H → Set.Ioi (⊥ : EReal)} (hφ : φ ∈ Γ₀(H))
{ψ : K → Set.Ioi (⊥ : EReal)} (hψ : ψ ∈ Γ₀(K))
(z : H) (r : K) (L : H →L[ℝ] K)
(hsri : r ∈ sri (L '' effectiveDomain φ - effectiveDomain ψ)) :
(Argmin
(fun v : K ↦
((((1 / 2 : ℝ) * ‖z - L.adjoint v‖ ^ 2 : ℝ) : EReal) -
({}^[(1 : PosReal)] φ) (z - L.adjoint v)) +
(ψ∗[hψ] v : EReal) +
((⟪v, r⟫_ℝ : ℝ) : EReal))).Nonempty ∧
∀ {v : K},
v ∈
Argmin
(fun v : K ↦
((((1 / 2 : ℝ) * ‖z - L.adjoint v‖ ^ 2 : ℝ) : EReal) -
({}^[(1 : PosReal)] φ) (z - L.adjoint v)) +
(ψ∗[hψ] v : EReal) +
((⟪v, r⟫_ℝ : ℝ) : EReal)) →
Argmin
(fun x : H ↦
(φ x : EReal) + (ψ (L x - r) : EReal) +
((((1 / 2 : ℝ) * ‖x - z‖ ^ 2 : ℝ) : EReal))) =
({Prox[φ, hφ] (z - L.adjoint v)} : Set H)Corollary 19.7
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 19.7 (1): if φ ∈ Γ₀(ℋ) and ‖L‖ ≤ 1, then the map v ↦ r + v - L (Prox_φ (z - L^* v)) is firmly nonexpansive.
open SubtypeFirmness
-- Declarations for this item will be appended below by the statement pipeline.
open Set
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K]
theorem proximalConstraintDualMap_firmlyNonexpansive_of_mem_gammaZero
{φ : H → Set.Ioi (⊥ : EReal)} (hφ : φ ∈ Γ₀(H))
(z : H) (r : K) (L : H →L[ℝ] K) (hL : ‖L‖ ≤ 1) :
FirmlyNonexpansive (proximalConstraintDualMap φ hφ z r L)Example 19.10
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 19.10: if C and D are closed convex subsets of real Hilbert spaces and 0 ∈ sri (L(C) - D), then the dual problem v ↦ (1 / 2) ‖z - L^* v‖² - (1 / 2) d_C(z - L^* v)² + σ[D] v has a solution; moreover, for every dual solution v, the unique minimizer of ‖x - z‖ over x ∈ C with L x ∈ D is P_C (z - L^* v).
open Set
open scoped InnerProductSpace Pointwise
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K]
variable {C : Set H} (hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
variable {D : Set K} (hD_closed : IsClosed D) (hD_convex : Convex ℝ D)
variable (z : H) (L : H →L[ℝ] K)
variable (hsri : (0 : K) ∈ sri (L '' C - D))
local notation "hC_cheb" =>
isChebyshev_of_nonempty_isClosed_convex
(nonempty_of_zero_mem_sri_image_sub_left C D L hsri) hC_closed hC_convex
local notation "P_C" => P[C, hC_cheb]
-- Proof sketch: apply Proposition 19.5 with `φ = ι_C`, `ψ = ι_D`, and `r = 0`. Rewrite the dual
-- objective by the indicator Moreau-envelope formula and the conjugate of an indicator as a
-- support function. Then identify the proximal point of `ι_C` with the metric projection onto
-- `C`, and use that minimizing `‖x - z‖` over the feasible set is equivalent to minimizing
-- `(1 / 2) ‖x - z‖²`.
theorem argmin_bestApproximationDual_nonempty_and_argminOn_norm_eq_singleton_projectionPoint :
(Argmin
(fun v : K ↦
((((1 / 2 : ℝ) * ‖z - L.adjoint v‖ ^ 2 : ℝ) : EReal) -
((((1 / 2 : ℝ) * (Metric.infDist (z - L.adjoint v) C) ^ 2 : ℝ) : EReal))) +
σ[D] v)).Nonempty ∧
∀ {v : K},
v ∈
Argmin
(fun v : K ↦
((((1 / 2 : ℝ) * ‖z - L.adjoint v‖ ^ 2 : ℝ) : EReal) -
((((1 / 2 : ℝ) * (Metric.infDist (z - L.adjoint v) C) ^ 2 : ℝ) : EReal))) +
σ[D] v) →
Argmin[C ∩ L ⁻¹' D] (fun x : H ↦ ‖x - z‖) =
({P_C (z - L.adjoint v)} : Set H)Definition 19.11
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
The objective function of the primal perturbation problem associated with F.
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [Zero K]
def perturbationPrimalObjective (F : H × K → Set.Ioi (⊥ : EReal)) : H → EReal :=
fun x ↦ (F (x, 0) : EReal)Proposition 19.12
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 19.12 (1): if ϑ = Prod.snd ▷ F, then ϑ* is the dual objective v ↦ F^*(0, v) of F.
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K]
-- Proof sketch: expand the conjugate of the value function `Prod.snd ▷ F` directly on `K`, use
-- `infimalPostcomposition_snd_apply` to rewrite the value function as the fiberwise infimum of the
-- slices `x ↦ F (x, y)`, and then commute the outer supremum in `y` with the inner infimum in `x`
-- to obtain the explicit dual-objective formula `v ↦ F^*(0, v)`.
theorem conjugate_valueFunction_eq_dualObjective
(F : H × K → Set.Ioi (⊥ : EReal)) :
(Prod.snd ▷ F)∗ = perturbationDualObjective FProposition 19.13
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 19.13: if the canonical value function Prod.snd ▷ F is convex, lower semicontinuous at the origin, and finite there in the canonical sense 0 ∈ effectiveDom (Prod.snd ▷ F), then the primal infimum inf_x F(x, 0) equals the negative dual infimum - inf_v F^*(0, v).
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K]
-- Proof sketch: Proposition 13.44 identifies the value at `0` of the canonical value function
-- `Prod.snd ▷ F` with its biconjugate there from the convexity, lower semicontinuity, and
-- effective-domain hypotheses. Finally,
-- Proposition 19.12 rewrites that biconjugate value as the negative infimum of the dual slice
-- `v ↦ F^*(0, v)`.
theorem valueFunction_zero_eq_neg_sInf_perturbationDualObjective_of_lscAt_and_finite
(F : H × K → Set.Ioi (⊥ : EReal)) (hconv : IsConvex (Prod.snd ▷ F))
(hlsc : LowerSemicontinuousAt (Prod.snd ▷ F) (0 : K))
(hzero : (0 : K) ∈ effectiveDom (Prod.snd ▷ F)) :
(Prod.snd ▷ F) 0 = -sInf (Set.range (perturbationDualObjective F))Proposition 19.14
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 19.14 (1): the dual solution set U = Argmin (perturbationDualObjective F) equals the subdifferential of the biconjugate of the value function at the origin.
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K]
-- Proof sketch: Proposition 19.12 identifies `perturbationDualObjective F` with the
-- Fenchel conjugate
-- `(Prod.snd ▷ F)∗`. Fermat's rule rewrites the argmin set of that conjugate as the zero set of
-- its subdifferential, and the Fenchel--Young/subdifferential correspondence for the conjugate
-- turns that zero condition into membership in `∂ ((Prod.snd ▷ F)∗∗) (0)`.
theorem argmin_perturbationDualObjective_eq_subdifferential_biconjugate_valueFunction_zero
(F : H × K → Set.Ioi (⊥ : EReal)) (hproper : IsProper ((Prod.snd ▷ F)∗)) :
Argmin (perturbationDualObjective F) = (∂ ((Prod.snd ▷ F)∗∗)) 0Proposition 19.15
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 19.15: for F ∈ Γ₀(ℋ × 𝒦) and (x, v) ∈ ℋ × 𝒦, the following are equivalent: (i) x is a primal solution, v is a dual solution, and strong duality holds; (ii) F(x, 0) + F^*(0, v) = 0; (iii) (0, v) ∈ ∂ F(x, 0); (iv) (x, 0) ∈ ∂ F^*(0, v), with F^* represented by F∗[hF].
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K]
theorem primal_dual_solution_tfae_for_perturbation_function
(F : H × K → Set.Ioi (⊥ : EReal)) (hF : F ∈ Γ₀(H × K)) (x : H) (v : K) :
List.TFAE
[x ∈ Argmin (perturbationPrimalObjective F) ∧
v ∈ Argmin (perturbationDualObjective F) ∧
sInf (Set.range (perturbationPrimalObjective F)) =
-sInf (Set.range (perturbationDualObjective F)),
(F (x, 0) : EReal) + (F∗[hF] (0, v) : EReal) = 0,
((0 : H), v) ∈ (∂ F) (x, 0),
(x, (0 : K)) ∈ (∂ (F∗[hF])) (0, v)]Definition 19.16
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Definition 19.16: the Lagrangian associated with F : H × K → ]-∞,+∞] is the extended-real-valued function (x, v) ↦ inf_y (F(x, y) - ⟪y, v⟫), expressed through the canonical first-projection infimal postcomposition owner.
open Set
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K]
def lagrangian (F : H × K → Set.Ioi (⊥ : EReal)) (x : H) (v : K) : EReal :=
(Prod.fst ▷ fun p : H × K ↦ (F p : EReal) - (⟪p.2, v⟫_ℝ : EReal)) x
notation3:max "ℒ[" F "]" => lagrangian FProposition 19.17
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 19.17 (1): clause (i). For every x, the fiber v ↦ ℒ[F] x v is upper semicontinuous and concave, expressed canonically as convexity of its negation.
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K]
theorem lagrangian_upperSemicontinuous_and_concave_in_second_variable
(F : H × K → Set.Ioi (⊥ : EReal)) (x : H) :
UpperSemicontinuous (ℒ[F] x) ∧
IsConvex (fun v ↦ -(ℒ[F] x v))Corollary 19.18
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 19.18: a point v minimizes the dual objective exactly when the infimum of the Lagrangian fiber x ↦ ℒ[F] x v equals the supremum over w of the infima of the fibers x ↦ ℒ[F] x w.
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K]
-- Proof sketch: rewrite `v ∈ Argmin (perturbationDualObjective F)` as minimization of the dual
-- objective. Then apply Proposition 19.17(iv) to rewrite each dual objective value `F^*(0, w)` as
-- the negative of the infimum of the Lagrangian fiber over `H`, and convert minimizing
-- `F^*(0, ·)` into maximizing `w ↦ inf_x ℒ[F] x w`.
theorem mem_argmin_perturbationDualObjective_iff_lagrangian_sInf_eq_sSup
(F : H × K → Set.Ioi (⊥ : EReal)) (v : K) :
v ∈ Argmin (perturbationDualObjective F) ↔
sInf (Set.range fun x ↦ ℒ[F] x v) =
sSup (Set.range fun w ↦ sInf (Set.range fun x ↦ ℒ[F] x w))Corollary 19.19
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 19.19: for F ∈ Γ₀(ℋ ⊕ 𝒦) and (x, v) ∈ ℋ × 𝒦, the following are equivalent: (i) x is a primal solution, v is a dual solution, and strong duality holds; (ii) F(x, 0) + F^*(0, v) = 0; (iii) (0, v) ∈ ∂ F(x, 0); (iv) (x, 0) ∈ ∂ F^*(0, v); (v) (x, v) is a saddle point of ℒ[F], with F^* represented by F∗[hF].
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K]
theorem primal_dual_solution_and_lagrangian_saddlePoint_tfae
(F : H × K → Set.Ioi (⊥ : EReal)) (hF : F ∈ Γ₀(H × K)) (x : H) (v : K) :
List.TFAE
[x ∈ Argmin (perturbationPrimalObjective F) ∧
v ∈ Argmin (perturbationDualObjective F) ∧
sInf (Set.range (perturbationPrimalObjective F)) =
-sInf (Set.range (perturbationDualObjective F)),
(F (x, 0) : EReal) + (F∗[hF] (0, v) : EReal) = 0,
((0 : H), v) ∈ (∂ F) (x, 0),
(x, (0 : K)) ∈ (∂ (F∗[hF])) (0, v),
IsSaddlePointOn (Set.univ : Set H) (Set.univ : Set K) (ℒ[F]) x v]Proposition 19.20
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 19.20 (2): the primal problem associated with the perturbation F(x,y) = f(x) + g(Lx + y) is the minimization of x ↦ f(x) + g(Lx).
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [SeminormedAddCommGroup H] [NormedSpace ℝ H]
variable [SeminormedAddCommGroup K] [NormedSpace ℝ K]
-- Proof sketch: both summands lie in `]-∞,+∞]`, and the sum of two values strictly above `-∞`
-- still lies in `]-∞,+∞]`.
theorem perturbationPrimalObjective_compositePerturbationFunction
(f : H → Set.Ioi (⊥ : EReal)) (g : K → Set.Ioi (⊥ : EReal)) (L : H →L[ℝ] K) :
perturbationPrimalObjective (compositePerturbationFunction f g L) =
compositePrimalObjective f g LProposition 19.21
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 19.21 (2): the primal problem attached to the equality-constraint perturbation is the constrained minimization of f over L ⁻¹' {r}.
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
-- Proof sketch: specialize the canonical indicator owner `ι[C]` to the singleton `{r}`.
theorem perturbationPrimalObjective_equalityConstraintPerturbationFunction
[SeminormedAddCommGroup H] [NormedSpace ℝ H]
[SeminormedAddCommGroup K] [NormedSpace ℝ K]
(f : H → Set.Ioi (⊥ : EReal)) (L : H →L[ℝ] K) (r : K) :
perturbationPrimalObjective (equalityConstraintPerturbationFunction f L r) =
fun x : H ↦ if L x = r then (f x : EReal) else ⊤Remark 19.22
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
The unconstrained affine objective obtained from the equality-constraint Lagrangian after freezing the multiplier v, written in the primitive pairing form f x + ⟪L x, v⟫. In complete Hilbert spaces this agrees with f x + ⟪x, L.adjoint v⟫.
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {K : Type v}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable [NormedAddCommGroup K] [InnerProductSpace ℝ K]
def equalityConstraintAffineObjective
(f : H → Set.Ioi (⊥ : EReal)) (L : H →L[ℝ] K) (v : K) : H → ERealCorollary 19.23
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 19.23: if f ∈ Γ₀(H) and the constraint vector ρ is attained by x ↦ (⟪x, u_i⟫)_i on effectiveDomain f, then the perturbation function from (19.45) belongs to Γ₀(H × ℝ^m).
open scoped BigOperators InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable {m : ℕ}
local notation "ConstraintSpace" => EuclideanSpace ℝ (Fin m)
theorem coordinateEqualityConstraintPerturbation_mem_gammaZero
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H))
(u : Fin m → H) (ρ : ConstraintSpace)
(hρ : ρ ∈ equalityCoordinateMap u '' effectiveDomain f) :
equalityConstraintPerturbationFunction f (equalityCoordinateMap u) ρ ∈
Γ₀(H × ConstraintSpace)Definition 19.24
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Definition 19.24: a map R : H → E is convex with respect to K when, for every x, y ∈ H and every α ∈ ]0, 1[, the strict Jensen defect R (α • x + (1 - α) • y) - α • R x - (1 - α) • R y belongs to K.
universe u v
namespace Function
variable {𝕜 : Type*} {H : Type u} {E : Type v}
variable [Ring 𝕜] [Preorder 𝕜]
variable [AddCommMonoid H] [Module 𝕜 H] [AddCommGroup E] [Module 𝕜 E]
def IsConvexWithRespectTo (𝕜 : Type*) [Ring 𝕜] [Preorder 𝕜] [Module 𝕜 H] [Module 𝕜 E]
(R : H → E) (K : Set E) : Prop :=
∀ x y {α : 𝕜}, α ∈ Set.Ioo (0 : 𝕜) 1 →
R (α • x + (1 - α) • y) - α • R x - (1 - α) • R y ∈ K
-- Proof sketch: unfold `IsConvexWithRespectTo` and apply the defining clause at the given
-- points `x`, `y`, and coefficient `α ∈ ]0, 1[`.Proposition 19.25
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 19.25 (2): the primal objective of the inequality-constraint perturbation is f(x) on the feasible set {x | R x ∈ K} and +∞ outside it, so the primal problem is to minimize f subject to R x ∈ K.
open Set
open scoped InnerProductSpace Pointwise
universe u v
namespace ERealFunction
variable {H : Type u} {G : Type v}
variable [Add G]
variable [AddZeroClass G]
-- Proof sketch: evaluate `perturbationPrimalObjective` at `0 ∈ G` and note that
-- `R x + 0 ∈ K` is equivalent to `R x ∈ K`.
theorem perturbationPrimalObjective_inequalityConstraintPerturbation
(f : H → Set.Ioi (⊥ : EReal)) (R : H → G) (K : Set G) :
perturbationPrimalObjective (inequalityConstraintPerturbation f R K) =
fun x : H ↦ if R x ∈ K then (f x : EReal) else ⊤Remark 19.26
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Remark 19.26: if (x̄, v̄) is a saddle point of the Lagrangian attached to the inequality- constraint perturbation, then the associated multiplier v̄ makes x̄ solve the unconstrained minimization problem min_x f x + ⟪R x, v̄⟫.
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {H : Type u} {G : Type v}
variable [NormedAddCommGroup G] [InnerProductSpace ℝ G]
theorem mem_argmin_of_isInequalityConstraintLagrangeMultiplier
(f : H → Set.Ioi (⊥ : EReal))
(R : H → G) (K : Set G)
(hK_nonempty : K.Nonempty) (hK_cone : IsCone K)
{xbar : H} {vbar : G}
(hsaddle :
IsSaddlePointOn (Set.univ : Set H) (Set.univ : Set G)
(ℒ[inequalityConstraintPerturbation f R K]) xbar vbar) :
xbar ∈ Argmin (fun x : H ↦ (f x : EReal) + (⟪R x, vbar⟫_ℝ : EReal))Example 19.27
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 19.27: the perturbation attached to minimizing f over the translated cone z + K, implemented as the canonical inequality-constraint perturbation for the translation map x ↦ x - z.
open Set
open scoped InnerProductSpace Pointwise
universe u
namespace ERealFunction
variable {H : Type u}
variable [AddCommGroup H]
abbrev translatedConePerturbation
(f : H → Set.Ioi (⊥ : EReal)) (z : H) (K : Set H) :
H × H → Set.Ioi (⊥ : EReal) :=
inequalityConstraintPerturbation f (fun x ↦ x - z) K
-- Proof sketch: unfold `translatedConePerturbation`, rewrite
-- `x - z + y ∈ K ↔ x ∈ ({z - y} : Set H) + K`, and then simplify the indicator term via the
-- canonical owner `inequalityConstraintPerturbation`.Example 19.28
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 19.28 (1): clause (i). If φ ∈ Γ₀(ℝ) and 0 ∈ dom φ, then the perturbation function F from (19.67) belongs to Γ₀(ℝ² × ℝ).
open Set
namespace ERealFunction
open scoped InnerProductSpace Pointwise
variable (φ : ℝ → Set.Ioi (⊥ : EReal))
theorem lorentzConstraintPerturbation_mem_gammaZero
(hφ : φ ∈ Γ₀(ℝ)) (hφ0 : 0 ∈ effectiveDomain φ) :
lorentzConstraintPerturbation φ ∈ Γ₀((ℝ × ℝ) × ℝ)Remark 19.29
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Remark 19.29: in the setting of Example 19.28, if γ < φ(0) then the Lagrangian of the Lorentz-constraint perturbation has no saddle point.
namespace ERealFunction
variable (φ : ℝ → Set.Ioi (⊥ : EReal))
-- Proof sketch: Example 19.28 (9) characterizes existence of a saddle point by the equality
-- `phiRangeInfimum φ = (φ 0 : EReal)`. A strict inequality between these two values therefore
-- excludes saddle points.
lemma not_exists_saddlePoint_lorentzConstraintPerturbation_of_phiRangeInfimum_lt
(hφ : φ ∈ Γ₀(ℝ)) (hφ0 : 0 ∈ effectiveDomain φ)
(hγ : phiRangeInfimum φ < (φ 0 : EReal)) :
¬ ∃ ξ : ℝ × ℝ, ∃ v : ℝ,
IsSaddlePointOn (Set.univ : Set (ℝ × ℝ)) (Set.univ : Set ℝ)
(ℒ[lorentzConstraintPerturbation φ]) ξ vCorollary 19.30
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 19.30 (1): if f ∈ Γ₀(H), each real-valued g_i belongs to Γ₀(H) after coercion, and the mixed inequality/equality system is feasible, then the perturbation function from formula (19.74) belongs to Γ₀(H × ℝ^m) in the split-coordinate model EuclideanSpace ℝ (Fin p ⊕ Fin (m - p)).
open scoped BigOperators InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable {m p : ℕ} {hp : p ≤ m}
local notation "ConstraintSpace" => EuclideanSpace ℝ (Fin p ⊕ Fin (m - p))
theorem mixedConstraintPerturbation_mem_gammaZero
(f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H))
(g : Fin p → H → ℝ) (hg : ∀ i : Fin p, (g i).toEReal ∈ Γ₀(H))
(u : Fin (m - p) → H) (ρ : Fin (m - p) → ℝ)
(hfeas : HasMixedConstraintFeasiblePoint f g u ρ) :
mixedConstraintPerturbation f g u ρ ∈
Γ₀(H × ConstraintSpace)Remark 19.31
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Remark 19.31: in Corollary 19.30, the inequality-block coordinates of a saddle-point parameter vector are the Lagrange multipliers associated with the primal solution, they satisfy complementary slackness, and if dom f is nonempty then any strictly inactive inequality constraint has zero multiplier.
universe u
namespace ERealFunction
variable {H : Type u}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable {m p : ℕ}
local notation "ConstraintSpace" => EuclideanSpace ℝ (Fin p ⊕ Fin (m - p))
-- Proof sketch: use the explicit branch formula for the mixed-constraint Lagrangian. A finite
-- comparison point of `f` rules out negative inequality multipliers, then rules out
-- `x̄ ∉ dom f`. After
-- that, replacing the `i`-th multiplier by `0` still preserves dual feasibility, and strict
-- inactivity makes the resulting Lagrangian value strictly larger unless `ν̄_i = 0`.
theorem inequalityMultiplier_eq_zero_of_strictlyInactiveConstraint
(f : H → Set.Ioi (⊥ : EReal))
(g : Fin p → H → ℝ)
(u : Fin (m - p) → H) (ρ : Fin (m - p) → ℝ)
(hdom : (effectiveDomain f).Nonempty)
{xbar : H} {νbar : ConstraintSpace}
(hsaddle :
IsSaddlePointOn (Set.univ : Set H)
(Set.univ : Set ConstraintSpace)
(ℒ[mixedConstraintPerturbation f g u ρ]) xbar νbar)
(i : Fin p) (hstrict : g i xbar < 0) :
νbar (Sum.inl i) = 0