Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
โ† Formalpedia

Theorem 5.2 (corrected) โ€” the SDP (40) upper-bounds the linear-fractional worst-case residual, exactly when ๐’Ÿ = โ„^{Nร—N}

Proved
RobustLS.LinFrac.sdp_upper_bound_theorem52

by mikedeng1 ยท Sep 27, 2026 ยท Mathlib 0df444a (Lean v4.33.1)

linear-fractional-uncertaintyp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-least-squaress-proceduresemidefinite-programming

Consider the linear-fractional robust least-squares model of ยง5.2 with ฯ=1\rho = 1ฯ=1: a subspace DโІRNร—N\mathcal D \subseteq \mathbb R^{N\times N}DโІRNร—N, data AโˆˆRnร—mA \in \mathbb R^{n\times m}AโˆˆRnร—m, bโˆˆRnb \in \mathbb R^nbโˆˆRn, LโˆˆRnร—NL \in \mathbb R^{n\times N}LโˆˆRnร—N, RAโˆˆRNร—mR_A \in \mathbb R^{N\times m}RAโ€‹โˆˆRNร—m, RbโˆˆRNR_b \in \mathbb R^NRbโ€‹โˆˆRN, DโˆˆRNร—ND \in \mathbb R^{N\times N}DโˆˆRNร—N, the perturbed data A(ฮ”)=A+Lฮ”(Iโˆ’Dฮ”)โˆ’1RAA(\Delta) = A + L\Delta(I - D\Delta)^{-1}R_AA(ฮ”)=A+Lฮ”(Iโˆ’Dฮ”)โˆ’1RAโ€‹, b(ฮ”)=b+Lฮ”(Iโˆ’Dฮ”)โˆ’1Rbb(\Delta) = b + L\Delta(I - D\Delta)^{-1}R_bb(ฮ”)=b+Lฮ”(Iโˆ’Dฮ”)โˆ’1Rbโ€‹, and the worst-case residual

rD(A,b,x)=maxโกฮ”โˆˆD,ย โˆฅฮ”โˆฅโ‰ค1โˆฅA(ฮ”)xโˆ’b(ฮ”)โˆฅ(=+โˆžย ifย detโก(Iโˆ’Dฮ”)=0ย forย someย suchย ฮ”).r_{\mathcal D}(A,b,x) = \max_{\Delta \in \mathcal D,\ \|\Delta\| \le 1} \|A(\Delta)x - b(\Delta)\| \quad (\text{$= +\infty$ if $\det(I - D\Delta) = 0$ for some such $\Delta$}).rDโ€‹(A,b,x)=ฮ”โˆˆD,ย โˆฅฮ”โˆฅโ‰ค1maxโ€‹โˆฅA(ฮ”)xโˆ’b(ฮ”)โˆฅ(=+โˆžย ifย det(Iโˆ’Dฮ”)=0ย forย someย suchย ฮ”).

Let S\mathcal SS, G\mathcal GG be the symmetric and skew-symmetric matrices commuting with every element of D\mathcal DD, and F(ฮป,S,G,x)\mathcal F(\lambda, S, G, x)F(ฮป,S,G,x) the matrix (38)โ€“(39). Consider the SDP

infโกS,G,ฮปย ฮปsubjectย toSโˆˆS,ย GโˆˆG,ย Sโ‰ป0,ย Gฮ”=โˆ’(Gฮ”)Tย โˆ€ฮ”โˆˆD,ย F(ฮป,S,G,x)โ‰ป0.(40)\inf_{S, G, \lambda}\ \lambda \quad \text{subject to} \quad S \in \mathcal S,\ G \in \mathcal G,\ S \succ 0,\ G\Delta = -(G\Delta)^T \ \forall \Delta \in \mathcal D,\ \mathcal F(\lambda, S, G, x) \succ 0 . \qquad (40)S,G,ฮปinfโ€‹ย ฮปsubjectย toSโˆˆS,ย GโˆˆG,ย Sโ‰ป0,ย Gฮ”=โˆ’(Gฮ”)Tย โˆ€ฮ”โˆˆD,ย F(ฮป,S,G,x)โ‰ป0.(40)

Then, for every xโˆˆRmx \in \mathbb R^mxโˆˆRm and ฮปโˆˆR\lambda \in \mathbb RฮปโˆˆR:

  1. (Upper bound.) If (ฮป,S,G)(\lambda, S, G)(ฮป,S,G) is feasible for (40), then ฮป>rD(A,b,x)\lambda > r_{\mathcal D}(A,b,x)ฮป>rDโ€‹(A,b,x).
  2. (Exactness for full perturbations.) If D=RNร—N\mathcal D = \mathbb R^{N\times N}D=RNร—N and ฮป>rD(A,b,x)\lambda > r_{\mathcal D}(A,b,x)ฮป>rDโ€‹(A,b,x), then there is s>0s > 0s>0 such that (ฮป,sI,0)(\lambda, sI, 0)(ฮป,sI,0) is feasible for (40).

Hence the value of (40) is an upper bound on rD(A,b,x)r_{\mathcal D}(A,b,x)rDโ€‹(A,b,x), and it equals rD(A,b,x)r_{\mathcal D}(A,b,x)rDโ€‹(A,b,x) when D=RNร—N\mathcal D = \mathbb R^{N\times N}D=RNร—N (with (40) infeasible exactly when rD=+โˆžr_{\mathcal D} = +\inftyrDโ€‹=+โˆž).

