Proof of Theorem 4.1, p. 56 — the KKT matrix (4.5) is nonsingular
ProvedRobinsonSR.NLP.matrix_4_5_nonsingularkkt-matrixlinear-independencenonsingular-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1second-order-sufficiency
Let be an , a and an real matrix (playing , and ). Assume
- the strong second-order sufficient condition: for every nonzero with and ;
- the rows of and are jointly linearly independent: implies and .
Then the matrix
is nonsingular.
This is the first step of the proof of Theorem 4.1: it makes the Schur complement (4.6) well defined.
Formalization Note The index sets are arbitrary finite types, so the statement covers the degenerate cases , or . The page applies the full linear independence assumption (b), which also involves ; only its consequence for and is used, and that is what is assumed here. need not be symmetric.
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 (on the null
space of `H` and `G⁺`) and linear independence of the rows of `H` and `G⁺`, the matrix (4.5)
`[ℒ″ Hᵀ G⁺ᵀ; −H 0 0; −G⁺ 0 0]` is nonsingular. -/
theorem matrix_4_5_nonsingular {ιn ιq ιr : Type*} [Fintype ιn] [Fintype ιq] [Fintype ιr]
[DecidableEq ιn] [DecidableEq ιq] [DecidableEq ιr]
(Q : Matrix ιn ιn ℝ) (H : Matrix ιq ιn ℝ) (Gp : Matrix ιr ιn ℝ)
(hSSOSC : ∀ y : ιn → ℝ, y ≠ 0 → Gp *ᵥ y = 0 → H *ᵥ y = 0 → 0 < y ⬝ᵥ (Q *ᵥ y))
(hLI : ∀ (b : ιq → ℝ) (c : ιr → ℝ), Hᵀ *ᵥ b + Gpᵀ *ᵥ c = 0 → b = 0 ∧ c = 0) :
(kktMatrix Q H Gp).det ≠ 0 := by sorry
end RobinsonSR.NLP
Source
Robinson, Strongly regular generalized equations, Math. Oper. Res. 5 (1980), p. 56, proof of Theorem 4.1, (4.5), (4.7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.