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.