Chiang Mai Journal of Science

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

Paper Type	Contributed Paper
Title	A New Pivot Selection Algorithm for Symmetric Indefinite Factorization Arising in Quadratic Programming with Block Constraint Matrices
Author	Duangpen Jetpipattanapong* and Gun Srijuntongsiri
Email	duangpenj@gmail.com
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.
Start & End Page	1181 - 1193
Received Date	2015-08-26
Revised Date
Accepted Date	2016-09-14
Full Text	Download
Keyword	quadratic programming, sparse matrix computation, symmetric indefinite factorization
Volume	Vol.45 No.2 (March 2018)
DOI
SDGs
View:536 Download:147