A New Pivot Selection Algorithm for Symmetric Indefinite Factorization Arising in Quadratic Programming with Block Constraint Matrices

Abstract

Quadratic programming is 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. The Karush-Kuhn-Tucker (KKT) matrices for these programs are typically sparse and have certain specific structures that can be exploited to efficiently solve them. Using the direct solution method, we propose a new pivot selection algorithm for the factorization of the 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 factorization of such matrices. In addition, we compare our method with MA57 and bounded Bunch-Kaufman (BBK) and find that the factors produced by our algorithm are sparser in almost all of the test problems. Consequently, solving the system using our factors is much faster than using the factors produced by the other methods. In particular, our method works especially well when the constraint matrices are very sparse. Lastly, the method is also efficient when applied to problems with sparse Hessian matrices as well as problems whose constraint matrices contain unequal-sized blocks.