Positive definiteness of the ellipsoid update matrix
ProvedLinearOptimization.ellipsoid_update_matrix_posDefconvex-geometrylinear-optimization
Let , let be a symmetric positive-definite real matrix, and let be nonzero. Define
Then is positive definite.
This is the positive-definiteness component of the ellipsoid update in Theorem 8.1 and guarantees that the updated quadratic set is again an ellipsoid.
Formalization Note The matrix is represented by D * vecMulVec a a * D.
Preamble
import Definitions.Def_LinearOptimization_EllipsoidMethod open Matrix
Formal statement
theorem LinearOptimization.ellipsoid_update_matrix_posDef {n : ℕ} (hn : 2 ≤ n)
(D : Matrix (Fin n) (Fin n) ℝ) (hD : D.PosDef)
(a : Fin n → ℝ) (ha : a ≠ 0) :
(ellipsoidUpdateMatrix D a).PosDef := by
sorrySource
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 8.1, p. 366, proof in Section 8.2, pp. 366–369