Theorem 5.2 (corrected) โ the SDP (40) upper-bounds the linear-fractional worst-case residual, exactly when ๐ = โ^{NรN}
ProvedRobustLS.LinFrac.sdp_upper_bound_theorem52Consider the linear-fractional robust least-squares model of ยง5.2 with : a subspace , data , , , , , , the perturbed data , , and the worst-case residual
Let , be the symmetric and skew-symmetric matrices commuting with every element of , and the matrix (38)โ(39). Consider the SDP
Then, for every and :
- (Upper bound.) If is feasible for (40), then .
- (Exactness for full perturbations.) If and , then there is such that is feasible for (40).
Hence the value of (40) is an upper bound on , and it equals when (with (40) infeasible exactly when ).
Computing 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 , and (38); the constraints (from Lemma 2.3's hypotheses) and " skew-symmetric for every " (the identity 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 , . The statement is written through 's feasibility rather than an infimum over the open LMI set: part 1 says every feasible exceeds , part 2 that every is feasible. The printed last sentence, "If 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. "" is the predicate ResidualBelow.
import Mathlib import Definitions.Def_RobustLS_LinFrac_Core open Matrix
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.