Theorem 9.1.2 — Rank-sensitive approximation of structured robust LMIs
ProvedRobustOpt2009.SDPApproximation.theorem_9_1_2Consider the real uncertain LMI of Definition 9.1.1, with positive matrix and full-block dimensions, perturbation blocks, and radius . Its nominal matrix , scalar coefficient matrices and full-block factors are affine in ; the nominal and scalar matrices are symmetric and each fixed is nonzero. Robust feasibility means
for all and . Let be feasibility in symmetric matrices and real scalars of
There is one universal function with
such that for every instance and every design vector:
- implies : the finite LMI system is safe.
- If is the least integer at least two bounding all uniformly over every , then
- and are equivalent if there is one perturbation block, or if every block is scalar and every 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 , with fixed ; 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 precedes every instance parameter. The main theorem's printed bound is retained.
import Mathlib open Matrix open scoped Matrix.Norms.L2Operator
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
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 with three properties:
- ;
- ;
- for every natural number .
No other constraint is placed on . Its values at and are free. For the values are bounded above only, with no lower bound, so they may be zero or negative. The function is chosen once, before any of the data below, so the same must work for all of it.
Data and hypotheses. For this fixed , the statement then quantifies over the following:
- natural numbers with and ;
- positive natural numbers and for each ;
- an affine map ;
- affine maps for ;
- affine maps for ;
- fixed matrices for .
These must satisfy:
- is symmetric for every ;
- each is symmetric for every and ;
- every is nonzero.
Finally it quantifies over a real and a point . "Positive semidefinite" () below means: symmetric, and for all real vectors .
Robust condition . For a real , means the following. For every with for all , and every family of matrices with for all , we have
Here is the spectral (largest-singular-value, -operator) norm.
SDP condition. means that there exist symmetric (), symmetric () and reals () such that:
- and for every ;
- for every , the block matrix
- .
The are not explicitly required to be nonnegative.
Conclusions. Under the hypotheses above, the statement asserts three things.
-
.
-
Let be a natural number that is the least element of the set
For any such :
The rank bound ranges over all points , not only the fixed . The set is never empty (it contains ), so always exists and equals .
- Suppose either , or and for all and all . Then
Degenerate cases.
- : is a single point, so every affine map is constant.
- (hence ):
- there is no and no , and all sums over are zero;
- the rank set is , so and ;
- when in addition , part 3 gives exact equivalence.
- (hence ):
- there are no , or , and involves only the ;
- part 3 applies when , or when every has rank at most (including the zero matrix, which has rank ).
- The case is excluded by the hypothesis.
- Negative radius : no with exists when , and no with exists when . Since , is then vacuously true.
- Effect of a non-positive : for , is only bounded above. If the chosen had , then would be false, and part 2 would force to hold for all data with that . The statement only asserts that some meeting all the listed constraints exists.
- No junk values: no division, natural-number subtraction, integral or supremum appears. is evaluated only for , where its argument is positive.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.