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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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

Proposition 19.5

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

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 F

Proposition 19.13

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

Source header · Attribution source

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.

Source header · Attribution source

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

Proposition 19.15

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

Source header · Attribution source

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.

Source header · Attribution source

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 F

Proposition 19.17

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

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 L

Proposition 19.21

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

Source header · Attribution source

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.

Source header · Attribution source

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 → EReal

Corollary 19.23

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

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 φ]) ξ v

Corollary 19.30

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

Source header · Attribution source

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.

Source header · Attribution source

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