Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 9.1.2 — Rank-sensitive approximation of structured robust LMIs

Proved
RobustOpt2009.SDPApproximation.theorem_9_1_2

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

matrix-cuberobust-optimizationsemidefinite-programming

Consider the real uncertain LMI of Definition 9.1.1, with positive matrix and full-block dimensions, s+f≥1s+f\ge1s+f≥1 perturbation blocks, and radius ρ>0\rho>0ρ>0. Its nominal matrix An(y)A^n(y)An(y), scalar coefficient matrices Ai(y)A_i(y)Ai​(y) and full-block factors Lj(y)L_j(y)Lj​(y) are affine in y∈Rny\in\mathbb R^ny∈Rn; the nominal and scalar matrices are symmetric and each fixed RjR_jRj​ is nonzero. Robust feasibility Ay(ρ)\mathcal A_y(\rho)Ay​(ρ) means

An(y)+∑iziAi(y)+∑j[Lj(y)TZjRj+RjTZjTLj(y)]⪰0A^n(y)+\sum_i z_iA_i(y)+\sum_j[L_j(y)^TZ_jR_j+R_j^TZ_j^TL_j(y)]\succeq0An(y)+i∑​zi​Ai​(y)+j∑​[Lj​(y)TZj​Rj​+RjT​ZjT​Lj​(y)]⪰0

for all ∣zi∣≤ρ|z_i|\le\rho∣zi​∣≤ρ and ∥Zj∥2,2≤ρ\|Z_j\|_{2,2}\le\rho∥Zj​∥2,2​≤ρ. Let Cy(ρ)\mathcal C_y(\rho)Cy​(ρ) be feasibility in symmetric matrices Ui,VjU_i,V_jUi​,Vj​ and real scalars λj\lambda_jλj​ of

Ui⪰±Ai(y),[λjIpjLj(y)Lj(y)TVj−λjRjTRj]⪰0,An(y)−ρ(∑iUi+∑jVj)⪰0.U_i\succeq\pm A_i(y),\quad \begin{bmatrix}\lambda_jI_{p_j}&L_j(y)\\L_j(y)^T&V_j-\lambda_jR_j^TR_j\end{bmatrix}\succeq0,\quad A^n(y)-\rho\left(\sum_iU_i+\sum_jV_j\right)\succeq0.Ui​⪰±Ai​(y),[λj​Ipj​​Lj​(y)T​Lj​(y)Vj​−λj​RjT​Rj​​]⪰0,An(y)−ρ(i∑​Ui​+j∑​Vj​)⪰0.

There is one universal function ϑ\varthetaϑ with

ϑ(2)=π/2,ϑ(4)=2,ϑ(μ)≤πμ/2(μ>2)\vartheta(2)=\pi/2,\qquad\vartheta(4)=2,\qquad\vartheta(\mu)\le\pi\sqrt{\mu/2}\quad(\mu>2)ϑ(2)=π/2,ϑ(4)=2,ϑ(μ)≤πμ/2​(μ>2)

