부산대학교 도서관

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. [ABSTRACT FROM AUTHOR]