Lemma 4.2, p. 15 — the NT scaling: θ² = √(sᵀQs/xᵀQx), and W is (1/θ)(X⁻¹S)^{1/2}, (31) or (34) with w of (32), W² = −Q + 2wwᵀ
ProvedConicQuadIPM.NTScaling.lemma_4_2Let be one cone block — the positive half-line , the quadratic cone or the rotated quadratic cone — with matrices , of Definition 3.2, and let . A Nesterov–Todd (NT) scaling of is a pair , with , and (28). Then:
- (30) Every NT scaling satisfies
- Let be given by (30) and
- i) If , then (with , ) makes an NT scaling.
- ii) If , then
makes $(\theta,W)$ an NT scaling, the two expressions agree, and $W^2 = -Q + 2ww^T$ (33).
- iii) If , then
makes $(\theta,W)$ an NT scaling, and $W^2 = -Q + 2ww^T$ (35).
The lemma gives closed forms for the NT scaling of each cone of a conic quadratic program: is determined by one vector per cone, and , and their inverses can be applied in operations. This is what makes the NT direction practical in an implementation such as MOSEK.
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 interior is written with strict inequalities (; , ; ). The paper names and without quantifying them. The statement reads them as in the paper's proof: part 1 holds for every NT scaling, and part 2 asserts that the displayed , form an NT scaling. Uniqueness of the NT scaling among all scaling matrices is not claimed (the paper does not prove it). For , is the matrix and its square root is (Wnonneg).
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_ConicQuadIPM_NTScaling_Setting import Definitions.Def_ConicQuadIPM_NTScaling_Scaling open Matrix
namespace ConicQuadIPM.NTScaling
/-- Lemma 4.2, p. 15, for one cone block with `x, s` in the interior:
(a) every NT scaling `θ, W` satisfies (30); (b) `θ` of (30) with `W` of i) (`R₊`), (31) (`K^q`)
or (34) (`K^r`), `w` of (32), is an NT scaling; the two forms of (31) agree; and
`W² = −Q + 2wwᵀ` ((33), (35)). -/
theorem lemma_4_2 (kind : ConicQuadIPM.Complementarity.ConeKind) (d : ℕ) (hwf : WellFormedBlock kind d)
(x s : Fin d → ℝ) (hx : inConeInt kind x) (hs : inConeInt kind s) :
(∀ (θ : ℝ) (W : Matrix (Fin d) (Fin d) ℝ), IsNT kind d θ W x s →
θ ^ 2 = Real.sqrt ((s ⬝ᵥ (Qmat kind d *ᵥ s)) / (x ⬝ᵥ (Qmat kind d *ᵥ x)))) ∧
(kind = .nonneg →
IsNT .nonneg d (thetaNT .nonneg d x s) (Wnonneg d x s) x s) ∧
(kind = .quad →
IsNT .quad d (thetaNT .quad d x s) (WquadOuter d (wNT .quad d x s)) x s ∧
WquadArrow (wNT .quad d x s) = WquadOuter d (wNT .quad d x s) ∧
WquadOuter d (wNT .quad d x s) * WquadOuter d (wNT .quad d x s) =
-Qmat .quad d + (2 : ℝ) • vecMulVec (wNT .quad d x s) (wNT .quad d x s)) ∧
(kind = .rot →
IsNT .rot d (thetaNT .rot d x s) (Wrot d (wNT .rot d x s)) x s ∧
Wrot d (wNT .rot d x s) * Wrot d (wNT .rot d x s) =
-Qmat .rot d + (2 : ℝ) • vecMulVec (wNT .rot d x s) (wNT .rot d x s)) := by sorry
end ConicQuadIPM.NTScaling
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.