Computing rDr_{\mathcal D}rDโ€‹ is NP-hard in general (Lemma 5.1); this theorem replaces it by a polynomial-time computable bound that is tight for unstructured perturbations.

Formalization Note The printed (40) has only SโˆˆSS \in \mathcal SSโˆˆS, GโˆˆGG \in \mathcal GGโˆˆG and (38); the constraints Sโ‰ป0S \succ 0Sโ‰ป0 (from Lemma 2.3's hypotheses) and "Gฮ”G\DeltaGฮ” skew-symmetric for every ฮ”โˆˆD\Delta \in \mathcal Dฮ”โˆˆD" (the identity pTGq=0p^TGq = 0pTGq=0 of Lemma 2.3's proof) are added, because without either one the upper bound is false (counterexamples in the milestone for Eqs. (38)โ€“(39)). Both hold for the exactness certificate S=sIS = sIS=sI, G=0G = 0G=0. The statement is written through ฮป\lambdaฮป's feasibility rather than an infimum over the open LMI set: part 1 says every feasible ฮป\lambdaฮป exceeds rDr_{\mathcal D}rDโ€‹, part 2 that every ฮป>rD\lambda > r_{\mathcal D}ฮป>rDโ€‹ is feasible. The printed last sentence, "If ฮ˜>0\Theta > 0ฮ˜>0 at the optimum, the upper bound is also exact", is not stated: the infimum over the strict inequality (38) is not attained, and the paper does not specify the limit it refers to. "ฮป>rD\lambda > r_{\mathcal D}ฮป>rDโ€‹" is the predicate ResidualBelow.

Preamble
import Mathlib
import Definitions.Def_RobustLS_LinFrac_Core

open Matrix
Formal statement
namespace RobustLS.LinFrac

/-- El Ghaoui & Lebret (1997), Theorem 5.2, p. 1048 (PDF p. 14), **corrected**, with `ฯ = 1`.
Printed: "When ฯ = 1, an upper bound on the worst-case residual r_๐’Ÿ(A, b, x) can be obtained by
solving the SDP (40) inf_{S,G,ฮป} ฮป subject to S โˆˆ ๐’ฎ, G โˆˆ ๐’ข, (38). The upper bound is exact when
๐’Ÿ = โ„^{Nร—N}."
(a) Upper bound: every `ฮป` feasible for (40) โ€” with the added constraints `S โ‰ป 0` and `Gฮ”`
skew-symmetric for every `ฮ” โˆˆ ๐’Ÿ` (see `residualBelow_of_certificate` for the counterexamples
to the printed version) โ€” satisfies `ฮป > r_๐’Ÿ(A, b, x)`.
(b) Exactness for `๐’Ÿ = โ„^{Nร—N}`: every `ฮป > r_๐’Ÿ(A, b, x)` is feasible for (40), already with
`S = sI` (`s > 0`) and `G = 0`, which lie in `๐’ฎ`, `๐’ข` and satisfy the added constraints.
Together, the infimum (40) equals `r_๐’Ÿ(A, b, x)` when `๐’Ÿ = โ„^{Nร—N}`, including `r_๐’Ÿ = โˆž`
exactly when (40) is infeasible. The printed clause "If ฮ˜ > 0 at the optimum, the upper bound is
also exact" is not stated (the infimum over the strict LMI (38) is not attained). -/
theorem sdp_upper_bound_theorem52 {n m N : โ„•} (๐’Ÿ : Submodule โ„ (Matrix (Fin N) (Fin N) โ„))
    (A : Matrix (Fin n) (Fin m) โ„) (b : Fin n โ†’ โ„) (L : Matrix (Fin n) (Fin N) โ„)
    (RA : Matrix (Fin N) (Fin m) โ„) (Rb : Fin N โ†’ โ„) (D : Matrix (Fin N) (Fin N) โ„)
    (x : Fin m โ†’ โ„) (lam : โ„) :
    (โˆ€ S G : Matrix (Fin N) (Fin N) โ„, S โˆˆ symCommutant ๐’Ÿ โ†’ G โˆˆ skewCommutant ๐’Ÿ โ†’
        (โˆ€ ฮ” โˆˆ ๐’Ÿ, (G * ฮ”)แต€ = -(G * ฮ”)) โ†’ S.PosDef โ†’
        (lmiF A b L RA Rb D x lam S G).PosDef โ†’ ResidualBelow ๐’Ÿ A b L RA Rb D x lam) โˆง
    (๐’Ÿ = โŠค โ†’ ResidualBelow ๐’Ÿ A b L RA Rb D x lam โ†’
        โˆƒ s : โ„, 0 < s โˆง (lmiF A b L RA Rb D x lam (s โ€ข 1) 0).PosDef) := by sorry

end RobustLS.LinFrac
Source
El Ghaoui & Lebret, Robust Solutions to Least-Squares Problems with Uncertain Data, SIAM J. Matrix Anal. Appl. 18(4):1035โ€“1064 (1997), p. 1048, Theorem 5.2, Eq. (40) (corrected; last clause not stated); proof in Appendix C, pp. 1061โ€“1062
Human review
  • Endorsed by Shuze Chen ยท Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 ยท Sep 27, 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