import DeqMdErratum.KL
import DeqMdErratum.Lemma3

/-!
# Theorem 4: Global Sequence Convergence of Constant-Step Shifted-Burg Mirror Descent

This module formalizes Theorem 4 of the erratum (p. 3):
* Under a constant step size `τ ∈ (0, τ_bar)` starting from `x⁰ ∈ [0, a]^n` with `Ψ(x⁰) < +∞`,
  the shifted-Burg Mirror Descent sequence `x^{k+1} := T_τ(x^k)` stays in `L₀`, satisfies
  Theorem A.8's hypotheses `(H1)-(H3)`, has finite trajectory length
  `∑_{k=0}^∞ ‖x^{k+1} - x^k‖ < ∞` (assuming `HasKL (Psi P)`), and converges to a critical point
  `x^∞ ∈ crit(Ψ) ∩ L₀` satisfying `x^∞ = T_τ(x^∞)`.
-/

open Filter Topology
open scoped BigOperators InnerProductSpace

namespace DeqMdErratum

section ConvergenceHelpers

variable {m n : ℕ}

lemma L0_isClosed (P : ProblemData m n) (x0 : E n) : IsClosed (L0 P x0) := by
  have hsub : IsClosed {x : E n | Psi P x ≤ Psi P x0} :=
    (lowerSemicontinuous_iff_isClosed_preimage.mp (Psi_lowerSemicontinuous P)) (Psi P x0)
  exact (boxSet_isClosed n P.a).inter hsub

lemma L0_isBounded (P : ProblemData m n) {x0 : E n} {z : ℕ → E n}
    (hz : ∀ k, z k ∈ L0 P x0) :
    Bornology.IsBounded (Set.range z) := by
  refine (boxSet_isCompact n P.a).isBounded.subset ?_
  rintro x ⟨k, rfl⟩
  exact (hz k).1

/-- Any subsequence converging in `L₀` has convergent objective values `(H3)` by continuity of
`FSmooth` on the open neighborhood `UPos P ∩ P.U_R` containing `K_{β₀}`. -/
lemma Psi_tendsto_of_mem_L0 (P : ProblemData m n) {x0 : E n}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    {z : ℕ → E n} (hz_L0 : ∀ k, z k ∈ L0 P x0)
    {x_bar : E n} {ψ : ℕ → ℕ} (_hψ : StrictMono ψ)
    (hlim : Tendsto (z ∘ ψ) atTop (𝓝 x_bar)) :
    Tendsto (fun j => Psi P (z (ψ j))) atTop (𝓝 (Psi P x_bar)) := by
  have hx_bar_box : x_bar ∈ boxSet n P.a :=
    (boxSet_isClosed n P.a).mem_of_tendsto hlim (Eventually.of_forall fun j => (hz_L0 (ψ j)).1)
  have hx_bar_K0 : x_bar ∈ K_beta P (beta0 P x0) :=
    (K_beta_isClosed P (beta0 P x0)).mem_of_tendsto hlim
      (Eventually.of_forall fun j => L0_subset_K_beta0 P hx0_box hx0_fin (hz_L0 (ψ j)))
  have hx_bar_UPos : x_bar ∈ UPos P := K_beta_subset_UPos P (beta0 P x0) hx_bar_K0
  have hV_open : IsOpen (UPos P ∩ P.U_R) := (isOpen_UPos P).inter P.hU_R_open
  have hF_cont : ContinuousAt (FSmooth P) x_bar :=
    ((FSmooth_contDiffOn_open P).continuousOn.continuousAt
      (hV_open.mem_nhds (K_beta_subset_open P (beta0 P x0) hx_bar_K0)))
  have hPsi_cont : Tendsto (fun j => (FSmooth P (z (ψ j)) : EReal)) atTop
      (𝓝 (FSmooth P x_bar : EReal)) :=
    (continuous_coe_real_ereal.continuousAt.tendsto).comp (hF_cont.tendsto.comp hlim)
  rw [Psi_eq_FSmooth_on_box_inter_UPos P hx_bar_box hx_bar_UPos]
  exact hPsi_cont.congr fun j => (Psi_eq_FSmooth_on_box_inter_UPos P (hz_L0 (ψ j)).1
    (K_beta_subset_UPos P (beta0 P x0) (L0_subset_K_beta0 P hx0_box hx0_fin (hz_L0 (ψ j))))).symm

