Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.1.3 — Real mixed-block Matrix Cube Theorem

Proved
RobustOpt2009.SDPApproximation.theorem_7_1_3

by Shuze Chen · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

matrix-cuberobust-optimizationsemidefinite-programming

Let B0,B1,…,BsB_0,B_1,\ldots,B_sB0​,B1​,…,Bs​ be real symmetric m×mm\times mm×m matrices, where m>0m>0m>0, and let Lj∈Rpj×mL_j\in\mathbb R^{p_j\times m}Lj​∈Rpj​×m, Rj∈Rqj×mR_j\in\mathbb R^{q_j\times m}Rj​∈Rqj​×m for j=1,…,fj=1,\ldots,fj=1,…,f, with positive block dimensions. For ρ≥0\rho\ge0ρ≥0, let A(ρ)\mathcal A(\rho)A(ρ) require

B0+∑iziBi+∑j(LjTZjRj+RjTZjTLj)⪰0B_0+\sum_i z_iB_i+\sum_j(L_j^TZ_jR_j+R_j^TZ_j^TL_j)\succeq0B0​+i∑​zi​Bi​+j∑​(LjT​Zj​Rj​+RjT​ZjT​Lj​)⪰0

for every ∣zi∣≤ρ|z_i|\le\rho∣zi​∣≤ρ, ∥Zj∥2,2≤ρ\|Z_j\|_{2,2}\le\rho∥Zj​∥2,2​≤ρ. Let B(ρ)\mathcal B(\rho)B(ρ) ask for symmetric Ui,VjU_i,V_jUi​,Vj​ dominating respectively ±Bi\pm B_i±Bi​ and every unit-radius full-block perturbation, with B0−ρ∑iUi−ρ∑jVj⪰0B_0-\rho\sum_iU_i-\rho\sum_jV_j\succeq0B0​−ρ∑i​Ui​−ρ∑j​Vj​⪰0.

There is a universal nondecreasing function ϑ\varthetaϑ such that ϑ(2)=π/2\vartheta(2)=\pi/2ϑ(2)=π/2, ϑ(4)=2\vartheta(4)=2ϑ(4)=2, and ϑ(μ)≤πμ/2\vartheta(\mu)\le\pi\sqrt{\mu/2}ϑ(μ)≤πμ/2​ for integers μ≥2\mu\ge2μ≥2. For all the data above:

B(ρ)⟹A(ρ).\mathcal B(\rho)\Longrightarrow\mathcal A(\rho).B(ρ)⟹A(ρ).

When s+f=1s+f=1s+f=1, these conditions are equivalent. Whenever μ≥2\mu\ge2μ≥2 bounds every scalar matrix rank,

¬B(ρ)⟹¬A(ϑ(μ)ρ).\neg\mathcal B(\rho)\Longrightarrow\neg\mathcal A(\vartheta(\mu)\rho).¬B(ρ)⟹¬A(ϑ(μ)ρ).

This is the mixed scalar/full-block result; the existing Open scalar-only Matrix Cube Theorem is not re-posed.

Formalization Note The universal function is chosen before all dimensions and data. The scalar and full block counts may separately be zero. The full-block factors may vanish in this theorem. The finite certificate (9.1.3) is not substituted for the independently defined predicate B\mathcal BB.

Preamble
import Mathlib

open Matrix
open scoped Matrix.Norms.L2Operator
Formal statement
namespace RobustOpt2009.SDPApproximation

/-- Theorem 7.1.3: one universal nondecreasing function, with the two
predicates expanded independently inside the statement. -/
theorem theorem_7_1_3 :
    ∃ θ : ℕ → ℝ, 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
      (b → a ρ) ∧ (s + f = 1 → (b ↔ a ρ)) ∧
      (∀ μ : ℕ, 2 ≤ μ → (∀ i, (B i).rank ≤ μ) → ¬ b → ¬ a (θ μ * ρ)) := by sorry

end RobustOpt2009.SDPApproximation
Source
Ben-Tal, El Ghaoui and Nemirovski, Robust Optimization, Princeton University Press, 2009, https://doi.org/10.1515/9781400831050, Theorem 7.1.3, printed p. 183 (PDF p. 209)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

The statement asserts that there is a single function θ:N→R\theta:\mathbb{N}\to\mathbb{R}θ:N→R, chosen before any data, with the following properties.

Properties of θ\thetaθ.

  • θ\thetaθ is nondecreasing.
  • θ(2)=π/2\theta(2) = \pi/2θ(2)=π/2 and θ(4)=2\theta(4) = 2θ(4)=2.
  • θ(μ)≤πμ/2\theta(\mu) \le \pi\sqrt{\mu/2}θ(μ)≤πμ/2​ for every integer μ≥2\mu \ge 2μ≥2.

The data. The remaining claims hold for every choice of:

  • natural numbers m≥1m\ge1m≥1, s≥0s\ge0s≥0 and f≥0f\ge0f≥0;
  • positive integers pj,qj≥1p_j, q_j \ge 1pj​,qj​≥1 for j=1,…,fj=1,\dots,fj=1,…,f;
  • a symmetric real m×mm\times mm×m matrix B0B_0B0​ and symmetric real m×mm\times mm×m matrices B1,…,BsB_1,\dots,B_sB1​,…,Bs​;
  • real pj×mp_j\times mpj​×m matrices LjL_jLj​ and real qj×mq_j\times mqj​×m matrices RjR_jRj​;
  • a real number ρ≥0\rho \ge 0ρ≥0.

The notation is as follows. A⪰0A\succeq0A⪰0 means AAA is symmetric and x⊤Ax≥0x^\top A x\ge0x⊤Ax≥0 for all real xxx. The norm ∥Z∥\|Z\|∥Z∥ of a matrix is its spectral (Euclidean operator) norm.

Predicate a(r)a(r)a(r). For a real number rrr, a(r)a(r)a(r) says the following. For every z∈Rsz\in\mathbb{R}^sz∈Rs and every family of real pj×qjp_j\times q_jpj​×qj​ matrices ZjZ_jZj​ with ∣zi∣≤r|z_i|\le r∣zi​∣≤r for all iii and ∥Zj∥≤r\|Z_j\|\le r∥Zj​∥≤r for all jjj,

B0+∑i=1sziBi+∑j=1f(Lj⊤ZjRj+Rj⊤Zj⊤Lj)⪰0.B_0 + \sum_{i=1}^s z_i B_i + \sum_{j=1}^f \left(L_j^\top Z_j R_j + R_j^\top Z_j^\top L_j\right) \succeq 0 .B0​+i=1∑s​zi​Bi​+j=1∑f​(Lj⊤​Zj​Rj​+Rj⊤​Zj⊤​Lj​)⪰0.

Proposition bbb. This proposition is evaluated at the given ρ\rhoρ. It says there exist symmetric real m×mm\times mm×m matrices U1,…,UsU_1,\dots,U_sU1​,…,Us​ and V1,…,VfV_1,\dots,V_fV1​,…,Vf​ such that:

  • Ui−Bi⪰0U_i - B_i\succeq0Ui​−Bi​⪰0 and Ui+Bi⪰0U_i + B_i \succeq 0Ui​+Bi​⪰0 for every iii;
  • for every jjj and every real pj×qjp_j\times q_jpj​×qj​ matrix ZZZ with ∥Z∥≤1\|Z\|\le1∥Z∥≤1, we have Vj−(Lj⊤ZRj+Rj⊤Z⊤Lj)⪰0V_j - (L_j^\top Z R_j + R_j^\top Z^\top L_j)\succeq0Vj​−(Lj⊤​ZRj​+Rj⊤​Z⊤Lj​)⪰0;
  • B0−ρ∑iUi−ρ∑jVj⪰0B_0 - \rho\sum_i U_i - \rho\sum_j V_j \succeq 0B0​−ρ∑i​Ui​−ρ∑j​Vj​⪰0.

Conclusions. The theorem asserts all three of the following.

  1. b⇒a(ρ)b \Rightarrow a(\rho)b⇒a(ρ).

  2. If s+f=1s+f = 1s+f=1, then b  ⟺  a(ρ)b \iff a(\rho)b⟺a(ρ).

  3. For every integer μ≥2\mu\ge2μ≥2: if rank⁡Bi≤μ\operatorname{rank} B_i \le \murankBi​≤μ for all i=1,…,si = 1,\dots,si=1,…,s and bbb fails, then a(θ(μ) ρ)a(\theta(\mu)\,\rho)a(θ(μ)ρ) fails.

    The rank hypothesis concerns only the scalar matrices BiB_iBi​. Nothing is assumed about the ranks of LjL_jLj​ or RjR_jRj​. The negated predicate is evaluated at the scaled radius θ(μ)ρ\theta(\mu)\rhoθ(μ)ρ, while bbb uses ρ\rhoρ.

Degenerate cases.

  • Values of θ\thetaθ. θ(0)\theta(0)θ(0) and θ(1)\theta(1)θ(1) are constrained only by monotonicity: θ(0)≤θ(1)≤π/2\theta(0)\le\theta(1)\le\pi/2θ(0)≤θ(1)≤π/2. Also θ(3)∈[π/2, 2]\theta(3)\in[\pi/2,\,2]θ(3)∈[π/2,2]. For μ≥2\mu\ge2μ≥2, monotonicity gives θ(μ)≥π/2>0\theta(\mu)\ge\pi/2>0θ(μ)≥π/2>0, so the radius θ(μ)ρ\theta(\mu)\rhoθ(μ)ρ is nonnegative.
  • s=f=0s=f=0s=f=0. Clause 2 is vacuous, and the rank hypothesis in clause 3 is empty. Both a(r)a(r)a(r) and bbb reduce to B0⪰0B_0\succeq0B0​⪰0.
  • ρ=0\rho = 0ρ=0. a(0)a(0)a(0) and a(θ(μ)⋅0)a(\theta(\mu)\cdot 0)a(θ(μ)⋅0) only test z=0z=0z=0 and Zj=0Z_j=0Zj​=0, so both reduce to B0⪰0B_0\succeq0B0​⪰0. In bbb, the final condition reduces to B0⪰0B_0\succeq0B0​⪰0. The remaining conditions on UiU_iUi​ and VjV_jVj​ are then separate existence requirements.
  • Zero factors. LjL_jLj​ and RjR_jRj​ may be zero. The hypothesis m≥1m\ge1m≥1 rules out empty m×mm\times mm×m matrices.
  • s+f≠1s+f\ne1s+f=1. Clause 2 gives nothing.
Human review
  • Endorsed by Community (Bot) · Oct 22, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me