import DeqMdErratum.ProximalStep

/-!
# Lemma 2: Regularity on `K_β`, Sublevel Inclusion, and Relative Smoothness

This module formalizes Lemma 2 of the erratum (pp. 2–3) together with the basic structural
properties of `Ψ`:
* `Psi_isProper`, `Psi_lowerSemicontinuous`, `Psi_bddBelow`.
* `K_beta_convex`, `K_beta_isClosed`, `K_beta_isCompact`.
* `K_beta_ax_lower_bound`: uniform positive lower bound `(Ax)_i ≥ c_β > 0` whenever `y_i > 0`,
  giving `K_beta P β ⊆ UPos P` and `Disjoint (K_beta P β) (singularSet P)`.
* `grad_FSmooth_lipschitzOn_K_beta`: `∇F` is `M_β`-Lipschitz on `K_β`.
* `L_beta_shiftedBurg_sub_FSmooth_convexOn` and `FSmooth_bregman_upper_bound`: for
  `L_β := M_β (a + ξ)²`, `L_β h_ξ - F` is convex on `K_β` and `F` satisfies the Bregman descent
  inequality relative to `h_ξ` on `K_β`.
* `L0_subset_K_beta0`: `L₀ ⊆ K_{β₀}`.
-/

open Filter Topology
open scoped BigOperators InnerProductSpace

namespace DeqMdErratum

section PsiProperties

variable {m n : ℕ}

lemma lowerSemicontinuous_ereal_add {f g : E n → EReal}
    (hf : LowerSemicontinuous f) (hg : LowerSemicontinuous g)
    (hf_bot : ∀ x, f x ≠ ⊥) (hg_bot : ∀ x, g x ≠ ⊥) :
    LowerSemicontinuous (fun x => f x + g x) :=
  hf.add' hg fun x => EReal.continuousAt_add (.inr (hg_bot x)) (.inl (hf_bot x))

