On Active-Set Methods for Quadratic Problems with Positive Semidefinite Matrices
Quadratic programming problems (QP) arise in a vast variety of real-world applications in finance, engineering, operational research, and many other fields. A huge number of methods and their various modifications have been developed for solving convex QPs. One of the first algorithms popularized as the solution method for QPs was the active-set method. The main idea of the method is selection of a set of binding constraints (an active set) and then iteratively adaptation it by adding and dropping constraints from the index set. The dual active-set (DAS) method of Goldfarb and Idnani is still well-known to be efficient and numerically stable. Taking advantage of the fact that the unconstrained minimum of the objective function can be used as a starting point of the method, its implementation utilizes the Cholesky and QR factorizations and procedures for updating them. At the same time, it suffers from the restriction that it cannot be applied to problems with positive semidefinite objective matrices, whereas in practice optimization problems may often be of such structure. We propose an add-in to the method of Goldfarb and Idnani that allows solving problems with positive semidefinite matrices directly by the DAS algorithm with a warm-start where a good estimate of the optimal active set is used to start the algorithm. The proposed technique is based on the well-known possibility of representing any matrix, as a difference of two, positive definite ones and solving then a sequence of so-called partially linearized problems. It can be viewed as a particular case of the special local search method for DC minimization problems. A computational experiment to testing the proposed approach was carried out on QPs with positive semidefinite objective matrices from the Maros and Meszaros test set. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Библиографическая ссылка
Vasiliev I. , Gruzdeva T. , Barkova M. , Boyarkin D. , Iakubovskii D. On Active-Set Methods for Quadratic Problems with Positive Semidefinite Matrices // Communications in Computer and Information Science. Vol.2239 CCIS. 2024. P.46-58. ISBN (print): 978-303173364-2. DOI: 10.1007/978-3-031-73365-9_3
Скопировать
