Minimizing quadratic functions subject to bound constraints with the rate of convergence and finite termination (Q1773107)

The authors present a new variant of the active set based algorithm for the solution of strictly convex quadratic programming problems with an inexact solution of auxiliary linear problems. The unique feature of the new algorithm is a balanced treatment of the chopped and free gradients that enables to prove both its rate of convergence in the matrix-vector multiplications and its finite termination property even for problems whose solution does not satisfy the strict complementary condition. The algorithm avoids any backtracking at the cost of using the upper bound on the spectral norm of the Hessian matrix. Its performance illustrated on the solution of the inner obstacle problems is comparable with that of some other efficient methods. The result is an important ingredient in development of scalable algorithms for numerical solution of elliptic variational inequalities.