Constant potential reduction yields an explicit iteration bound
ProvedLinearOptimization.interior_point_potential_reductioncomplexityduality-gapinterior-pointpotential-reduction
(Theorem 9.4, p. 410 — generic potential-reduction iteration bound, Section 9.3) Define the potential function
where is a constant larger than (p. 409). Let and with be feasible solutions to the primal and dual problem, respectively. Let be the optimality tolerance.
Any algorithm that maintains primal and dual feasibility and reduces by an amount greater than or equal to at each iteration finds a solution to the primal and dual problems with duality gap
after
iterations.
Preamble
import Definitions.Def_LinearOptimization_LogBarrier_CentralPath import Definitions.Def_LinearOptimization_InteriorPointPotential open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 9.4 (p. 410).** Potential reduction implies an explicit iteration bound: if every step keeps `(x^k, s^k)` interior primal-dual feasible and cuts `G` by at least `δ`, then after `K = ⌈(G(x⁰, s⁰) + (q − n) log(1/ε) − n log n) / δ⌉` iterations the duality gap satisfies `(s^K)'x^K ≤ ε`. -/
Formal statement
theorem LinearOptimization.interior_point_potential_reduction {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(q delta eps : ℝ) (hq : (n : ℝ) < q) (hdelta : 0 < delta)
(heps : 0 < eps)
(x : ℕ → Fin n → ℝ) (p : ℕ → Fin m → ℝ) (s : ℕ → Fin n → ℝ)
(hfeas : ∀ k, A.mulVec (x k) = b ∧ (∀ j, 0 < x k j) ∧
Aᵀ.mulVec (p k) + s k = c ∧ (∀ j, 0 < s k j))
(hdec : ∀ k, interiorPointPotential q (x (k + 1)) (s (k + 1)) ≤
interiorPointPotential q (x k) (s k) - delta)
(K : ℕ)
(hK : K = ⌈(interiorPointPotential q (x 0) (s 0) +
(q - n) * Real.log (1 / eps) - n * Real.log n) / delta⌉₊) :
s K ⬝ᵥ x K ≤ eps := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 9.4, p. 410 (potential function p. 409, Assumption 9.3 p. 409)