lemma klScalar_lowerSemicontinuous {yi : ℝ} (hyi : 0 ≤ yi) :
    LowerSemicontinuous (klScalar yi) := by
  rw [lowerSemicontinuous_iff_isClosed_preimage]
  intro r
  induction r with
  | bot =>
    have hempty : klScalar yi ⁻¹' Set.Iic ⊥ = ∅ := by
      ext u
      simp only [Set.mem_preimage, Set.mem_Iic, Set.mem_empty_iff_false, iff_false, not_le]
      exact lt_of_lt_of_le (EReal.bot_lt_coe 0) (klScalar_nonneg hyi)
    rw [hempty]
    exact isClosed_empty
  | top =>
    have huniv : klScalar yi ⁻¹' Set.Iic ⊤ = Set.univ := by
      ext u
      simp
    rw [huniv]
    exact isClosed_univ
  | coe c =>
    rcases eq_or_lt_of_le hyi with rfl | hyi_pos
    · have heq : klScalar 0 ⁻¹' Set.Iic (c : EReal) = Set.Icc 0 c := by
        ext u
        simp only [Set.mem_preimage, Set.mem_Iic, klScalar, ↓reduceIte, Set.mem_Icc]
        by_cases hu : 0 ≤ u
        · simp [hu, EReal.coe_le_coe_iff]
        · simp [hu]
      rw [heq]
      exact isClosed_Icc
    · set u₀ : ℝ := yi * Real.exp (-(c + yi) / yi)
      have hu₀_pos : 0 < u₀ := mul_pos hyi_pos (Real.exp_pos _)
      have hset : klScalar yi ⁻¹' Set.Iic (c : EReal) =
          {u ∈ Set.Ici u₀ | yi * Real.log (yi / u) + u - yi ≤ c} := by
        ext u
        simp only [Set.mem_preimage, Set.mem_Iic, Set.mem_setOf_eq, Set.mem_Ici]
        constructor
        · intro hle
          have hu_pos : 0 < u := by
            by_contra hu_not
            dsimp only [klScalar] at hle
            rw [if_neg hyi_pos.ne', if_pos hyi_pos, if_neg hu_not] at hle
            exact not_le_of_gt (EReal.coe_lt_top c) hle
          have hreal : yi * Real.log (yi / u) + u - yi ≤ c := by
            dsimp only [klScalar] at hle
            rwa [if_neg hyi_pos.ne', if_pos hyi_pos, if_pos hu_pos, EReal.coe_le_coe_iff] at hle
          have hlog : Real.log (yi / u) ≤ (c + yi) / yi := by
            rw [le_div_iff₀ hyi_pos]
            linarith
          have hexp : yi / u ≤ Real.exp ((c + yi) / yi) := by
            rw [← Real.log_le_iff_le_exp (div_pos hyi_pos hu_pos)]
            exact hlog
          have hu_ge : u₀ ≤ u := by
            have h1 : yi ≤ Real.exp ((c + yi) / yi) * u := (div_le_iff₀ hu_pos).mp hexp
            have h2 : yi * Real.exp (-((c + yi) / yi)) ≤ u := by
              rw [Real.exp_neg, ← div_eq_mul_inv, div_le_iff₀ (Real.exp_pos _)]
              linarith
            have hneg : -((c + yi) / yi) = -(c + yi) / yi := by ring
            dsimp only [u₀]
            rwa [← hneg]
          exact ⟨hu_ge, hreal⟩
        · rintro ⟨hu_ge, hreal⟩
          have hu_pos : 0 < u := hu₀_pos.trans_le hu_ge
          dsimp only [klScalar]
          rw [if_neg hyi_pos.ne', if_pos hyi_pos, if_pos hu_pos, EReal.coe_le_coe_iff]
          exact hreal
      rw [hset]
      have hcont : ContinuousOn (fun u : ℝ => yi * Real.log (yi / u) + u - yi) (Set.Ici u₀) := by
        have hdiv : ContinuousOn (fun u : ℝ => yi / u) (Set.Ici u₀) :=
          continuousOn_const.div continuousOn_id fun u hu => (hu₀_pos.trans_le hu).ne'
        have hlog : ContinuousOn (fun u : ℝ => Real.log (yi / u)) (Set.Ici u₀) :=
          hdiv.log fun u hu => (div_pos hyi_pos (hu₀_pos.trans_le hu)).ne'
        exact ((continuousOn_const.mul hlog).add continuousOn_id).sub continuousOn_const
      exact hcont.preimage_isClosed_of_isClosed isClosed_Ici isClosed_Iic

lemma klDiv_lowerSemicontinuous (P : ProblemData m n) :
    LowerSemicontinuous (fun x : E n => klDiv P.y (Ax P x)) := by
  unfold klDiv
  have hterm : ∀ i : Fin m, LowerSemicontinuous (fun x : E n => klScalar (P.y i) (Ax P x i)) :=
    fun i => (klScalar_lowerSemicontinuous (P.hy i)).comp (Ax_coord_continuous P i)
  have hbot : ∀ (s : Finset (Fin m)) (x : E n),
      (∑ i ∈ s, klScalar (P.y i) (Ax P x i)) ≠ ⊥ := by
    intro s x
    induction s using Finset.induction with
    | empty => simp
    | @insert a t ha ih =>
      rw [Finset.sum_insert ha, ne_eq, EReal.add_eq_bot_iff]
      push_neg
      exact ⟨klScalar_ne_bot _ _, ih⟩
  have hsum_lsc : ∀ s : Finset (Fin m),
      LowerSemicontinuous (fun x : E n => ∑ i ∈ s, klScalar (P.y i) (Ax P x i)) := by
    intro s
    induction s using Finset.induction with
    | empty => simp [lowerSemicontinuous_const]
    | @insert a t ha ih =>
      simp_rw [Finset.sum_insert ha]
      exact lowerSemicontinuous_ereal_add (hterm a) ih (fun x => klScalar_ne_bot _ _) (hbot t)
  exact hsum_lsc Finset.univ

theorem Psi_isProper (P : ProblemData m n) : IsProper (Psi P) := by
  refine ⟨?_, ?_⟩
  · let aVec : E n := WithLp.toLp 2 (fun _ : Fin n => P.a)
    refine ⟨aVec, ?_⟩
    rw [effectiveDom_Psi_eq]
    refine ⟨fun _ => ⟨P.ha.le, le_rfl⟩, fun i _ => ?_⟩
    obtain ⟨j, hj⟩ := P.hA_row_pos i
    unfold Ax
    have hnn : ∀ k ∈ Finset.univ, 0 ≤ P.A i k * aVec k := fun k _ =>
      mul_nonneg (P.hA_nonneg i k) P.ha.le
    exact lt_of_lt_of_le (mul_pos hj P.ha) (Finset.single_le_sum hnn (Finset.mem_univ j))
  · intro x
    unfold Psi
    rw [ne_eq, EReal.add_eq_bot_iff, EReal.add_eq_bot_iff]
    push_neg
    refine ⟨⟨klDiv_ne_bot _ _, EReal.coe_ne_bot _⟩, ?_⟩
    by_cases hx : x ∈ boxSet n P.a <;> simp [hx]

theorem Psi_lowerSemicontinuous (P : ProblemData m n) : LowerSemicontinuous (Psi P) := by
  let Rbox : E n → EReal := fun x =>
    letI := Classical.propDecidable
    if x ∈ boxSet n P.a then (P.R_θ x : EReal) else ⊤
  have hPsi_eq : Psi P = fun x => klDiv P.y (Ax P x) + Rbox x := by
    ext x
    unfold Psi Rbox
    by_cases hx : x ∈ boxSet n P.a
    · simp [hx]
    · have h1 : klDiv P.y (Ax P x) + (P.R_θ x : EReal) ≠ ⊥ := by
        rw [ne_eq, EReal.add_eq_bot_iff]
        push_neg
        exact ⟨klDiv_ne_bot _ _, EReal.coe_ne_bot _⟩
      simp [hx, EReal.add_top_of_ne_bot h1, EReal.add_top_of_ne_bot (klDiv_ne_bot _ _)]
  have hRbox_lsc : LowerSemicontinuous Rbox := by
    rw [lowerSemicontinuous_iff_isClosed_preimage]
    intro r
    induction r with
    | bot =>
      have hempty : Rbox ⁻¹' Set.Iic ⊥ = ∅ := by
        ext x
        simp only [Set.mem_preimage, Set.mem_Iic, Set.mem_empty_iff_false, iff_false, not_le, Rbox]
        by_cases hx : x ∈ boxSet n P.a <;> simp [hx]
      rw [hempty]
      exact isClosed_empty
    | top =>
      have huniv : Rbox ⁻¹' Set.Iic ⊤ = Set.univ := by
        ext x
        simp
      rw [huniv]
      exact isClosed_univ
    | coe c =>
      have hset : Rbox ⁻¹' Set.Iic (c : EReal) = {x ∈ boxSet n P.a | P.R_θ x ≤ c} := by
        ext x
        simp only [Set.mem_preimage, Set.mem_Iic, Set.mem_setOf_eq, Rbox]
        by_cases hx : x ∈ boxSet n P.a
        · simp [hx, EReal.coe_le_coe_iff]
        · simp [hx]
      rw [hset]
      have hcont : ContinuousOn P.R_θ (boxSet n P.a) :=
        P.hR_C2.continuousOn.mono P.hBox_sub_U_R
      exact hcont.preimage_isClosed_of_isClosed (boxSet_isClosed n P.a) isClosed_Iic
  have hRbox_bot : ∀ x, Rbox x ≠ ⊥ := by
    intro x
    dsimp only [Rbox]
    by_cases hx : x ∈ boxSet n P.a <;> simp [hx]
  rw [hPsi_eq]
  exact lowerSemicontinuous_ereal_add (klDiv_lowerSemicontinuous P) hRbox_lsc
    (fun x => klDiv_ne_bot _ _) hRbox_bot

lemma R_theta_bddBelow_box (P : ProblemData m n) :
    BddBelow (P.R_θ '' boxSet n P.a) :=
  ((boxSet_isCompact n P.a).image_of_continuousOn
    (P.hR_C2.continuousOn.mono P.hBox_sub_U_R)).bddBelow

lemma R_theta_sInf_le (P : ProblemData m n) {x : E n} (hx : x ∈ boxSet n P.a) :
    sInf (P.R_θ '' boxSet n P.a) ≤ P.R_θ x :=
  csInf_le (R_theta_bddBelow_box P) ⟨x, hx, rfl⟩

theorem Psi_bddBelow (P : ProblemData m n) :
    ∃ m_low : ℝ, ∀ x : E n, (m_low : EReal) ≤ Psi P x := by
  refine ⟨sInf (P.R_θ '' boxSet n P.a), fun x => ?_⟩
  by_cases hx : x ∈ boxSet n P.a
  · unfold Psi
    rw [boxIndicator_of_mem hx, add_zero]
    have hkl : (0 : EReal) ≤ klDiv P.y (Ax P x) := klDiv_nonneg P.hy _
    have hR : ((sInf (P.R_θ '' boxSet n P.a) : ℝ) : EReal) ≤ (P.R_θ x : EReal) :=
      EReal.coe_le_coe_iff.mpr (R_theta_sInf_le P hx)
    calc
      ((sInf (P.R_θ '' boxSet n P.a) : ℝ) : EReal)
          = 0 + ((sInf (P.R_θ '' boxSet n P.a) : ℝ) : EReal) := (zero_add _).symm
      _ ≤ klDiv P.y (Ax P x) + (P.R_θ x : EReal) := add_le_add hkl hR
  · unfold Psi
    rw [boxIndicator_of_notMem hx]
    have h1 : klDiv P.y (Ax P x) + (P.R_θ x : EReal) ≠ ⊥ := by
      rw [ne_eq, EReal.add_eq_bot_iff]
      push_neg
      exact ⟨klDiv_ne_bot _ _, EReal.coe_ne_bot _⟩
    rw [EReal.add_top_of_ne_bot h1]
    exact le_top

end PsiProperties

section Lemma2

variable {m n : ℕ}

lemma K_beta_mono (P : ProblemData m n) {β₁ β₂ : ℝ} (hβ : β₁ ≤ β₂) :
    K_beta P β₁ ⊆ K_beta P β₂ := fun _ hx =>
  ⟨hx.1, hx.2.trans (EReal.coe_le_coe_iff.mpr hβ)⟩

lemma klScalar_mem_K_beta_bounds (P : ProblemData m n) {β : ℝ} {x : E n}
    (hx : x ∈ K_beta P β) (i : Fin m) :
    klScalar (P.y i) (Ax P x i) ≤ (β : EReal) ∧
      klScalar (P.y i) (Ax P x i) ≠ ⊤ ∧
      klScalar (P.y i) (Ax P x i) ≠ ⊥ ∧
      (0 < P.y i → 0 < Ax P x i) := by
  have hsum_le : klDiv P.y (Ax P x) ≤ (β : EReal) := hx.2
  have hterm_le : klScalar (P.y i) (Ax P x i) ≤ klDiv P.y (Ax P x) := by
    unfold klDiv
    rw [← Finset.add_sum_erase Finset.univ _ (Finset.mem_univ i)]
    have hrest_nn : (0 : EReal) ≤ ∑ j ∈ Finset.univ.erase i, klScalar (P.y j) (Ax P x j) := by
      have h := Finset.sum_le_sum (s := Finset.univ.erase i)
        (f := fun _ => (0 : EReal))
        (g := fun j => klScalar (P.y j) (Ax P x j))
        (fun j _ => klScalar_nonneg (P.hy j))
      simpa using h
    calc
      klScalar (P.y i) (Ax P x i) = klScalar (P.y i) (Ax P x i) + 0 := (add_zero _).symm
      _ ≤ klScalar (P.y i) (Ax P x i) +
          ∑ j ∈ Finset.univ.erase i, klScalar (P.y j) (Ax P x j) :=
        add_le_add_right hrest_nn _
  have hle_beta : klScalar (P.y i) (Ax P x i) ≤ (β : EReal) := hterm_le.trans hsum_le
  have hne_top : klScalar (P.y i) (Ax P x i) ≠ ⊤ := ne_top_of_le_ne_top (EReal.coe_ne_top β) hle_beta
  have hne_bot : klScalar (P.y i) (Ax P x i) ≠ ⊥ := klScalar_ne_bot _ _
  have hpos_imp : 0 < P.y i → 0 < Ax P x i := by
    intro hyi
    by_contra hnot
    apply hne_top
    simp [klScalar, hyi.ne', hyi, hnot]
  exact ⟨hle_beta, hne_top, hne_bot, hpos_imp⟩

/-- Lemma 2(a): `K_β` is convex. -/
theorem K_beta_convex (P : ProblemData m n) (β : ℝ) : Convex ℝ (K_beta P β) := by
  intro x₁ hx₁ x₂ hx₂ c₁ c₂ hc₁ hc₂ hsum
  refine ⟨boxSet_convex n P.a hx₁.1 hx₂.1 hc₁ hc₂ hsum, ?_⟩
  set z : E n := c₁ • x₁ + c₂ • x₂
  have hz_box : z ∈ boxSet n P.a := boxSet_convex n P.a hx₁.1 hx₂.1 hc₁ hc₂ hsum
  have hAx_lin : ∀ i : Fin m, Ax P z i = c₁ * Ax P x₁ i + c₂ * Ax P x₂ i := by
    intro i
    unfold Ax
    simp only [z, PiLp.add_apply, PiLp.smul_apply, smul_eq_mul, mul_add, Finset.sum_add_distrib]
    congr 1 <;> rw [Finset.mul_sum] <;> refine Finset.sum_congr rfl fun j _ => by ring
  have hterm_le : ∀ i : Fin m,
      klScalar (P.y i) (Ax P z i) ≤
        ((c₁ * (klScalar (P.y i) (Ax P x₁ i)).toReal +
          c₂ * (klScalar (P.y i) (Ax P x₂ i)).toReal : ℝ) : EReal) := by
    intro i
    have h1 := klScalar_mem_K_beta_bounds P hx₁ i
    have h2 := klScalar_mem_K_beta_bounds P hx₂ i
    rcases eq_or_lt_of_le (P.hy i) with hy0 | hy_pos
    · have hAx1 : 0 ≤ Ax P x₁ i := Ax_nonneg_of_mem_box P hx₁.1 i
      have hAx2 : 0 ≤ Ax P x₂ i := Ax_nonneg_of_mem_box P hx₂.1 i
      have hAxz : 0 ≤ Ax P z i := Ax_nonneg_of_mem_box P hz_box i
      have hy0' : P.y i = 0 := hy0.symm
      have hk1 : (klScalar (P.y i) (Ax P x₁ i)).toReal = Ax P x₁ i := by
        dsimp only [klScalar]
        rw [if_pos hy0', if_pos hAx1, EReal.toReal_coe]
      have hk2 : (klScalar (P.y i) (Ax P x₂ i)).toReal = Ax P x₂ i := by
        dsimp only [klScalar]
        rw [if_pos hy0', if_pos hAx2, EReal.toReal_coe]
      rw [klScalar, if_pos hy0', if_pos hAxz, EReal.coe_le_coe_iff, hk1, hk2, hAx_lin i]
    · have hAx1 : 0 < Ax P x₁ i := h1.2.2.2 hy_pos
      have hAx2 : 0 < Ax P x₂ i := h2.2.2.2 hy_pos
      have hAxz : 0 < Ax P z i := by
        rw [hAx_lin i]
        rcases eq_or_lt_of_le hc₁ with rfl | hc₁_pos
        · have hc₂_one : c₂ = 1 := by linarith
          simpa [hc₂_one] using hAx2
        · have h_term1 : 0 < c₁ * Ax P x₁ i := mul_pos hc₁_pos hAx1
          have h_term2 : 0 ≤ c₂ * Ax P x₂ i := mul_nonneg hc₂ hAx2.le
          linarith
      have h_log_conc : c₁ * Real.log (Ax P x₁ i) + c₂ * Real.log (Ax P x₂ i) ≤
          Real.log (Ax P z i) := by
        rw [hAx_lin i]
        rcases eq_or_ne (Ax P x₁ i) (Ax P x₂ i) with heq | hne
        · rw [heq]
          have hlin : c₁ * (Ax P x₂ i) + c₂ * (Ax P x₂ i) = Ax P x₂ i := by
            calc
              c₁ * Ax P x₂ i + c₂ * Ax P x₂ i = (c₁ + c₂) * Ax P x₂ i := by ring
              _ = Ax P x₂ i := by rw [hsum, one_mul]
          have hlin2 : c₁ * Real.log (Ax P x₂ i) + c₂ * Real.log (Ax P x₂ i) =
              Real.log (Ax P x₂ i) := by
            calc
              c₁ * Real.log (Ax P x₂ i) + c₂ * Real.log (Ax P x₂ i)
                  = (c₁ + c₂) * Real.log (Ax P x₂ i) := by ring
              _ = Real.log (Ax P x₂ i) := by rw [hsum, one_mul]
          rw [hlin, hlin2]
        · rcases eq_or_lt_of_le hc₁ with rfl | hc₁_pos
          · have hc₂_one : c₂ = 1 := by linarith
            subst hc₂_one
            simp
          · rcases eq_or_lt_of_le hc₂ with rfl | hc₂_pos
            · have hc₁_one : c₁ = 1 := by linarith
              subst hc₁_one
              simp
            · exact (strictConcaveOn_log_Ioi.2 hAx1 hAx2 hne hc₁_pos hc₂_pos hsum).le
      have h_kl1 : (klScalar (P.y i) (Ax P x₁ i)).toReal =
          P.y i * Real.log (P.y i) - P.y i * Real.log (Ax P x₁ i) + Ax P x₁ i - P.y i := by
        dsimp only [klScalar]
        rw [if_neg hy_pos.ne', if_pos hy_pos, if_pos hAx1, EReal.toReal_coe,
          Real.log_div hy_pos.ne' hAx1.ne']
        ring
      have h_kl2 : (klScalar (P.y i) (Ax P x₂ i)).toReal =
          P.y i * Real.log (P.y i) - P.y i * Real.log (Ax P x₂ i) + Ax P x₂ i - P.y i := by
        dsimp only [klScalar]
        rw [if_neg hy_pos.ne', if_pos hy_pos, if_pos hAx2, EReal.toReal_coe,
          Real.log_div hy_pos.ne' hAx2.ne']
        ring
      have h_klz : klScalar (P.y i) (Ax P z i) =
          ((P.y i * Real.log (P.y i) - P.y i * Real.log (Ax P z i) + Ax P z i - P.y i : ℝ) : EReal) := by
        dsimp only [klScalar]
        rw [if_neg hy_pos.ne', if_pos hy_pos, if_pos hAxz]
        congr 1
        rw [Real.log_div hy_pos.ne' hAxz.ne']
        ring
      rw [h_klz, EReal.coe_le_coe_iff, h_kl1, h_kl2]
      have h_mul_log : -(P.y i * Real.log (Ax P z i)) ≤
          -(P.y i * (c₁ * Real.log (Ax P x₁ i) + c₂ * Real.log (Ax P x₂ i))) :=
        neg_le_neg (mul_le_mul_of_nonneg_left h_log_conc hy_pos.le)
      have h_comb : c₁ * (P.y i * Real.log (P.y i) - P.y i) +
          c₂ * (P.y i * Real.log (P.y i) - P.y i) =
          P.y i * Real.log (P.y i) - P.y i := by
        calc
          c₁ * (P.y i * Real.log (P.y i) - P.y i) + c₂ * (P.y i * Real.log (P.y i) - P.y i)
              = (c₁ + c₂) * (P.y i * Real.log (P.y i) - P.y i) := by ring
          _ = P.y i * Real.log (P.y i) - P.y i := by rw [hsum, one_mul]
      rw [hAx_lin i] at h_mul_log
      rw [hAx_lin i]
      calc
        P.y i * Real.log (P.y i) - P.y i * Real.log (c₁ * Ax P x₁ i + c₂ * Ax P x₂ i) +
            (c₁ * Ax P x₁ i + c₂ * Ax P x₂ i) - P.y i
            ≤ (c₁ * (P.y i * Real.log (P.y i) - P.y i) + c₂ * (P.y i * Real.log (P.y i) - P.y i)) -
                P.y i * (c₁ * Real.log (Ax P x₁ i) + c₂ * Real.log (Ax P x₂ i)) +
                (c₁ * Ax P x₁ i + c₂ * Ax P x₂ i) := by
              rw [h_comb]
              linarith
        _ = c₁ * (P.y i * Real.log (P.y i) - P.y i * Real.log (Ax P x₁ i) + Ax P x₁ i - P.y i) +
              c₂ * (P.y i * Real.log (P.y i) - P.y i * Real.log (Ax P x₂ i) + Ax P x₂ i - P.y i) := by
          ring
  have hsum_ineq : klDiv P.y (Ax P z) ≤
      ((c₁ * (klDiv P.y (Ax P x₁)).toReal + c₂ * (klDiv P.y (Ax P x₂)).toReal : ℝ) : EReal) := by
    have h1_eq : (klDiv P.y (Ax P x₁)).toReal = ∑ i : Fin m, (klScalar (P.y i) (Ax P x₁ i)).toReal := by
      unfold klDiv
      have hcoe : ((∑ i : Fin m, (klScalar (P.y i) (Ax P x₁ i)).toReal : ℝ) : EReal) =
          ∑ i : Fin m, klScalar (P.y i) (Ax P x₁ i) := by
        rw [ereal_coe_finset_sum]
        refine Finset.sum_congr rfl fun i _ => ?_
        have hb := klScalar_mem_K_beta_bounds P hx₁ i
        exact EReal.coe_toReal hb.2.1 hb.2.2.1
      rw [← hcoe, EReal.toReal_coe]
    have h2_eq : (klDiv P.y (Ax P x₂)).toReal = ∑ i : Fin m, (klScalar (P.y i) (Ax P x₂ i)).toReal := by
      unfold klDiv
      have hcoe : ((∑ i : Fin m, (klScalar (P.y i) (Ax P x₂ i)).toReal : ℝ) : EReal) =
          ∑ i : Fin m, klScalar (P.y i) (Ax P x₂ i) := by
        rw [ereal_coe_finset_sum]
        refine Finset.sum_congr rfl fun i _ => ?_
        have hb := klScalar_mem_K_beta_bounds P hx₂ i
        exact EReal.coe_toReal hb.2.1 hb.2.2.1
      rw [← hcoe, EReal.toReal_coe]
    rw [h1_eq, h2_eq, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib,
      ereal_coe_finset_sum]
    exact Finset.sum_le_sum fun i _ => hterm_le i
  have h_le1 : (klDiv P.y (Ax P x₁)).toReal ≤ β := by
    have hne_top : klDiv P.y (Ax P x₁) ≠ ⊤ := ne_top_of_le_ne_top (EReal.coe_ne_top β) hx₁.2
    have hcoe := EReal.coe_toReal hne_top (klDiv_ne_bot _ _)
    have hle := hx₁.2
    rwa [← hcoe, EReal.coe_le_coe_iff] at hle
  have h_le2 : (klDiv P.y (Ax P x₂)).toReal ≤ β := by
    have hne_top : klDiv P.y (Ax P x₂) ≠ ⊤ := ne_top_of_le_ne_top (EReal.coe_ne_top β) hx₂.2
    have hcoe := EReal.coe_toReal hne_top (klDiv_ne_bot _ _)
    have hle := hx₂.2
    rwa [← hcoe, EReal.coe_le_coe_iff] at hle
  have h_comb_beta : c₁ * (klDiv P.y (Ax P x₁)).toReal + c₂ * (klDiv P.y (Ax P x₂)).toReal ≤ β := by
    calc
      c₁ * (klDiv P.y (Ax P x₁)).toReal + c₂ * (klDiv P.y (Ax P x₂)).toReal
          ≤ c₁ * β + c₂ * β :=
        add_le_add (mul_le_mul_of_nonneg_left h_le1 hc₁) (mul_le_mul_of_nonneg_left h_le2 hc₂)
      _ = (c₁ + c₂) * β := by ring
      _ = β := by rw [hsum, one_mul]
  exact hsum_ineq.trans (EReal.coe_le_coe_iff.mpr h_comb_beta)

/-- `K_β` is closed. -/
theorem K_beta_isClosed (P : ProblemData m n) (β : ℝ) : IsClosed (K_beta P β) := by
  have heq : K_beta P β = boxSet n P.a ∩ (fun x => klDiv P.y (Ax P x)) ⁻¹' Set.Iic (β : EReal) :=
    rfl
  rw [heq]
  exact (boxSet_isClosed n P.a).inter ((klDiv_lowerSemicontinuous P).isClosed_preimage (β : EReal))

/-- Lemma 2(b): `K_β` is compact. -/
theorem K_beta_isCompact (P : ProblemData m n) (β : ℝ) : IsCompact (K_beta P β) :=
  (boxSet_isCompact n P.a).of_isClosed_subset (K_beta_isClosed P β) (fun _ hx => hx.1)

/-- Lemma 2(c): Uniform positive lower bound `(Ax)_i ≥ c_β > 0` on `K_β` for every `i` with `y_i > 0`. -/
theorem K_beta_ax_lower_bound (P : ProblemData m n) (β : ℝ) :
    ∃ c > (0 : ℝ), ∀ x ∈ K_beta P β, ∀ i : Fin m, 0 < P.y i → c ≤ Ax P x i := by
  classical
  let posY : Finset (Fin m) := Finset.univ.filter fun i => 0 < P.y i
  by_cases hne : posY.Nonempty
  · set c : ℝ := posY.inf' hne fun i => P.y i * Real.exp (-(β + P.y i) / P.y i)
    have hc_pos : 0 < c := (Finset.lt_inf'_iff hne).mpr fun i hi => by
      have hyi : 0 < P.y i := (Finset.mem_filter.mp hi).2
      exact mul_pos hyi (Real.exp_pos _)
    refine ⟨c, hc_pos, fun x hx i hyi => ?_⟩
    have hi_mem : i ∈ posY := Finset.mem_filter.mpr ⟨Finset.mem_univ i, hyi⟩
    have hbounds := klScalar_mem_K_beta_bounds P hx i
    have hAx_pos : 0 < Ax P x i := hbounds.2.2.2 hyi
    have hkl_le : P.y i * Real.log (P.y i / Ax P x i) + Ax P x i - P.y i ≤ β := by
      have h := hbounds.1
      dsimp only [klScalar] at h
      rwa [if_neg hyi.ne', if_pos hyi, if_pos hAx_pos, EReal.coe_le_coe_iff] at h
    have hlog_le : Real.log (P.y i / Ax P x i) ≤ (β + P.y i) / P.y i := by
      rw [le_div_iff₀ hyi]
      linarith
    have hexp_le : P.y i / Ax P x i ≤ Real.exp ((β + P.y i) / P.y i) :=
      (Real.log_le_iff_le_exp (div_pos hyi hAx_pos)).mp hlog_le
    have hAx_ge_i : P.y i * Real.exp (-(β + P.y i) / P.y i) ≤ Ax P x i := by
      have h1 : P.y i ≤ Real.exp ((β + P.y i) / P.y i) * Ax P x i :=
        (div_le_iff₀ hAx_pos).mp hexp_le
      have h2 : P.y i * Real.exp (-((β + P.y i) / P.y i)) ≤ Ax P x i := by
        rw [Real.exp_neg, ← div_eq_mul_inv, div_le_iff₀ (Real.exp_pos _)]
        linarith
      have hneg : -((β + P.y i) / P.y i) = -(β + P.y i) / P.y i := by ring
      rwa [← hneg]
    exact (Finset.inf'_le (fun j => P.y j * Real.exp (-(β + P.y j) / P.y j)) hi_mem).trans hAx_ge_i
  · refine ⟨1, one_pos, fun _ _ i hyi => ?_⟩
    exfalso
    exact hne ⟨i, Finset.mem_filter.mpr ⟨Finset.mem_univ i, hyi⟩⟩

lemma K_beta_subset_UPos (P : ProblemData m n) (β : ℝ) :
    K_beta P β ⊆ UPos P := by
  obtain ⟨c, hc_pos, hc_le⟩ := K_beta_ax_lower_bound P β
  intro x hx i hyi
  exact hc_pos.trans_le (hc_le x hx i hyi)

lemma K_beta_subset_open (P : ProblemData m n) (β : ℝ) :
    K_beta P β ⊆ UPos P ∩ P.U_R := fun _ hx =>
  ⟨K_beta_subset_UPos P β hx, P.hBox_sub_U_R hx.1⟩

/-- Lemma 2(d): `K_β ∩ S = ∅`. -/
theorem K_beta_disjoint_singularSet (P : ProblemData m n) (β : ℝ) :
    Disjoint (K_beta P β) (singularSet P) := by
  rw [Set.disjoint_left]
  rintro x hxK ⟨_, i, hyi, hax0⟩
  have hpos := K_beta_subset_UPos P β hxK i hyi
  linarith

lemma L0_subset_K_beta0 (P : ProblemData m n) {x0 : E n}
    (_hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤) :
    L0 P x0 ⊆ K_beta P (beta0 P x0) := by
  intro x hxL
  refine ⟨hxL.1, ?_⟩
  have hPsi_x_le : Psi P x ≤ Psi P x0 := hxL.2
  have hPsi_x_ne_top : Psi P x ≠ ⊤ := ne_top_of_le_ne_top hx0_fin hPsi_x_le
  have hx_dom : x ∈ effectiveDom (Psi P) := ⟨hPsi_x_ne_top, (Psi_isProper P).2 x⟩
  have htoReal_le : (Psi P x).toReal ≤ (Psi P x0).toReal :=
    EReal.toReal_le_toReal hPsi_x_le hx_dom.2 hx0_fin
  have hx_box_pos : x ∈ boxSet n P.a ∩ UPos P := by rwa [← effectiveDom_Psi_eq P]
  have hPsi_x_eq : (Psi P x).toReal = FSmooth P x := by
    rw [Psi_eq_FSmooth_on_box_inter_UPos P hx_box_pos.1 hx_box_pos.2, EReal.toReal_coe]
  have hkl_eq : klDiv P.y (Ax P x) =
      ((∑ i : Fin m, klSmoothScalar (P.y i) (Ax P x i) : ℝ) : EReal) :=
    klDiv_eq_sum_klSmoothScalar_on_box_inter_UPos P hx_box_pos.1 hx_box_pos.2
  have hkl_le : (∑ i : Fin m, klSmoothScalar (P.y i) (Ax P x i)) ≤ beta0 P x0 := by
    have hR_le := R_theta_sInf_le P hxL.1
    dsimp [beta0]
    have hF_def : FSmooth P x = (∑ i : Fin m, klSmoothScalar (P.y i) (Ax P x i)) + P.R_θ x := rfl
    linarith
  rw [hkl_eq, EReal.coe_le_coe_iff]
  exact hkl_le

lemma fderiv_gradient_FSmooth_continuousOn (P : ProblemData m n) :
    ContinuousOn (fderiv ℝ (gradient (FSmooth P))) (UPos P ∩ P.U_R) := by
  have hU_open : IsOpen (UPos P ∩ P.U_R) := (isOpen_UPos P).inter P.hU_R_open
  have hF_C2 : ContDiffOn ℝ 2 (FSmooth P) (UPos P ∩ P.U_R) := FSmooth_contDiffOn_open P
  have hfd_C1 : ContDiffOn ℝ 1 (fderiv ℝ (FSmooth P)) (UPos P ∩ P.U_R) :=
    hF_C2.fderiv_of_isOpen hU_open (by norm_num)
  have hgrad_C1 : ContDiffOn ℝ 1 (gradient (FSmooth P)) (UPos P ∩ P.U_R) := by
    have hcomp : ContDiffOn ℝ 1
        (fun x => (InnerProductSpace.toDual ℝ (E n)).symm (fderiv ℝ (FSmooth P) x))
        (UPos P ∩ P.U_R) :=
      ((InnerProductSpace.toDual ℝ (E n)).symm.toContinuousLinearEquiv.toContinuousLinearMap.contDiff.contDiffOn).comp
        hfd_C1 (fun _ _ => Set.mem_univ _)
    refine hcomp.congr fun x hx => ?_
    have hdiff : DifferentiableAt ℝ (FSmooth P) x :=
      ((hF_C2.of_le (by norm_num)).differentiableOn one_ne_zero x hx).differentiableAt
        (hU_open.mem_nhds hx)
    have hfd : fderiv ℝ (FSmooth P) x = (InnerProductSpace.toDual ℝ (E n)) (gradient (FSmooth P) x) :=
      (hasGradientAt_iff_hasFDerivAt.mp hdiff.hasGradientAt).fderiv
    rw [hfd, LinearIsometryEquiv.symm_apply_apply]
  exact hgrad_C1.continuousOn_fderiv_of_isOpen hU_open le_rfl

/-- Constant `M_β ≥ 1` bounding `‖∇²F(x)‖` on `K_β`. -/
noncomputable def M_beta (P : ProblemData m n) (β : ℝ) : ℝ :=
  max 1 (sSup ((fun x => ‖fderiv ℝ (gradient (FSmooth P)) x‖) '' K_beta P β))

lemma M_beta_pos (P : ProblemData m n) (β : ℝ) : 0 < M_beta P β :=
  lt_of_lt_of_le one_pos (le_max_left _ _)

lemma norm_fderiv_gradient_le_M_beta (P : ProblemData m n) (β : ℝ) {x : E n}
    (hx : x ∈ K_beta P β) :
    ‖fderiv ℝ (gradient (FSmooth P)) x‖ ≤ M_beta P β := by
  have hcont : ContinuousOn (fun z => ‖fderiv ℝ (gradient (FSmooth P)) z‖) (K_beta P β) :=
    (fderiv_gradient_FSmooth_continuousOn P).norm.mono (K_beta_subset_open P β)
  have hbdd : BddAbove ((fun z => ‖fderiv ℝ (gradient (FSmooth P)) z‖) '' K_beta P β) :=
    ((K_beta_isCompact P β).image_of_continuousOn hcont).bddAbove
  exact (le_csSup hbdd ⟨x, hx, rfl⟩).trans (le_max_right _ _)

/-- Lemma 2(e): `∇F` is `M_β`-Lipschitz continuous on `K_β`. -/
theorem grad_FSmooth_lipschitzOn_K_beta (P : ProblemData m n) (β : ℝ) :
    LipschitzOnWith (M_beta P β).toNNReal (gradient (FSmooth P)) (K_beta P β) := by
  have hU_open : IsOpen (UPos P ∩ P.U_R) := (isOpen_UPos P).inter P.hU_R_open
  have hgrad_C1 : ContDiffOn ℝ 1 (gradient (FSmooth P)) (UPos P ∩ P.U_R) := by
    have hF_C2 : ContDiffOn ℝ 2 (FSmooth P) (UPos P ∩ P.U_R) := FSmooth_contDiffOn_open P
    have hfd_C1 : ContDiffOn ℝ 1 (fderiv ℝ (FSmooth P)) (UPos P ∩ P.U_R) :=
      hF_C2.fderiv_of_isOpen hU_open (by norm_num)
    have hcomp : ContDiffOn ℝ 1
        (fun x => (InnerProductSpace.toDual ℝ (E n)).symm (fderiv ℝ (FSmooth P) x))
        (UPos P ∩ P.U_R) :=
      ((InnerProductSpace.toDual ℝ (E n)).symm.toContinuousLinearEquiv.toContinuousLinearMap.contDiff.contDiffOn).comp
        hfd_C1 (fun _ _ => Set.mem_univ _)
    refine hcomp.congr fun x hx => ?_
    have hdiff : DifferentiableAt ℝ (FSmooth P) x :=
      ((hF_C2.of_le (by norm_num)).differentiableOn one_ne_zero x hx).differentiableAt
        (hU_open.mem_nhds hx)
    have hfd : fderiv ℝ (FSmooth P) x = (InnerProductSpace.toDual ℝ (E n)) (gradient (FSmooth P) x) :=
      (hasGradientAt_iff_hasFDerivAt.mp hdiff.hasGradientAt).fderiv
    rw [hfd, LinearIsometryEquiv.symm_apply_apply]
  refine (K_beta_convex P β).lipschitzOnWith_of_nnnorm_fderiv_le (𝕜 := ℝ) ?_ ?_
  · intro x hx
    exact (hgrad_C1.differentiableOn one_ne_zero x (K_beta_subset_open P β hx)).differentiableAt
      (hU_open.mem_nhds (K_beta_subset_open P β hx))
  · intro x hx
    rw [← NNReal.coe_le_coe, coe_nnnorm, Real.coe_toNNReal _ (M_beta_pos P β).le]
    exact norm_fderiv_gradient_le_M_beta P β hx

lemma grad_FSmooth_norm_sub_le (P : ProblemData m n) (β : ℝ) {u x : E n}
    (hu : u ∈ K_beta P β) (hx : x ∈ K_beta P β) :
    ‖gradient (FSmooth P) u - gradient (FSmooth P) x‖ ≤ M_beta P β * ‖u - x‖ := by
  have h := (grad_FSmooth_lipschitzOn_K_beta P β).dist_le_mul u hu x hx
  rw [dist_eq_norm, dist_eq_norm, Real.coe_toNNReal _ (M_beta_pos P β).le] at h
  exact h

/-- Smoothness constant `L_β := M_β (a + ξ)² > 0` from Lemma 2. -/
noncomputable def L_beta (P : ProblemData m n) (β : ℝ) : ℝ :=
  M_beta P β * (P.a + P.ξ) ^ 2

lemma L_beta_pos (P : ProblemData m n) (β : ℝ) : 0 < L_beta P β := by
  have haξ : 0 < P.a + P.ξ := by linarith [P.ha, P.hξ]
  exact mul_pos (M_beta_pos P β) (sq_pos_of_pos haξ)

private lemma hasDerivAt_segment_shiftedBurg_sub_FSmooth (P : ProblemData m n) (β : ℝ)
    {x u : E n} (hx : x ∈ K_beta P β) (hu : u ∈ K_beta P β) :
    let d : E n := u - x
    let z : ℝ → E n := fun t => (1 - t) • x + t • u
    let Φ : E n → ℝ := fun w => L_beta P β * shiftedBurgReal P.ξ w - FSmooth P w
    ∀ t ∈ Set.Icc (0 : ℝ) 1,
      HasDerivAt (fun s => Φ (z s))
        (⟪L_beta P β • shiftedBurgGrad P.ξ (z t) - gradient (FSmooth P) (z t), d⟫_ℝ) t := by
  intro d z Φ t ht
  have hz_K : z t ∈ K_beta P β :=
    K_beta_convex P β hx hu (by linarith [ht.1, ht.2]) ht.1 (by ring)
  have hz_box : z t ∈ boxSet n P.a := hz_K.1
  have hz_open : z t ∈ UPos P ∩ P.U_R := K_beta_subset_open P β hz_K
  have hU_open : IsOpen (UPos P ∩ P.U_R) := (isOpen_UPos P).inter P.hU_R_open
  have hz_deriv : HasDerivAt z d t := by
    have h1 : HasDerivAt (fun s : ℝ => (1 - s) • x) ((-1 : ℝ) • x) t := by
      simpa using ((hasDerivAt_const t (1 : ℝ)).fun_sub (hasDerivAt_id' t)).smul_const x
    have h2 : HasDerivAt (fun s : ℝ => s • u) ((1 : ℝ) • u) t :=
      (hasDerivAt_id' t).smul_const u
    have hadd := h1.fun_add h2
    convert hadd using 1
    simp [d, sub_eq_add_neg, add_comm]
  have hBurg_fderiv : HasFDerivAt (shiftedBurgReal P.ξ)
      ((InnerProductSpace.toDual ℝ (E n)) (shiftedBurgGrad P.ξ (z t))) (z t) := by
    have hcoord : ∀ j : Fin n, HasFDerivAt (fun w : E n => Real.log (w j + P.ξ))
        (((z t j + P.ξ)⁻¹) •
          ((ContinuousLinearMap.proj (R := ℝ) (ι := Fin n) (φ := fun _ => ℝ) j).comp
            (PiLp.continuousLinearEquiv 2 ℝ (fun _ : Fin n => ℝ)).toContinuousLinearMap)) (z t) := by
      intro j
      have hproj : HasFDerivAt (fun w : E n => w j)
          ((ContinuousLinearMap.proj (R := ℝ) (ι := Fin n) (φ := fun _ => ℝ) j).comp
            (PiLp.continuousLinearEquiv 2 ℝ (fun _ : Fin n => ℝ)).toContinuousLinearMap) (z t) :=
        ((ContinuousLinearMap.proj (R := ℝ) (ι := Fin n) (φ := fun _ => ℝ) j).comp
          (PiLp.continuousLinearEquiv 2 ℝ (fun _ : Fin n => ℝ)).toContinuousLinearMap).hasFDerivAt
      have hadd_c : HasFDerivAt (fun w : E n => w j + P.ξ) _ (z t) := hproj.add_const P.ξ
      have hpos : z t j + P.ξ ≠ 0 := by linarith [(hz_box j).1, P.hξ]
      exact hadd_c.log hpos
    have hsum : HasFDerivAt (shiftedBurgReal P.ξ)
        (- ∑ j : Fin n, ((z t j + P.ξ)⁻¹) •
          ((ContinuousLinearMap.proj (R := ℝ) (ι := Fin n) (φ := fun _ => ℝ) j).comp
            (PiLp.continuousLinearEquiv 2 ℝ (fun _ : Fin n => ℝ)).toContinuousLinearMap)) (z t) := by
      unfold shiftedBurgReal
      exact (HasFDerivAt.fun_sum fun j _ => hcoord j).neg
    convert hsum using 1
    ext v
    simp only [InnerProductSpace.toDual_apply_apply, ContinuousLinearMap.neg_apply,
      ContinuousLinearMap.sum_apply, ContinuousLinearMap.smul_apply, ContinuousLinearMap.comp_apply,
      ContinuousLinearMap.proj_apply, smul_eq_mul, E_inner_eq, shiftedBurgGrad, neg_mul]
    rw [← Finset.sum_neg_distrib]
    refine Finset.sum_congr rfl fun j _ => ?_
    change -((z t j + P.ξ)⁻¹ * v j) = -((z t j + P.ξ)⁻¹ * v j)
    rfl
  have hF_fderiv : HasFDerivAt (FSmooth P)
      ((InnerProductSpace.toDual ℝ (E n)) (gradient (FSmooth P) (z t))) (z t) := by
    have hdiff : DifferentiableAt ℝ (FSmooth P) (z t) :=
      (((FSmooth_contDiffOn_open P).of_le (by norm_num)).differentiableOn one_ne_zero _ hz_open).differentiableAt
        (hU_open.mem_nhds hz_open)
    exact hasGradientAt_iff_hasFDerivAt.mp hdiff.hasGradientAt
  have hΦ_fderiv : HasFDerivAt Φ
      ((InnerProductSpace.toDual ℝ (E n))
        (L_beta P β • shiftedBurgGrad P.ξ (z t) - gradient (FSmooth P) (z t))) (z t) := by
    have h1 := (hBurg_fderiv.const_smul (L_beta P β)).sub hF_fderiv
    convert h1 using 1
    ext v
    simp [InnerProductSpace.toDual_apply_apply]
  have hcomp := hΦ_fderiv.comp_hasDerivAt t hz_deriv
  dsimp only [Function.comp_def] at hcomp
  convert hcomp using 1

private lemma deriv_segment_monotoneOn (P : ProblemData m n) (β : ℝ)
    {x u : E n} (hx : x ∈ K_beta P β) (hu : u ∈ K_beta P β) :
    let d : E n := u - x
    let z : ℝ → E n := fun t => (1 - t) • x + t • u
    let φ' : ℝ → ℝ := fun t =>
      ⟪L_beta P β • shiftedBurgGrad P.ξ (z t) - gradient (FSmooth P) (z t), d⟫_ℝ
    MonotoneOn φ' (Set.Icc (0 : ℝ) 1) := by
  intro d z φ' t₁ ht₁ t₂ ht₂ h12
  have hz₁ : z t₁ ∈ K_beta P β := K_beta_convex P β hx hu (by linarith [ht₁.1, ht₁.2]) ht₁.1 (by ring)
  have hz₂ : z t₂ ∈ K_beta P β := K_beta_convex P β hx hu (by linarith [ht₂.1, ht₂.2]) ht₂.1 (by ring)
  have hz_diff : z t₂ - z t₁ = (t₂ - t₁) • d := by
    dsimp [z, d]
    ext j
    simp
    ring
  have hburg_lower : (t₂ - t₁) / (P.a + P.ξ) ^ 2 * ‖d‖ ^ 2 ≤
      ⟪shiftedBurgGrad P.ξ (z t₂) - shiftedBurgGrad P.ξ (z t₁), d⟫_ℝ := by
    rw [E_inner_eq, E_norm_sq_eq, Finset.mul_sum]
    refine Finset.sum_le_sum fun j _ => ?_
    have hz₁j := hz₁.1 j
    have hz₂j := hz₂.1 j
    have h1ξ_pos : 0 < z t₁ j + P.ξ := by linarith [hz₁j.1, P.hξ]
    have h2ξ_pos : 0 < z t₂ j + P.ξ := by linarith [hz₂j.1, P.hξ]
    have hcoord_diff : z t₂ j - z t₁ j = (t₂ - t₁) * d j := by
      have h := congrArg (fun v : E n => v j) hz_diff
      simpa using h
    have hid : ((shiftedBurgGrad P.ξ (z t₂) - shiftedBurgGrad P.ξ (z t₁)) j) * d j =
        (t₂ - t₁) * (d j) ^ 2 / ((z t₁ j + P.ξ) * (z t₂ j + P.ξ)) := by
      simp only [PiLp.sub_apply, shiftedBurgGrad]
      have hne1 : z t₁ j + P.ξ ≠ 0 := h1ξ_pos.ne'
      have hne2 : z t₂ j + P.ξ ≠ 0 := h2ξ_pos.ne'
      calc
        (-(z t₂ j + P.ξ)⁻¹ - -(z t₁ j + P.ξ)⁻¹) * d j
            = ((z t₂ j - z t₁ j) / ((z t₁ j + P.ξ) * (z t₂ j + P.ξ))) * d j := by
          field_simp; ring
        _ = (t₂ - t₁) * (d j) ^ 2 / ((z t₁ j + P.ξ) * (z t₂ j + P.ξ)) := by
          rw [hcoord_diff]; ring
    rw [hid]
    have hprod_le : (z t₁ j + P.ξ) * (z t₂ j + P.ξ) ≤ (P.a + P.ξ) ^ 2 := by
      have h1 : z t₁ j + P.ξ ≤ P.a + P.ξ := by linarith [hz₁j.2]
      have h2 : z t₂ j + P.ξ ≤ P.a + P.ξ := by linarith [hz₂j.2]
      nlinarith
    have hinv_ge : 1 / (P.a + P.ξ) ^ 2 ≤ 1 / ((z t₁ j + P.ξ) * (z t₂ j + P.ξ)) :=
      one_div_le_one_div_of_le (mul_pos h1ξ_pos h2ξ_pos) hprod_le
    have hnum_nn : 0 ≤ (t₂ - t₁) * (d j) ^ 2 := mul_nonneg (sub_nonneg.mpr h12) (sq_nonneg _)
    calc
      (t₂ - t₁) / (P.a + P.ξ) ^ 2 * (d j) ^ 2
          = (1 / (P.a + P.ξ) ^ 2) * ((t₂ - t₁) * (d j) ^ 2) := by ring
      _ ≤ (1 / ((z t₁ j + P.ξ) * (z t₂ j + P.ξ))) * ((t₂ - t₁) * (d j) ^ 2) :=
        mul_le_mul_of_nonneg_right hinv_ge hnum_nn
      _ = (t₂ - t₁) * (d j) ^ 2 / ((z t₁ j + P.ξ) * (z t₂ j + P.ξ)) := by ring
  have hF_upper : ⟪gradient (FSmooth P) (z t₂) - gradient (FSmooth P) (z t₁), d⟫_ℝ ≤
      M_beta P β * (t₂ - t₁) * ‖d‖ ^ 2 := by
    have hcs := real_inner_le_norm (gradient (FSmooth P) (z t₂) - gradient (FSmooth P) (z t₁)) d
    have hlip := grad_FSmooth_norm_sub_le P β hz₂ hz₁
    have hznorm : ‖z t₂ - z t₁‖ = (t₂ - t₁) * ‖d‖ := by
      rw [hz_diff, norm_smul, Real.norm_of_nonneg (sub_nonneg.mpr h12)]
    rw [hznorm] at hlip
    calc
      ⟪gradient (FSmooth P) (z t₂) - gradient (FSmooth P) (z t₁), d⟫_ℝ
          ≤ ‖gradient (FSmooth P) (z t₂) - gradient (FSmooth P) (z t₁)‖ * ‖d‖ := hcs
      _ ≤ (M_beta P β * ((t₂ - t₁) * ‖d‖)) * ‖d‖ :=
        mul_le_mul_of_nonneg_right hlip (norm_nonneg d)
      _ = M_beta P β * (t₂ - t₁) * ‖d‖ ^ 2 := by ring
  have hdiff_eq : φ' t₂ - φ' t₁ =
      L_beta P β * ⟪shiftedBurgGrad P.ξ (z t₂) - shiftedBurgGrad P.ξ (z t₁), d⟫_ℝ -
        ⟪gradient (FSmooth P) (z t₂) - gradient (FSmooth P) (z t₁), d⟫_ℝ := by
    dsimp [φ']
    rw [← inner_sub_left]
    have hvec : (L_beta P β • shiftedBurgGrad P.ξ (z t₂) - gradient (FSmooth P) (z t₂)) -
        (L_beta P β • shiftedBurgGrad P.ξ (z t₁) - gradient (FSmooth P) (z t₁)) =
        L_beta P β • (shiftedBurgGrad P.ξ (z t₂) - shiftedBurgGrad P.ξ (z t₁)) -
          (gradient (FSmooth P) (z t₂) - gradient (FSmooth P) (z t₁)) := by
      simp only [smul_sub]
      abel
    rw [hvec, inner_sub_left, inner_smul_left]
    simp
  have hcomb : 0 ≤ L_beta P β * ((t₂ - t₁) / (P.a + P.ξ) ^ 2 * ‖d‖ ^ 2) -
      M_beta P β * (t₂ - t₁) * ‖d‖ ^ 2 := by
    have haξ_ne : P.a + P.ξ ≠ 0 := by linarith [P.ha, P.hξ]
    dsimp [L_beta]
    have heq : M_beta P β * (P.a + P.ξ) ^ 2 * ((t₂ - t₁) / (P.a + P.ξ) ^ 2 * ‖d‖ ^ 2) -
        M_beta P β * (t₂ - t₁) * ‖d‖ ^ 2 = 0 := by
      field_simp
      ring
    linarith
  have hburg_mul := mul_le_mul_of_nonneg_left hburg_lower (L_beta_pos P β).le
  linarith

/-- Lemma 2(f): `L_β h_ξ - F` is convex on `K_β`. -/
theorem L_beta_shiftedBurg_sub_FSmooth_convexOn (P : ProblemData m n) (β : ℝ) :
    ConvexOn ℝ (K_beta P β) (fun x => L_beta P β * shiftedBurgReal P.ξ x - FSmooth P x) := by
  refine ⟨K_beta_convex P β, fun x hx u hu c₁ c₂ hc₁ hc₂ hsum => ?_⟩
  let z : ℝ → E n := fun t => (1 - t) • x + t • u
  let Φ : E n → ℝ := fun w => L_beta P β * shiftedBurgReal P.ξ w - FSmooth P w
  let φ : ℝ → ℝ := fun t => Φ (z t)
  let φ' : ℝ → ℝ := fun t =>
    ⟪L_beta P β • shiftedBurgGrad P.ξ (z t) - gradient (FSmooth P) (z t), u - x⟫_ℝ
  have hderiv : ∀ t ∈ Set.Icc (0 : ℝ) 1, HasDerivAt φ (φ' t) t :=
    hasDerivAt_segment_shiftedBurg_sub_FSmooth P β hx hu
  have hmono : MonotoneOn φ' (Set.Icc (0 : ℝ) 1) :=
    deriv_segment_monotoneOn P β hx hu
  have hmono_deriv : MonotoneOn (deriv φ) (interior (Set.Icc (0 : ℝ) 1)) := by
    intro t₁ ht₁ t₂ ht₂ h12
    rw [(hderiv t₁ (interior_subset ht₁)).deriv, (hderiv t₂ (interior_subset ht₂)).deriv]
    exact hmono (interior_subset ht₁) (interior_subset ht₂) h12
  have hconv : ConvexOn ℝ (Set.Icc (0 : ℝ) 1) φ := by
    refine hmono_deriv.convexOn_of_deriv (convex_Icc 0 1) ?_ ?_
    · exact fun t ht => (hderiv t ht).continuousAt.continuousWithinAt
    · exact fun t ht => (hderiv t (interior_subset ht)).differentiableAt.differentiableWithinAt
  have hz0 : z 0 = x := by simp [z]
  have hz1 : z 1 = u := by simp [z]
  have hzc : z (c₁ * 0 + c₂ * 1) = c₁ • x + c₂ • u := by
    have hc₁_eq : 1 - c₂ = c₁ := by linarith
    simp [z, hc₁_eq]
  have h_res := hconv.2 ⟨le_rfl, zero_le_one⟩ ⟨zero_le_one, le_rfl⟩ hc₁ hc₂ hsum
  simpa only [smul_eq_mul, φ, hz0, hz1, hzc] using h_res

/-- Bregman descent upper bound on `K_β` deduced from convexity of `L_β h_ξ - F`. -/
theorem FSmooth_bregman_upper_bound (P : ProblemData m n) (β : ℝ) {x u : E n}
    (hx : x ∈ K_beta P β) (hu : u ∈ K_beta P β) :
    FSmooth P u ≤ FSmooth P x + ⟪u - x, gradient (FSmooth P) x⟫_ℝ +
      L_beta P β * bregmanShiftedBurg P.ξ u x := by
  let z : ℝ → E n := fun t => (1 - t) • x + t • u
  let Φ : E n → ℝ := fun w => L_beta P β * shiftedBurgReal P.ξ w - FSmooth P w
  let φ : ℝ → ℝ := fun t => Φ (z t)
  let φ' : ℝ → ℝ := fun t =>
    ⟪L_beta P β • shiftedBurgGrad P.ξ (z t) - gradient (FSmooth P) (z t), u - x⟫_ℝ
  have hderiv := hasDerivAt_segment_shiftedBurg_sub_FSmooth P β hx hu
  have hmono := deriv_segment_monotoneOn P β hx hu
  have hcont : ContinuousOn φ (Set.Icc 0 1) := fun t ht =>
    (hderiv t ht).continuousAt.continuousWithinAt
  have hdiff : DifferentiableOn ℝ φ (Set.Ioo 0 1) := fun t ht =>
    (hderiv t ⟨ht.1.le, ht.2.le⟩).differentiableAt.differentiableWithinAt
  obtain ⟨c, hc, hc_eq⟩ := exists_deriv_eq_slope φ zero_lt_one hcont hdiff
  have hc_deriv : deriv φ c = φ' c := (hderiv c ⟨hc.1.le, hc.2.le⟩).deriv
  rw [hc_deriv, sub_zero, div_one] at hc_eq
  have h0_le_c : φ' 0 ≤ φ' c := hmono ⟨le_rfl, zero_le_one⟩ ⟨hc.1.le, hc.2.le⟩ hc.1.le
  rw [hc_eq] at h0_le_c
  have hz0 : z 0 = x := by simp [z]
  have hz1 : z 1 = u := by simp [z]
  have hφ0 : φ 0 = Φ x := by simp [φ, hz0]
  have hφ1 : φ 1 = Φ u := by simp [φ, hz1]
  have hφ'0 : φ' 0 = L_beta P β * ⟪shiftedBurgGrad P.ξ x, u - x⟫_ℝ - ⟪gradient (FSmooth P) x, u - x⟫_ℝ := by
    dsimp [φ']
    rw [hz0, inner_sub_left, inner_smul_left]
    simp
  rw [hφ0, hφ1, hφ'0] at h0_le_c
  dsimp [Φ] at h0_le_c
  unfold bregmanShiftedBurg
  have hcomm : ⟪u - x, gradient (FSmooth P) x⟫_ℝ = ⟪gradient (FSmooth P) x, u - x⟫_ℝ :=
    real_inner_comm _ _
  linarith

end Lemma2

end DeqMdErratum
