# zbMATH — the first resource for mathematics

A direct active set algorithm for large sparse quadratic programs with simple bounds. (English) Zbl 0691.90070
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.
Reviewer: K.Zimmermann

##### MSC:
 90C20 Quadratic programming 65K05 Numerical mathematical programming methods 65K10 Numerical optimization and variational techniques 65F30 Other matrix algorithms (MSC2010) 90C06 Large-scale problems in mathematical programming
##### Software:
LINPACK; GQTPAR; CONEST; SONEST; symrcm
Full Text: