Submit your paper 
Download Template JOURNAL DETAIL
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 |
|
Citation |
Jetpipattanapong* D. and Srijuntongsiri G., A New Pivot Selection Algorithm for Symmetric Indefinite Factorization Arising in Quadratic Programming with Block Constraint Matrices, Chiang Mai Journal of Science, 2018; 45(2): 1181-1193. |
SDGs |
|
| View:676 Download:206 | |
Copyrights © Since 2021 All Rights Reserved by Chiang Mai Journal of Science