Theorem 5.1 — fixed potential decrease gives a duality-gap bound
ProvedVBSDP.Potential.theorem_5_1Consider the primal semidefinite program defined by symmetric , with linearly independent , matrix size , and the potential parameter . Fix and let , , be strictly feasible primal-dual pairs. Suppose a fixed satisfies at every step . For , if
then the duality gap obeys
This gives a numerical iteration bound whenever a method guarantees a fixed decrease in the potential.
Formalization Note The paper prints a strict “<” conclusion, but equality is possible at the displayed threshold. For , , , , , and , the bound holds with equality at . The non-strict conclusion records the boundary-correct result. The step condition (56) and strict feasibility are required only for the iterates up to , so the statement covers a method that stops after steps. Strict feasibility and protect all logarithms. The Fin m matrices are zero-based with separate.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_VBSDP_Potential_IsStrictlyFeasiblePair import Definitions.Def_VBSDP_Potential_phi
namespace VBSDP.Potential
/-- Theorem 5.1 with the boundary-correct non-strict conclusion. -/
theorem theorem_5_1 {m n : ℕ} [NeZero n] (ν : ℝ) (hν : 1 ≤ ν)
(c : Fin m → ℝ) (F₀ : Matrix (Fin n) (Fin n) ℝ)
(F : Fin m → Matrix (Fin n) (Fin n) ℝ)
(hF₀ : F₀.IsHermitian) (hF : ∀ i, (F i).IsHermitian)
(hlin : LinearIndependent ℝ F)
(xs : ℕ → Fin m → ℝ) (Zs : ℕ → Matrix (Fin n) (Fin n) ℝ) (k : ℕ)
(hfeas : ∀ j ≤ k, IsStrictlyFeasiblePair c F₀ F (xs j) (Zs j))
(δ : ℝ) (hδ : 0 < δ)
(h56 : ∀ j < k, phi ν F₀ F (xs (j + 1)) (Zs (j + 1)) ≤
phi ν F₀ F (xs j) (Zs j) - δ)
(ε : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1)
(hk : (ν * Real.sqrt n * Real.log (1 / ε) +
psi F₀ F (xs 0) (Zs 0)) / δ ≤ k) :
(VBSDP.Duality.lmi F₀ F (xs k) * Zs k).trace ≤
ε * (VBSDP.Duality.lmi F₀ F (xs 0) * Zs 0).trace := by sorry
end VBSDP.Potential
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.