lemma T_tau_fixed_point_of_tendsto (P : ProblemData m n) {x0 : E n}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    {z : ℕ → E n} {τs : ℕ → ℝ} {x_inf : E n} {τ_inf : ℝ}
    (hz_L0 : ∀ k, z k ∈ L0 P x0)
    (hstep : ∀ k, z (k + 1) = T_tau P (τs k) (z k))
    (hτ_lim : Tendsto τs atTop (𝓝 τ_inf))
    (hz_lim : Tendsto z atTop (𝓝 x_inf)) :
    x_inf = T_tau P τ_inf x_inf := by
  have hx_inf_K0 : x_inf ∈ K_beta P (beta0 P x0) :=
    (K_beta_isClosed P (beta0 P x0)).mem_of_tendsto hz_lim
      (Eventually.of_forall fun k => L0_subset_K_beta0 P hx0_box hx0_fin (hz_L0 k))
  have hx_inf_V : x_inf ∈ UPos P ∩ P.U_R := K_beta_subset_open P (beta0 P x0) hx_inf_K0
  have hV_open : IsOpen (UPos P ∩ P.U_R) := (isOpen_UPos P).inter P.hU_R_open
  have hg_cont : ContinuousAt (gradient (FSmooth P)) x_inf :=
    (gradient_FSmooth_continuousOn P).continuousAt (hV_open.mem_nhds hx_inf_V)
  have hT_joint : Tendsto (fun k => T_tau P (τs k) (z k)) atTop (𝓝 (T_tau P τ_inf x_inf)) := by
    have hpair : Tendsto (fun k => (τs k, z k)) atTop (𝓝 (τ_inf, x_inf)) := hτ_lim.prodMk_nhds hz_lim
    have hcoord_lim : Tendsto (fun k => fun j : Fin n => T_tau P (τs k) (z k) j) atTop
        (𝓝 (fun j : Fin n => T_tau P τ_inf x_inf j)) := by
      apply tendsto_pi_nhds.mpr
      intro j
      set δ : ℝ := P.ξ / (2 * (P.a + P.ξ))
      have hδ_pos : 0 < δ := div_pos P.hξ (by linarith [P.ha, P.hξ])
      let clamped : ℝ × E n → ℝ := fun p =>
        max 0 (min P.a ((p.2 j + P.ξ) / max δ (1 + p.1 * (p.2 j + P.ξ) * gradient (FSmooth P) p.2 j) - P.ξ))
      have hclamped_cont : ContinuousAt clamped (τ_inf, x_inf) := by
        have hp1 : ContinuousAt (fun p : ℝ × E n => p.1) (τ_inf, x_inf) := continuousAt_fst
        have hp2j : ContinuousAt (fun p : ℝ × E n => p.2 j) (τ_inf, x_inf) :=
          (E_coord_continuous j).continuousAt.comp continuousAt_snd
        have hg2 : ContinuousAt (fun p : ℝ × E n => gradient (FSmooth P) p.2) (τ_inf, x_inf) :=
          ContinuousAt.comp (g := gradient (FSmooth P)) (f := Prod.snd) hg_cont continuousAt_snd
        have hgj : ContinuousAt (fun p : ℝ × E n => gradient (FSmooth P) p.2 j) (τ_inf, x_inf) :=
          ContinuousAt.comp (g := fun v : E n => v j) (E_coord_continuous j).continuousAt hg2
        have hd : ContinuousAt (fun p : ℝ × E n => 1 + p.1 * (p.2 j + P.ξ) * gradient (FSmooth P) p.2 j)
            (τ_inf, x_inf) :=
          continuousAt_const.add ((hp1.mul (hp2j.add continuousAt_const)).mul hgj)
        have hden : ContinuousAt
            (fun p : ℝ × E n => max δ (1 + p.1 * (p.2 j + P.ξ) * gradient (FSmooth P) p.2 j))
            (τ_inf, x_inf) :=
          continuousAt_const.max hd
        have hdiv : ContinuousAt
            (fun p : ℝ × E n => (p.2 j + P.ξ) / max δ (1 + p.1 * (p.2 j + P.ξ) * gradient (FSmooth P) p.2 j))
            (τ_inf, x_inf) :=
          (hp2j.add continuousAt_const).div hden (lt_max_of_lt_left hδ_pos).ne'
        exact continuousAt_const.max (continuousAt_const.min (hdiv.sub continuousAt_const))
      have hlim_clamped : Tendsto (fun k => clamped (τs k, z k)) atTop (𝓝 (clamped (τ_inf, x_inf))) :=
        hclamped_cont.tendsto.comp hpair
      have heq_k : ∀ k, T_tau P (τs k) (z k) j = clamped (τs k, z k) := fun k =>
        T_tauCoord_eq_clamped P.ha P.hξ ((hz_L0 k).1 j)
      have hx_inf_box : x_inf ∈ boxSet n P.a :=
        (boxSet_isClosed n P.a).mem_of_tendsto hz_lim (Eventually.of_forall fun k => (hz_L0 k).1)
      have heq_lim : T_tau P τ_inf x_inf j = clamped (τ_inf, x_inf) :=
        T_tauCoord_eq_clamped P.ha P.hξ (hx_inf_box j)
      simpa only [← heq_k, ← heq_lim] using hlim_clamped
    have htoLp := (PiLp.continuous_toLp 2 (fun _ : Fin n => ℝ)).continuousAt.tendsto.comp hcoord_lim
    simpa [E_ext] using htoLp
  have hshift : Tendsto (fun k => z (k + 1)) atTop (𝓝 x_inf) :=
    (tendsto_add_atTop_iff_nat 1).mpr hz_lim
  have hT_lim : Tendsto (fun k => z (k + 1)) atTop (𝓝 (T_tau P τ_inf x_inf)) :=
    hT_joint.congr fun k => (hstep k).symm
  exact tendsto_nhds_unique hshift hT_lim

