Appendix, proof of Lemma 4.2, p. 38 — WQW = Q for the arrow form of (31) forces w₁² − ‖w_{2:n}‖² = 1
ProvedConicQuadIPM.NTScaling.w_normalizationconic-optimizationnesterov-todd-scalingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1second-order-cone
Let and be the matrix of the quadratic cone. For with let
If , then
This normalization is what makes the square of collapse to the rank-one correction (62).
Formalization Note 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 hypothesis is added so that the division by , which the page performs without comment, is defined.
Preamble
import Mathlib import Definitions.Def_ConicQuadIPM_NTScaling_Setting import Definitions.Def_ConicQuadIPM_NTScaling_Scaling open Matrix
Formal statement
namespace ConicQuadIPM.NTScaling
/-- Appendix, proof of Lemma 4.2, p. 38: if the arrow-form matrix (31) satisfies `WQW = Q` for
the quadratic cone, then `w₁² − ‖w_{2:n}‖² = 1`. -/
theorem w_normalization (d : ℕ) (hd : 1 ≤ d) (w : Fin d → ℝ) (hw : 0 < 1 + ConicQuadIPM.Complementarity.coord w 0)
(hWQW : WquadArrow w * Qmat .quad d * WquadArrow w = Qmat .quad d) :
ConicQuadIPM.Complementarity.coord w 0 ^ 2 - ConicQuadIPM.Complementarity.tailSq w 1 = 1 := by sorry
end ConicQuadIPM.NTScaling
Source
Andersen, Roos & Terlaky, On implementing a primal-dual interior-point method for conic quadratic optimization, Math. Program. (2003), DOI 10.1007/s10107-002-0349-3; authors' preprint of 18 Dec 2000, p. 38, Appendix, proof of Lemma 4.2 (line after (62))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.