Augmented Lagrangians, box constrained QP and extensions

摘要

A new method is described for the solution of the box constrained convex quadratic programming (QP) problems, based on modifications of Rockafellar's augmented Lagrangian function. A reduced function is defined by eliminating the multiplier parameter vector in a novel way. A minimizer of this function is shown to solve box-constrained QP. The function is convex and C-1 piecewise quadratic, and under mild conditions it is strictly convex. Thus a Newton iteration is readily devised and easily implemented. The same Newton iteration is already well known and frequently used as a consequence of semi-smooth Newton theory, but the development here, especially the globalization scheme, is thought to be new. A nonmonotonic line search can be used to guarantee finite convergence, but often this is not required. Some important issues in regard to the line search are discussed. Successful numerical results are presented on a wide selection of large dimension test problems from various areas of application and from the CUTE test set. Some very large problems are solved in a reasonable time. Further, this method is extended to solve box constrained QPs that include a few linear equations. Encouraging numerical evidence is presented on a range of practical problems of up to 10(8) variables from various sources. Issues relating to guaranteed convergence are discussed.