such that for every instance and every design vector:

  1. Cy(ρ)\mathcal C_y(\rho)Cy​(ρ) implies Ay(ρ)\mathcal A_y(\rho)Ay​(ρ): the finite LMI system is safe.
  2. If μ\muμ is the least integer at least two bounding all rank⁡Ai(y′)\operatorname{rank}A_i(y')rankAi​(y′) uniformly over every i,y′i,y'i,y′, then
¬Cy(ρ)⟹¬Ay(ϑ(μ)ρ).\neg\mathcal C_y(\rho)\Longrightarrow\neg\mathcal A_y(\vartheta(\mu)\rho).¬Cy​(ρ)⟹¬Ay​(ϑ(μ)ρ).
  1. Cy(ρ)\mathcal C_y(\rho)Cy​(ρ) and Ay(ρ)\mathcal A_y(\rho)Ay​(ρ) are equivalent if there is one perturbation block, or if every block is scalar and every Ai(y′)A_i(y')Ai​(y′) has rank at most one.

The theorem gives a safe SDP approximation with rank-sensitive tightness and identifies two exact regimes.

Formalization Note Tractability is represented by the displayed finite system of affine LMIs and its existential projection onto yyy, with fixed ρ\rhoρ; no algorithmic complexity model is asserted. Scalar and full indices are re-enumerated separately. The least rank bound quantifies over all design vectors, and the same existential ϑ\varthetaϑ precedes every instance parameter. The main theorem's printed bound πμ/2\pi\sqrt{\mu/2}πμ/2​ is retained.

Preamble
import Mathlib

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

/-- Theorem 9.1.2. All data and predicates are expanded here so that the
statement is independently readable without consulting an imported definition. -/
theorem theorem_9_1_2 :
    ∃ θ : ℕ → ℝ, θ 2 = Real.pi / 2 ∧ θ 4 = 2 ∧
      (∀ μ : ℕ, 2 < μ → θ μ ≤ Real.pi * Real.sqrt ((μ : ℝ) / 2)) ∧
      ∀ (n m s f : ℕ), 0 < m → 0 < s + f →
      ∀ (p q : Fin f → ℕ), (∀ j, 0 < p j) → (∀ j, 0 < q j) →
      ∀ (A₀ : (Fin n → ℝ) →ᵃ[ℝ] Matrix (Fin m) (Fin m) ℝ)
        (A : Fin s → ((Fin n → ℝ) →ᵃ[ℝ] Matrix (Fin m) (Fin m) ℝ))
        (L : (j : Fin f) → ((Fin n → ℝ) →ᵃ[ℝ] Matrix (Fin (p j)) (Fin m) ℝ))
        (R : (j : Fin f) → Matrix (Fin (q j)) (Fin m) ℝ),
      (∀ y, (A₀ y).IsHermitian) → (∀ i y, (A i y).IsHermitian) →
      (∀ j, R j ≠ 0) → ∀ (ρ : ℝ), 0 < ρ → ∀ y : Fin n → ℝ,
      let RC : ℝ → 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) →
          (A₀ y + (∑ i, z i • A i y) +
            ∑ j, ((L j y)ᵀ * Z j * R j + (R j)ᵀ * (Z j)ᵀ * L j y)).PosSemidef
      let SDP : Prop :=
        ∃ (U : Fin s → Matrix (Fin m) (Fin m) ℝ)
          (V : Fin f → Matrix (Fin m) (Fin m) ℝ) (lam : Fin f → ℝ),
          (∀ i, (U i).IsHermitian) ∧ (∀ j, (V j).IsHermitian) ∧
          (∀ i, (U i - A i y).PosSemidef ∧ (U i + A i y).PosSemidef) ∧
          (∀ j, (fromBlocks (lam j • (1 : Matrix (Fin (p j)) (Fin (p j)) ℝ))
            (L j y) (L j y)ᵀ (V j - lam j • ((R j)ᵀ * R j))).PosSemidef) ∧
          (A₀ y - ρ • ((∑ i, U i) + ∑ j, V j)).PosSemidef
      (SDP → RC ρ) ∧
      (∀ μ : ℕ, IsLeast {k : ℕ | 2 ≤ k ∧ ∀ i y', (A i y').rank ≤ k} μ →
        ¬ SDP → ¬ RC (θ μ * ρ)) ∧
      ((s + f = 1 ∨ (f = 0 ∧ ∀ i y', (A i y').rank ≤ 1)) → (SDP ↔ RC ρ)) := 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 9.1.2, printed pp. 225–226 (PDF pp. 251–252), (9.1.3)–(9.1.4)
Read-back

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

Setting. The statement asserts that there is a single function θ:N→R\theta:\mathbb{N}\to\mathbb{R}θ:N→R with three properties:

  • θ(2)=π/2\theta(2)=\pi/2θ(2)=π/2;
  • θ(4)=2\theta(4)=2θ(4)=2;
  • θ(μ)≤πμ/2\theta(\mu)\le \pi\sqrt{\mu/2}θ(μ)≤πμ/2​ for every natural number μ>2\mu>2μ>2.

No other constraint is placed on θ\thetaθ. Its values at 000 and 111 are free. For μ>2\mu>2μ>2 the values are bounded above only, with no lower bound, so they may be zero or negative. The function θ\thetaθ is chosen once, before any of the data below, so the same θ\thetaθ must work for all of it.

