ON THE PRIMAL-DUAL STEEPEST DESCENT ALGORITHM FOR EXTENDED LINEAR-QUADRATIC PROGRAMMING

The aim of this paper is two-fold. First, new variants are proposed fo r the primal-dual steepest descent algorithm as due in the family of p rimal-dual projected gradient algorithms developed by Zhu and Rockafel lar [SIAM J. Optim., 3 (1993), pp. 751-783] for large-scale extended l inear-quadratic programming. The variants include a second update sche me for the iterates, where the primal-dual feedback is arranged in a n ew pattern, as well as alternatives for the ''perfect line search'' in the original version of the reference. Second, new linear convergence results are proved for all these variants of the algorithm, including the original version as a special case, without the additional assump tions used by Zhu and Rockafellar. For the variants with the second up date scheme, a much sharper estimation for the rate of convergence is obtained due to the new primal-dual feedback pattern.