A direct active set algorithm for large sparse quadratic programs with simple bounds (Q583116)

The authors show how a direct active set method can be efficiently implemented for quadratic problems of the form min \(x^ TAx+b^ Tx\), \(\ell \leq x\leq u\), where A is an \(n\times n\) symmetric (not necessarily positive definite) large and sparse matrix. The following improvements to the basic algorithm are proposed: (1) a new way to find a search direction in the indefinite case that allows to free more than one variable at a time; (2) a new heuristic method for finding a starting point. Further it is shown how projection techniques can be used to add several constraints to the active set at each iteration. The experimental results showed that the algorithm with these improvements is faster for positive definite problems and finds local minima with lower function values for indefinite problems. The designed algorithms are not in general polynomial and in the indefinite case find only local minima.