Data and hypotheses. For this fixed θ\thetaθ, the statement then quantifies over the following:

  • natural numbers n,m,s,fn,m,s,fn,m,s,f with m>0m>0m>0 and s+f>0s+f>0s+f>0;
  • positive natural numbers pjp_jpj​ and qjq_jqj​ for each j∈{0,…,f−1}j\in\{0,\dots,f-1\}j∈{0,…,f−1};
  • an affine map A0:Rn→Rm×mA_0:\mathbb{R}^n\to\mathbb{R}^{m\times m}A0​:Rn→Rm×m;
  • affine maps Ai:Rn→Rm×mA_i:\mathbb{R}^n\to\mathbb{R}^{m\times m}Ai​:Rn→Rm×m for i∈{0,…,s−1}i\in\{0,\dots,s-1\}i∈{0,…,s−1};
  • affine maps Lj:Rn→Rpj×mL_j:\mathbb{R}^n\to\mathbb{R}^{p_j\times m}Lj​:Rn→Rpj​×m for j<fj<fj<f;
  • fixed matrices Rj∈Rqj×mR_j\in\mathbb{R}^{q_j\times m}Rj​∈Rqj​×m for j<fj<fj<f.

These must satisfy:

  • A0(y)A_0(y)A0​(y) is symmetric for every yyy;
  • each Ai(y)A_i(y)Ai​(y) is symmetric for every iii and yyy;
  • every RjR_jRj​ is nonzero.

Finally it quantifies over a real ρ>0\rho>0ρ>0 and a point y∈Rny\in\mathbb{R}^ny∈Rn. "Positive semidefinite" (⪰0\succeq 0⪰0) below means: symmetric, and x⊤Mx≥0x^\top M x\ge 0x⊤Mx≥0 for all real vectors xxx.

Robust condition RC(r)\mathrm{RC}(r)RC(r). For a real rrr, RC(r)\mathrm{RC}(r)RC(r) means the following. For every z∈Rsz\in\mathbb{R}^sz∈Rs with ∣zi∣≤r|z_i|\le r∣zi​∣≤r for all iii, and every family of matrices Zj∈Rpj×qjZ_j\in\mathbb{R}^{p_j\times q_j}Zj​∈Rpj​×qj​ with ∥Zj∥≤r\|Z_j\|\le r∥Zj​∥≤r for all jjj, we have

A0(y)+∑i<sziAi(y)+∑j<f(Lj(y)⊤ZjRj+Rj⊤Zj⊤Lj(y))⪰0.A_0(y)+\sum_{i<s} z_i A_i(y)+\sum_{j<f}\Big(L_j(y)^\top Z_j R_j + R_j^\top Z_j^\top L_j(y)\Big)\succeq 0 .A0​(y)+i<s∑​zi​Ai​(y)+j<f∑​(Lj​(y)⊤Zj​Rj​+Rj⊤​Zj⊤​Lj​(y))⪰0.

Here ∥Zj∥\|Z_j\|∥Zj​∥ is the spectral (largest-singular-value, ℓ2\ell_2ℓ2​-operator) norm.

SDP condition. SDP\mathrm{SDP}SDP means that there exist symmetric Ui∈Rm×mU_i\in\mathbb{R}^{m\times m}Ui​∈Rm×m (i<si<si<s), symmetric Vj∈Rm×mV_j\in\mathbb{R}^{m\times m}Vj​∈Rm×m (j<fj<fj<f) and reals λj\lambda_jλj​ (j<fj<fj<f) such that:

  • Ui−Ai(y)⪰0U_i-A_i(y)\succeq 0Ui​−Ai​(y)⪰0 and Ui+Ai(y)⪰0U_i+A_i(y)\succeq 0Ui​+Ai​(y)⪰0 for every iii;
  • for every jjj, the (pj+m)×(pj+m)(p_j+m)\times(p_j+m)(pj​+m)×(pj​+m) block matrix
(λjIpjLj(y)Lj(y)⊤Vj−λjRj⊤Rj)⪰0;\begin{pmatrix}\lambda_j I_{p_j} & L_j(y)\\ L_j(y)^\top & V_j-\lambda_j R_j^\top R_j\end{pmatrix}\succeq 0;(λj​Ipj​​Lj​(y)⊤​Lj​(y)Vj​−λj​Rj⊤​Rj​​)⪰0;
  • A0(y)−ρ(∑iUi+∑jVj)⪰0A_0(y)-\rho\Big(\sum_i U_i+\sum_j V_j\Big)\succeq 0A0​(y)−ρ(∑i​Ui​+∑j​Vj​)⪰0.

