A practical relative error criterion for augmented Lagrangians (Q378086)

A new error criterion for the inexact solution of the subproblems in an augmented Lagrangian method for convex optimization problems is developed. The criterion only requires the gradient (or subgradient) of the augmented Lagrangian and hence can be easily checked in practice. It also is a relative error criterion since it relates the precision requirement for each subproblem to the current degree of violation of feasibility and complementarity, and it uses a single relative tolerance parameter only rather than a summable parameter sequence. At first an abstract version of the criterion is described within Rockafellar's general parametric convex duality framework and the resulting algorithm is proven to converge globally. Subsequently this algorithm is studied for standard convex programming problems for which it becomes a classical augmented Lagrangian type method with a novel condition for the inexact solution of the subproblems. Computational results for a subset of problems from the CUTE test set including many nonconvex problems are presented and indicate that the proposed approach is superior to previous approaches.