Please use this identifier to cite or link to this item: http://cmuir.cmu.ac.th/jspui/handle/6653943832/64109
Title: A New Pivot Selection Algorithm for Symmetric Indefinite Factorization Arising in Quadratic Programming with Block Constraint Matrices
Authors: Duangpen Jetpipattanapong
Gun Srijuntongsiri
Authors: Duangpen Jetpipattanapong
Gun Srijuntongsiri
Issue Date: 2018
Publisher: Science Faculty of Chiang Mai University
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.
URI: http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=8994
http://cmuir.cmu.ac.th/jspui/handle/6653943832/64109
ISSN: 0125-2526
Appears in Collections:CMUL: Journal Articles

Files in This Item:
There are no files associated with this item.


Items in CMUIR are protected by copyright, with all rights reserved, unless otherwise indicated.