Optimal quadratic programming algorithms: with applications to variational inequalities

The main purpose of this book is to present some recent results concerning the development of in a sense optimal algorithms for the solution of large bound and/or equality constrained quadratic programming (QP) problems. The unique feature of these algorithms is the rate of convergence in terms of the bounds on the spectrum of the Hessian matrix of the cost function. If applied to the class of QP problems with the cost functions whose Hessian has the spectrum confined to a given positive interval, the algorithms can find approximate solutions in a uniformly bounded number of simple iterations. such as the matrix-vector multiplications. Moreover, if the class of problems admits a sparse representation of the Hessian, it simply follows that the cost of the solution Is proportional to the number of unknowns.