Lemma 3.3 i)–iii), p. 12 — scaling preserves xᵀs and rescales xᵀQx by θ², sᵀQs by θ⁻²
ProvedConicQuadIPM.NTScaling.lemma_3_3_i_iiiLet be one of , , in dimension , with matrix of Definition 3.2. Let , let be a scaling matrix (, ), and for put , . Then
Scaling therefore leaves the duality gap unchanged and changes the "Lorentz norms" , only by the factors . This is what determines in the Nesterov–Todd scaling (30).
Formalization Note The statement is made for one cone block , with the superscript dropped: and are block diagonal (p. 11–12), so the per-block statement is the paper's statement block by block. Vectors are Fin d → ℝ with 0-based indices (the paper's is coord x 0); is tailSq x 1, a sum of squares (Euclidean, never Mathlib's sup norm); is x ⬝ᵥ s. The dimension conventions the paper leaves implicit ( for , for , for ) are the hypothesis WellFormedBlock kind d. The hypothesis is implicit in the paper ( is positive definite, p. 24).
import Mathlib import Definitions.Def_ConicQuadIPM_NTScaling_Setting import Definitions.Def_ConicQuadIPM_NTScaling_Scaling open Matrix
namespace ConicQuadIPM.NTScaling
/-- Lemma 3.3 i)–iii), p. 12, for one cone block. -/
theorem lemma_3_3_i_iii (kind : ConicQuadIPM.Complementarity.ConeKind) (d : ℕ) (hwf : WellFormedBlock kind d)
(θ : ℝ) (hθ : 0 < θ) (W : Matrix (Fin d) (Fin d) ℝ) (hW : IsScaling kind d W)
(x s : Fin d → ℝ) :
x ⬝ᵥ s = xbar θ W x ⬝ᵥ sbar θ W s ∧
θ ^ 2 * (x ⬝ᵥ (Qmat kind d *ᵥ x)) = xbar θ W x ⬝ᵥ (Qmat kind d *ᵥ xbar θ W x) ∧
(θ ^ 2)⁻¹ * (s ⬝ᵥ (Qmat kind d *ᵥ s)) = sbar θ W s ⬝ᵥ (Qmat kind d *ᵥ sbar θ W s) := by sorry
end ConicQuadIPM.NTScaling
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.