A New Pivot Selection Algorithm for Symmetric Indefinite Factorization Arising in Quadratic Programming with Block Constraint Matrices
For practitioners solving quadratic programs with block-diagonal constraints, this algorithm improves factorization sparsity and stability.
The paper proposes a new pivot selection algorithm for symmetric indefinite factorization of KKT matrices arising in equality-constrained quadratic programming with block-diagonal constraint matrices. The algorithm produces no fill-ins and yields sparser factors compared to MA57.
Quadratic programmingis a class of constrained optimization problem with quadratic objective functions and linear constraints. It has applications in many areas and is also used to solve nonlinear optimization problems. This article focuses on the equality constrained quadratic programs whose constraint matrices are block diagonal. Using the direct solution method, we propose a new pivot selection algorithm for the factorization of the Karush-Kuhn-Tucker(KKT) matrix for this problem that maintains the sparsity and stability of the problem. Our experiments show that our pivot selection algorithm appears to produce no fill-ins in the factorizationof such matrices. In addition, we compare our method with MA57 and find that the factors produced by our algorithm are sparser.