p. 314 — the rank-one correction A_{k+1}⁻¹ = (1 + ε/((n−1)(1+ε)))A_k⁻¹ − (ε/((n−1)(1+ε)²)) b bᵗ
ProvedKhachiyanRound.BCD.rank_one_correctioncoordinate-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rank-one-update
Let , and . Let be an index maximizing , let , , and let be the BCD step from . With and ,
The inverse moment matrix is thus updated by a rank-one correction, which is what makes each BCD iteration cost arithmetic operations.
Formalization Note Only the matrix identity is formalized; the operation count per iteration is not. Central symmetry (2.1) and full dimension (2.2) are not needed ( already makes invertible) and are dropped; is kept, as the formula divides by .
Preamble
import Mathlib import Definitions.Def_LinearOptimization_Ellipsoid import Definitions.Def_KhachiyanRound_BCD_Setting open scoped Pointwise
Formal statement
namespace KhachiyanRound.BCD
theorem rank_one_correction {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ}
(a : ι → Fin n → ℝ) (hn : 2 ≤ n) (p : ι → ℝ) (hp : p ∈ SF a)
(r : ι) (hr : ∀ j, w a p j ≤ w a p r)
(ε τ : ℝ) (hε : ε = epsOf a p) (hτ : τ = ε / (w a p r - 1))
(b : Fin n → ℝ) (hb : b = (momentMatrix a p)⁻¹.mulVec (a r)) :
(momentMatrix a ((1 - τ) • p + τ • Pi.single r 1))⁻¹ =
(1 + ε / (((n : ℝ) - 1) * (1 + ε))) • (momentMatrix a p)⁻¹ -
(ε / (((n : ℝ) - 1) * (1 + ε) ^ 2)) • Matrix.vecMulVec b b := by sorry
end KhachiyanRound.BCD
Source
Khachiyan, Rounding of polytopes in the real number model of computation, Math. Oper. Res. 21 (1996), p. 314, rank-one corrections after the proof of Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.