The application of finite element methods to the solution of many variational inequalities leads to the minimization of a quadratic function of a large number of variables with bound constraints. Unconstrained problems of this size are often solved using conjugate gradient (CG) methods. This paper describes an algorithm to solve these problems using CG for the minimization, with an active set method to deal with the constraints. The algorithm is a modification of one previously published by one of the authors [1].

The algorithm is an active set method, which uses CG steps on the face of the feasible region determined by the current active set, until either a step leaves the feasible region, or the projected gradient becomes smaller than a fixed multiple of the norm of the violations of the Karush–Kuhn–Tucker conditions at the active constraints. In the first case, a fixed-length step is taken to an edge of the face, and the active set is expanded. In the second case, a minimum is found in the direction of the violated constraints, namely, perpendicular to the face.

This paper presents an effective way to extend straightforward CG methods to problems with bound constraints. The authors prove convergence rate results for the algorithm in terms of the condition number of the matrix of the quadratic form, and the two fixed constants used in the algorithm. These results lead to recommended ranges for values of these constants. The algorithm is applied to some finite element problems, and numerical results are given.