A GENERALIZED SUBGRADIENT METHOD WITH RELAXATION STEP

We study conditions for convergence of a generalized subgradient algor ithm in which a relaxation step is taken in a direction, which is a co nvex combination of possibly all previously generated subgradients. A simple condition for convergence is given and conditions that guarante e a linear convergence rate are also presented. We show that choosing the steplength parameter and convex combination of subgradients in a c ertain sense optimally is equivalent to solving a minimum norm quadrat ic programming problem. It is also shown that if the direction is rest ricted to be a convex combination of the current subgradient and the p revious direction, then an optimal choice of stepsize and direction is equivalent to the Camerini-Fratta-Maffioli modification of the subgra dient method.