Two quadratic functions can be compared losslessly. The S-procedure says that, when the constraint is strictly feasible, the implication
holds if and only if a single nonnegative multiplier certifies it as a matrix inequality, for some . It is a cornerstone of control theory, trust-region methods and robust optimization, and a rare case in which a nonconvex problem has zero duality gap. The route runs through the theory this mission builds from Boyd & Vandenberghe §5.8–5.9 and Appendix B: strong alternatives for convex inequality systems, cone-program strong duality under a generalized Slater condition, semidefinite programming duality, the LMI theorems of alternatives, and the hidden convexity of the joint range of two quadratic forms.
theorem ConvexOptimization.s_procedure {nn : ℕ}
(F₁ F₂ : Matrix (Fin nn) (Fin nn) ℝ) (hF₁ : F₁.IsSymm) (hF₂ : F₂.IsSymm)
(g₁ g₂ : Fin nn → ℝ) (h₁ h₂ : ℝ)
(xh : Fin nn → ℝ) (hxh : quadForm F₁ g₁ h₁ xh < 0) :
(∀ x, quadForm F₁ g₁ h₁ x ≤ 0 → quadForm F₂ g₂ h₂ x ≤ 0) ↔
∃ lam : ℝ, 0 ≤ lam ∧
(lam • symQuadBlock F₁ g₁ h₁ - symQuadBlock F₂ g₂ h₂).PosSemidef := by
sorry
The S-procedure — the goal of this mission: one quadratic inequality implies another exactly when a single nonnegative multiplier certifies it.
Let be symmetric real matrices, , , and set
with associated block matrices . Assume the strict-feasibility (Slater) condition: some satisfies . Then
The right-hand side is a linear matrix inequality in , so an implication between two quadratic inequalities — a statement quantified over all of , and in general nonconvex — becomes a small semidefinite feasibility problem. The direction is elementary; it is the converse, losslessness, that is the theorem, and it holds only for a pair of quadratics: with two or more constraints the analogous procedure is merely sufficient.
Known as the S-procedure in control, where it certifies stability and dissipativity of systems with quadratic constraints, the result is also the exactness statement behind trust-region subproblems and behind robust optimization with ellipsoidal uncertainty — one of the very few nonconvex problems with a provably zero duality gap.
Formalization Note The quadratics and their block matrices are the mission's quadForm and symQuadBlock; the certificate is PosSemidef of lam • symQuadBlock F₁ g₁ h₁ - symQuadBlock F₂ g₂ h₂. Strict feasibility is a hypothesis of the whole iff, matching the book. Source: B&V §B.2, p. 655, proved in §B.4, pp. 657–658.
No open leaves. Every sub-goal is proved or awaiting decomposition.