Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs

PDF

Abstract

We present a two-phase algorithm for solving large-scale quadratic programs (QPs). In the first phase, gradient-projection iterations approximately minimize an augmented Lagrangian function and provide an estimate of the optimal active set. In the second phase, an equality-constrained QP defined by the current inactive variables is approximately minimized in order to generate a second-order search direction. A filter determines the required accuracy of the subproblem solutions and provides an acceptance criterion for the search directions. The resulting algorithm is globally and finitely convergent. The algorithm is suitable for large-scale problems with many degrees of freedom, and provides an alternative to interior-point methods when iterative methods must be used to solve the underlying linear systems. Numerical experiments on a subset of the CUTEr QP test problems demonstrate the effectiveness of the approach.

BiBTeX

@article{FrieLeyf:2008,
   author = {Michael P. Friedlander and Sven Leyffer},
   title = {Global and finite termination of a two-phase augmented
           {L}agrangian filter method for general quadratic programs},
   publisher = {SIAM},
   year = {2008},
   journal = {SIAM Journal on Scientific Computing},
   volume = {30},
   number = {4},
   pages = {1706-1729},
   keywords = {large-scale optimization; quadratic programming;
               gradient projection; active-set methods; filter methods;
               augmented {L}agrangian},
   url = {http://link.aip.org/link/?SCE/30/1706},
   doi = {10.1137/060669930}
}