Theorem 7.1.3 (ii) — rank-sensitive tightness of the real mixed-block Matrix Cube certificate
ProvedRobustOpt2009.SDPApproximation.theorem_7_1_3_iiThis is part (ii) of the real mixed-block Matrix Cube Theorem (Theorem 7.1.3): the rank-sensitive tightness of the semidefinite certificate .
Let be real symmetric matrices (), and let , , , with . For let be the robust condition
and, for a fixed , let ask for symmetric matrices with
Claim. There is one universal nondecreasing function with
such that for all data as above and every integer with for all :
Part (i) of Theorem 7.1.3 (sufficiency , and exactness for a single perturbation block) is elementary; this child isolates the hard part, whose proof in the book (Appendix B.4.6, Theorem B.4.14) goes through semidefinite duality and Gaussian randomization. The predicates are expanded verbatim as in the parent statement theorem_7_1_3; is the spectral (L2 operator) norm.
import Mathlib open Matrix open scoped Matrix.Norms.L2Operator
namespace RobustOpt2009.SDPApproximation
/-- Theorem 7.1.3 (ii): the rank-sensitive tightness bound of the real mixed-block
Matrix Cube Theorem, with one universal nondecreasing function `θ`. -/
theorem theorem_7_1_3_ii :
∃ θ : ℕ → ℝ, Monotone θ ∧ θ 2 = Real.pi / 2 ∧ θ 4 = 2 ∧
(∀ μ : ℕ, 2 ≤ μ → θ μ ≤ Real.pi * Real.sqrt ((μ : ℝ) / 2)) ∧
∀ (m s f : ℕ), 0 < m → ∀ (p q : Fin f → ℕ),
(∀ j, 0 < p j) → (∀ j, 0 < q j) →
∀ (B₀ : Matrix (Fin m) (Fin m) ℝ) (B : Fin s → Matrix (Fin m) (Fin m) ℝ)
(L : (j : Fin f) → Matrix (Fin (p j)) (Fin m) ℝ)
(R : (j : Fin f) → Matrix (Fin (q j)) (Fin m) ℝ),
B₀.IsHermitian → (∀ i, (B i).IsHermitian) → ∀ ρ : ℝ, 0 ≤ ρ →
let a : ℝ → Prop := fun r =>
∀ (z : Fin s → ℝ) (Z : (j : Fin f) → Matrix (Fin (p j)) (Fin (q j)) ℝ),
(∀ i, |z i| ≤ r) → (∀ j, ‖Z j‖ ≤ r) →
(B₀ + (∑ i, z i • B i) +
∑ j, ((L j)ᵀ * Z j * R j + (R j)ᵀ * (Z j)ᵀ * L j)).PosSemidef
let b : Prop :=
∃ (U : Fin s → Matrix (Fin m) (Fin m) ℝ)
(V : Fin f → Matrix (Fin m) (Fin m) ℝ),
(∀ i, (U i).IsHermitian) ∧ (∀ j, (V j).IsHermitian) ∧
(∀ i, (U i - B i).PosSemidef ∧ (U i + B i).PosSemidef) ∧
(∀ j, ∀ Z : Matrix (Fin (p j)) (Fin (q j)) ℝ, ‖Z‖ ≤ 1 →
(V j - ((L j)ᵀ * Z * R j + (R j)ᵀ * Zᵀ * L j)).PosSemidef) ∧
(B₀ - ρ • (∑ i, U i) - ρ • (∑ j, V j)).PosSemidef
∀ μ : ℕ, 2 ≤ μ → (∀ i, (B i).rank ≤ μ) → ¬ b → ¬ a (θ μ * ρ) := by sorry
end RobustOpt2009.SDPApproximation