end ConvergenceHelpers

section Theorem4Section

variable {m n : ℕ}

/-- Constant-step shifted-Burg Mirror Descent sequence `x^{k+1} = T_τ(x^k)`. -/
noncomputable def mdIter (P : ProblemData m n) (τ : ℝ) (x0 : E n) : ℕ → E n
  | 0 => x0
  | k + 1 => T_tau P τ (mdIter P τ x0 k)

lemma mdIter_mem_L0 (P : ProblemData m n) {x0 : E n} {τ : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ : τ ∈ Set.Ioo 0 (tauBar P x0)) :
    ∀ k : ℕ, mdIter P τ x0 k ∈ L0 P x0 := by
  intro k
  induction k with
  | zero => exact ⟨hx0_box, le_rfl⟩
  | succ k ih => exact (lemma_3 P hx0_box hx0_fin ih hτ).2.2.2.1

/-- Theorem 4 (Global sequence convergence for constant step size `τ ∈ (0, τ_bar)`):
Under the Kurdyka-Łojasiewicz property (`HasKL (Psi P)`), the sequence generated by
`x^{k+1} = T_τ(x^k)` has finite length `∑ ‖x^{k+1} - x^k‖ < ∞` and converges to a critical point
`x^∞ ∈ crit(Ψ) ∩ L₀` which is a fixed point `x^∞ = T_τ(x^∞)`. -/
theorem theorem_4 (P : ProblemData m n) {x0 : E n} {τ : ℝ}
    (hx0_box : x0 ∈ boxSet n P.a) (hx0_fin : Psi P x0 ≠ ⊤)
    (hτ : τ ∈ Set.Ioo 0 (tauBar P x0)) (hKL : HasKL (Psi P)) :
    Summable (fun k => ‖mdIter P τ x0 (k + 1) - mdIter P τ x0 k‖) ∧
      ∃ x_inf : E n, Tendsto (mdIter P τ x0) atTop (𝓝 x_inf) ∧
        x_inf ∈ crit (Psi P) ∧ x_inf ∈ L0 P x0 ∧ x_inf = T_tau P τ x_inf := by
  have hx_L0 : ∀ k, mdIter P τ x0 k ∈ L0 P x0 := mdIter_mem_L0 P hx0_box hx0_fin hτ
  have hx_dom : ∀ k, mdIter P τ x0 k ∈ effectiveDom (Psi P) := by
    intro k
    rw [effectiveDom_Psi_eq]
    exact ⟨(hx_L0 k).1, K_beta_subset_UPos P (beta0 P x0)
      (L0_subset_K_beta0 P hx0_box hx0_fin (hx_L0 k))⟩
  obtain ⟨hτ_pos, _, hτL⟩ := (mem_Ioo_tauBar_iff P).mp hτ
  have hξ_pos : 0 < P.ξ := P.hξ
  have haξ_pos : 0 < P.a + P.ξ := by linarith [P.ha, P.hξ]
  have hcoef_pos : 0 < 1 / τ - L_beta P (beta1 P x0) := by
    have hinv : L_beta P (beta1 P x0) < 1 / τ := (lt_div_iff₀' hτ_pos).mpr hτL
    linarith
  set c₁ : ℝ := (1 / τ - L_beta P (beta1 P x0)) / (2 * (P.a + P.ξ) ^ 2)
  have hc₁_pos : 0 < c₁ := div_pos hcoef_pos (mul_pos zero_lt_two (sq_pos_of_pos haξ_pos))
  set b : ℝ := M_beta P (beta1 P x0) + 1 / (τ * P.ξ ^ 2)
  have hb_pos : 0 < b := add_pos (M_beta_pos P (beta1 P x0))
    (one_div_pos.mpr (mul_pos hτ_pos (sq_pos_of_pos hξ_pos)))
  have hH1 : ∀ k, Psi P (mdIter P τ x0 (k + 1)) +
      ((c₁ * ‖mdIter P τ x0 (k + 1) - mdIter P τ x0 k‖ ^ 2 : ℝ) : EReal) ≤
      Psi P (mdIter P τ x0 k) := by
    intro k
    have h3 := lemma_3 P hx0_box hx0_fin (hx_L0 k) hτ
    have hdesc : (1 / τ - L_beta P (beta1 P x0)) *
        bregmanShiftedBurg P.ξ (mdIter P τ x0 (k + 1)) (mdIter P τ x0 k) ≤
        (Psi P (mdIter P τ x0 k)).toReal - (Psi P (mdIter P τ x0 (k + 1))).toReal := h3.2.2.1
    have hbreg_ge : (1 / (2 * (P.a + P.ξ) ^ 2)) * ‖mdIter P τ x0 (k + 1) - mdIter P τ x0 k‖ ^ 2 ≤
        bregmanShiftedBurg P.ξ (mdIter P τ x0 (k + 1)) (mdIter P τ x0 k) :=
      bregmanShiftedBurg_ge_norm_sq P.hξ (hx_L0 (k + 1)).1 (hx_L0 k).1
    have hc1_le : c₁ * ‖mdIter P τ x0 (k + 1) - mdIter P τ x0 k‖ ^ 2 ≤
        (1 / τ - L_beta P (beta1 P x0)) *
          bregmanShiftedBurg P.ξ (mdIter P τ x0 (k + 1)) (mdIter P τ x0 k) := by
      have hmul := mul_le_mul_of_nonneg_left hbreg_ge hcoef_pos.le
      have heq : (1 / τ - L_beta P (beta1 P x0)) *
          ((1 / (2 * (P.a + P.ξ) ^ 2)) * ‖mdIter P τ x0 (k + 1) - mdIter P τ x0 k‖ ^ 2) =
          c₁ * ‖mdIter P τ x0 (k + 1) - mdIter P τ x0 k‖ ^ 2 := by
        dsimp [c₁]; ring
      linarith
    have hreal_le : (Psi P (mdIter P τ x0 (k + 1))).toReal +
        c₁ * ‖mdIter P τ x0 (k + 1) - mdIter P τ x0 k‖ ^ 2 ≤
        (Psi P (mdIter P τ x0 k)).toReal := by linarith
    rw [← EReal.coe_toReal_of_mem_effectiveDom (hx_dom (k + 1)),
      ← EReal.coe_toReal_of_mem_effectiveDom (hx_dom k), ← EReal.coe_add, EReal.coe_le_coe_iff]
    exact hreal_le
  have hH2 : ∀ k, ∃ ω ∈ limitingSubdiff (Psi P) (mdIter P τ x0 (k + 1)),
      ‖ω‖ ≤ b * ‖mdIter P τ x0 (k + 1) - mdIter P τ x0 k‖ := by
    intro k
    exact ⟨_, (lemma_3 P hx0_box hx0_fin (hx_L0 k) hτ).2.2.2.2⟩
  have hH3 : ∀ x_bar ψ, StrictMono ψ →
      Tendsto (mdIter P τ x0 ∘ ψ) atTop (𝓝 x_bar) →
      Tendsto (fun j => Psi P (mdIter P τ x0 (ψ j))) atTop (𝓝 (Psi P x_bar)) :=
    fun _x_bar _ψ hψ hlim => Psi_tendsto_of_mem_L0 P hx0_box hx0_fin hx_L0 hψ hlim
  obtain ⟨hsumm, x_inf, hlim, hcrit⟩ := theorem_A8 (Psi_isProper P) (Psi_lowerSemicontinuous P)
    (Psi_bddBelow P) hKL (hx_dom 0) (L0_isBounded P hx_L0) hc₁_pos hH1 hb_pos hH2 hH3
  have hx_inf_L0 : x_inf ∈ L0 P x0 :=
    (L0_isClosed P x0).mem_of_tendsto hlim (Eventually.of_forall hx_L0)
  have hfix : x_inf = T_tau P τ x_inf :=
    T_tau_fixed_point_of_tendsto P hx0_box hx0_fin hx_L0 (fun k => rfl) tendsto_const_nhds hlim
  exact ⟨hsumm, x_inf, hlim, hcrit, hx_inf_L0, hfix⟩

end Theorem4Section

end DeqMdErratum
