App. A, proof of Proposition 1, p. 34 — if y_j ≥ x_j², the matrix X with diagonal y and off-diagonal x_jx_k gives [[1, xᵀ], [x, X]] ⪰ 0
ProvedQCQPTightness.SOCP.lift_psd_of_diag_gep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1positive-semidefinitesocp-relaxation
Let with for all . Define by and for . Then
This is the construction in the proof that : an SOCP-feasible lifts to an SDP-feasible with the same diagonal.
Preamble
import Mathlib import Definitions.Def_QCQPTightness_SOCP_QCQP
Formal statement
namespace QCQPTightness.SOCP
open Matrix
/-- App. A, proof of Proposition 1, p. 34: if `y_j ≥ x_j²` for every `j`, the matrix `X` with
`X_{jj} = y_j` and `X_{jk} = x_j x_k` (`j ≠ k`) gives `[[1, xᵀ], [x, X]] ⪰ 0`. -/
theorem lift_psd_of_diag_ge {N : ℕ} (x y : Fin N → ℝ) (hxy : ∀ j, x j ^ 2 ≤ y j) :
(QCQPTightness.ConvHull.liftY x (Matrix.of fun j k => if j = k then y j else x j * x k)).PosSemidef := by sorry
end QCQPTightness.SOCP
Source
arXiv:1911.09195v3, App. A, proof of Proposition 1, p. 34
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.