Lemma 3.4.1 — minimization of a positive semidefinite quadratic form
ProvedModernConvex.Truss.quadratic_form_minimumLet be a symmetric positive semidefinite real matrix, , and consider the quadratic form
Then:
- is bounded below on if and only if it attains its minimum;
- attains its minimum if and only if the equation is solvable, and in that case the set of minimizers of is exactly the set of solutions of ;
- the minimum value of , if it exists, equals , where is any solution of .
This is the linear-algebra fact behind the variational description of the compliance of a truss (Proposition 3.4.4).
Formalization Note "Symmetric positive semidefinite" is Matrix.PosSemidef (which includes symmetry). "Bounded below" is BddBelow of the range of ; "attains its minimum" is the existence of with for all . Item 3 is stated as: for every minimizer and every solution of , .
import Mathlib open Matrix
namespace ModernConvex.Truss
/-- Ben-Tal–Nemirovski, Lemma 3.4.1, p. 122. Let `𝒜(v) = ½ vᵀAv − bᵀv` be a quadratic form on `ℝᵐ`
with symmetric positive semidefinite matrix `A`. Then
(i) `𝒜` is bounded below iff it attains its minimum;
(ii) `𝒜` attains its minimum iff `Av = b` (∗) is solvable, in which case the set of minimizers of
`𝒜` is exactly the set of solutions of (∗);
(iii) the minimum value, if it exists, equals `−½ bᵀv` for any solution `v` of (∗). -/
theorem quadratic_form_minimum {m : ℕ} (A : Matrix (Fin m) (Fin m) ℝ) (hA : A.PosSemidef)
(b : Fin m → ℝ) :
let Q : (Fin m → ℝ) → ℝ := fun v => (1 / 2 : ℝ) * (v ⬝ᵥ (A *ᵥ v)) - b ⬝ᵥ v
-- (i)
(BddBelow (Set.range Q) ↔ ∃ v₀, ∀ v, Q v₀ ≤ Q v) ∧
-- (ii)
((∃ v₀, ∀ v, Q v₀ ≤ Q v) ↔ ∃ v, A *ᵥ v = b) ∧
((∃ v, A *ᵥ v = b) → ∀ v₀, (∀ v, Q v₀ ≤ Q v) ↔ A *ᵥ v₀ = b) ∧
-- (iii)
(∀ v₀, (∀ v, Q v₀ ≤ Q v) → ∀ v, A *ᵥ v = b → Q v₀ = -((1 / 2 : ℝ) * (b ⬝ᵥ v))) := by sorry
end ModernConvex.Truss
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let , let be a real matrix that is positive semidefinite (symmetric, with for all ), and let . Define
Claims. The statement asserts all four of the following.
- The set of values is bounded below if and only if there is a with for all (a global minimizer).
- A global minimizer exists if and only if the equation has a solution.
- If has a solution, then for every : is a global minimizer of if and only if .
- For every global minimizer and every solution of ,
Degenerate cases.
- If , then is a single point, , holds trivially, and every claim is trivially true.
- If , then and all four claims concern whether .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.