Numerically stable LDL^T factorizations in interior point methods for convex quadratic programming

Abstract

Fletcher & Powell (1974, Math. Comput., 28, 1067-1087) proposed a numerically stable method for updating the LDLT factorization of a symmetric positive-definite matrix when a symmetric low-rank term is added to it. In Goldfarb & Scheinberg (2004, Math. Program., 99, 1-34) we proposed a product-form version of the method of Fletcher and Powell for use in interior point methods for linear programming and studied its numerical stability. In this paper we extend these results to convex quadratic programming where the Hessian matrix of the objective function is, or can be approximated by, a diagonal matrix plus a matrix of low rank. Our new results are based on showing that the elements of the unit lower triangular matrix in the LDLT factorizations that arise in this context are uniformly bounded as the duality gap is driven to zero. Practicable versions of our approach are described for structured quadratic programs that arise in support vector machines and portfolio optimization.