A finite gradient-projective solver for a quadratic programming problem (Q2870272)

The minimization method for a quadratic functional with linear constraints, which is proposed in this paper, generalizes the technique previously published by the first author (see [\textit{A. A. Tret'yakov}, Russ. J. Numer. Anal. Math. Model. 25, No. 3, 279--288 (2010; Zbl 1193.65102)]). The aim of the authors is to obtain the solution in a finite number of steps, not using a priori information. The algorithm constructs a sequence of iterative approximations of the gradient method with step doubling. Each iteration generates the set of active constraints and forms the equivalent Kuhn-Tucker system that gives the minimum condition. The iterative approximations are initial points of a sequence of projections. The final point of this sequence gives the required point of minimum after a finite number of iterations. The number of iterations at each step polynomially depends on the dimension of the problem.