The λj\lambda_jλj​ are not explicitly required to be nonnegative.

Conclusions. Under the hypotheses above, the statement asserts three things.

  1. SDP⇒RC(ρ)\mathrm{SDP}\Rightarrow\mathrm{RC}(\rho)SDP⇒RC(ρ).

  2. Let μ\muμ be a natural number that is the least element of the set

{k∈N:k≥2 and rank⁡Ai(y′)≤k for all i<s and all y′∈Rn}.\{k\in\mathbb{N} : k\ge 2 \text{ and } \operatorname{rank}A_i(y')\le k \text{ for all } i<s \text{ and all } y'\in\mathbb{R}^n\}.{k∈N:k≥2 and rankAi​(y′)≤k for all i<s and all y′∈Rn}.

For any such μ\muμ:

¬SDP ⇒ ¬RC(θ(μ)ρ).\neg\mathrm{SDP}\ \Rightarrow\ \neg\mathrm{RC}(\theta(\mu)\rho).¬SDP ⇒ ¬RC(θ(μ)ρ).

The rank bound ranges over all points y′y'y′, not only the fixed yyy. The set is never empty (it contains max⁡(2,m)\max(2,m)max(2,m)), so μ\muμ always exists and equals max⁡{2, sup⁡i,y′rank⁡Ai(y′)}\max\{2,\ \sup_{i,y'}\operatorname{rank}A_i(y')\}max{2, supi,y′​rankAi​(y′)}.

  1. Suppose either s+f=1s+f=1s+f=1, or f=0f=0f=0 and rank⁡Ai(y′)≤1\operatorname{rank}A_i(y')\le 1rankAi​(y′)≤1 for all iii and all y′y'y′. Then
SDP  ⟺  RC(ρ).\mathrm{SDP}\iff\mathrm{RC}(\rho).SDP⟺RC(ρ).

Degenerate cases.

  • n=0n=0n=0: R0\mathbb{R}^0R0 is a single point, so every affine map is constant.
  • s=0s=0s=0 (hence f≥1f\ge 1f≥1):
    • there is no zzz and no UiU_iUi​, and all sums over iii are zero;
    • the rank set is {k:k≥2}\{k:k\ge 2\}{k:k≥2}, so μ=2\mu=2μ=2 and θ(μ)=π/2\theta(\mu)=\pi/2θ(μ)=π/2;
    • when in addition f=1f=1f=1, part 3 gives exact equivalence.
  • f=0f=0f=0 (hence s≥1s\ge 1s≥1):
    • there are no ZjZ_jZj​, VjV_jVj​ or λj\lambda_jλj​, and RC\mathrm{RC}RC involves only the ziz_izi​;
    • part 3 applies when s=1s=1s=1, or when every Ai(y′)A_i(y')Ai​(y′) has rank at most 111 (including the zero matrix, which has rank 000).
  • The case s=f=0s=f=0s=f=0 is excluded by the hypothesis.
  • Negative radius r<0r<0r<0: no zzz with ∣zi∣≤r|z_i|\le r∣zi​∣≤r exists when s≥1s\ge 1s≥1, and no ZjZ_jZj​ with ∥Zj∥≤r\|Z_j\|\le r∥Zj​∥≤r exists when f≥1f\ge 1f≥1. Since s+f>0s+f>0s+f>0, RC(r)\mathrm{RC}(r)RC(r) is then vacuously true.
  • Effect of a non-positive θ(μ)\theta(\mu)θ(μ): for μ>2\mu>2μ>2, θ(μ)\theta(\mu)θ(μ) is only bounded above. If the chosen θ\thetaθ had θ(μ)<0\theta(\mu)<0θ(μ)<0, then ¬RC(θ(μ)ρ)\neg\mathrm{RC}(\theta(\mu)\rho)¬RC(θ(μ)ρ) would be false, and part 2 would force SDP\mathrm{SDP}SDP to hold for all data with that μ\muμ. The statement only asserts that some θ\thetaθ meeting all the listed constraints exists.
  • No junk values: no division, natural-number subtraction, integral or supremum appears. μ/2\sqrt{\mu/2}μ/2​ is evaluated only for μ>2\mu>2μ>2, where its argument is positive.
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