BOX CONSTRAINED QUADRATIC-PROGRAMMING WITH CONTROLLED PRECISION OF AUXILIARY PROBLEMS AND APPLICATIONS

We review our recent results on the solution of quadratic programming problems with simple bounds by means of the conjugate gradient method with inexact solution of auxiliary subproblems and projections. Precis ion of the solution of auxiliary problems is controlled by the product of a positive constant Gamma with the norm of violation of the Kuhn-T ucker contact conditions. The resulting algorithm converges for any po sitive Gamma and reaches the solution in a finite number of steps prov ided the problem is nondegenerate. A lower bound on Gamma is given so that the finite termination property is preserved even for degenerate problems. The algorithm may be implemented with projections so that it can drop and add many constraints whenever the active set is changed. Applications to the solution of inner obstacle problems and contact p roblems of elasticity are reported.