Duangpen Jetpipattanapong and Gun Srijuntongsiri

DOI: 10.14456/sjst-psu.2021.189

pp. 1449 - 1455

Abstract

Quadratic programming is an important optimization problem that has applications in many areas such as finance,
control, and management. Quadratic programs arisen in practice are often large but sparse, and they usually cannot be solved
efficiently without exploiting their structures. Since existing methods for quadratic programming deal with dense cases and do
not take advantage of any specific sparsity patterns in the problems, we propose a method to efficiently compute the search
directions for the primal-dual path-following interior-point method for the large-scale quadratic programs whose Hessian
matrices have block diagonal structures and whose constraint matrices are dense by exploiting the special sparsity pattern in the
problems to avoid unnecessary computations involving blocks of zeros. Examples of quadratic programs with such structure, to
which our method can be applied, are linear model predictive control in automatic control and portfolio optimization where
securities from different sectors are weakly correlated. The time complexity of our method is significantly smaller than that of
using a sparse linear solver. Additionally, the computational results show that our method is faster.