(63), Appendix p. 39 — for the rotated cone, Ŵ = TWT satisfies ŴQ̂Ŵ = Q̂ and ŝ = θ²Ŵ²x̂
ProvedConicQuadIPM.NTScaling.eq_63conic-optimizationnesterov-todd-scalingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1second-order-cone
Let , let , be the matrices (18), (19) of the rotated quadratic cone, and put , , , for a matrix and vectors . Then for every :
- if then ;
- if then
These identities transport the NT condition for the rotated cone to the quadratic cone, where (31) applies.
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 page writes in the last two members of (63) and then shows (formalized in rot_hat_quantities); here (63) is stated with . The page's is a printed slip for . The facts , the page uses are consequences of (18), not hypotheses.
Preamble
import Mathlib import Definitions.Def_ConicQuadIPM_NTScaling_Setting import Definitions.Def_ConicQuadIPM_NTScaling_Scaling open Matrix
Formal statement
namespace ConicQuadIPM.NTScaling
/-- (63), Appendix, proof of Lemma 4.2, p. 39 (rotated quadratic cone): with `Q̂ = TQT` and
`Ŵ = TWT`, `WQW = Q` gives `ŴQ̂Ŵ = Q̂`, and `s = θ²W²x` gives `ŝ = θ²Ŵ²x̂` for `x̂ = Tx`,
`ŝ = Ts`. -/
theorem eq_63 (d : ℕ) (hd : 2 ≤ d) (W : Matrix (Fin d) (Fin d) ℝ) (θ : ℝ)
(x s : Fin d → ℝ) :
(W * Qmat .rot d * W = Qmat .rot d →
(Tmat .rot d * W * Tmat .rot d) * (Tmat .rot d * Qmat .rot d * Tmat .rot d) *
(Tmat .rot d * W * Tmat .rot d) =
Tmat .rot d * Qmat .rot d * Tmat .rot d) ∧
(s = θ ^ 2 • ((W * W) *ᵥ x) →
Tmat .rot d *ᵥ s =
θ ^ 2 • (((Tmat .rot d * W * Tmat .rot d) * (Tmat .rot d * W * Tmat .rot d)) *ᵥ
(Tmat .rot d *ᵥ x))) := 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. 39, Appendix, proof of Lemma 4.2, (63)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.