Proof of Theorem 4.1, p. 56 — under (a′) and (b) the Schur complement (4.6) is positive definite
ProvedRobinsonSR.NLP.schur_posdeflinear-independencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1positive-definiteschur-complementsecond-order-sufficiency
Let (, symmetric), (), () and () be real matrices. Assume
- the strong second-order sufficient condition: for every nonzero with and ;
- linear independence (b): the rows of , and are jointly linearly independent, i.e. implies , , .
Then the Schur complement
is positive definite: for every .
Together with the two previous steps this shows that is a P-matrix, the condition of the §4 criterion.
Formalization Note The nonsingularity of (4.5) is not assumed: it follows from the two hypotheses.
Preamble
import Mathlib import Definitions.Def_RobinsonSR_NLP_Setting open scoped RealInnerProductSpace Matrix
Formal statement
namespace RobinsonSR.NLP
/-- Proof of Theorem 4.1, p. 56: under the strong second-order sufficient condition, symmetry of
`ℒ″` and linear independence of the rows of `G⁺`, `G⁰` and `H`, the Schur complement (4.6) is
positive definite. -/
theorem schur_posdef {ιn ιq ιr ιs : Type*} [Fintype ιn] [Fintype ιq] [Fintype ιr]
[Fintype ιs] [DecidableEq ιn] [DecidableEq ιq] [DecidableEq ιr]
(Q : Matrix ιn ιn ℝ) (H : Matrix ιq ιn ℝ) (Gp : Matrix ιr ιn ℝ) (G0 : Matrix ιs ιn ℝ)
(hQ : Q.IsSymm)
(hSSOSC : ∀ y : ιn → ℝ, y ≠ 0 → Gp *ᵥ y = 0 → H *ᵥ y = 0 → 0 < y ⬝ᵥ (Q *ᵥ y))
(hLI : ∀ (b : ιq → ℝ) (c : ιr → ℝ) (d : ιs → ℝ),
Hᵀ *ᵥ b + Gpᵀ *ᵥ c + G0ᵀ *ᵥ d = 0 → b = 0 ∧ c = 0 ∧ d = 0) :
RobinsonSR.Schur.PosDefNS (schurS Q H Gp G0) := by sorry
end RobinsonSR.NLP
Source
Robinson, Strongly regular generalized equations, Math. Oper. Res. 5 (1980), p. 56, proof of Theorem 4.1, (4.6), (4.8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.