ON THE PROJECTED SUBGRADIENT METHOD FOR NONSMOOTH CONVEX-OPTIMIZATIONIN A HILBERT-SPACE

We consider the method for constrained convex optimization in a Hilber t space, consisting of a step in the direction opposite to an epsilon( k)-subgradient of the objective at a current iterate, followed by an o rthogonal projection onto the feasible set. The normalized stepsizes a lpha(k) are exogenously given, satisfying Sigma(k=0)(infinity), alpha( k) = infinity, Sigma(k=0)(infinity) alpha(k)(2) < infinity, and epsilo n(k) is chosen so that epsilon(k) less than or equal to mu alpha(k) fo r some mu > 0. We prove that the sequence generated in this way is wea kly convergent to a minimizer if the problem has solutions, and is unb ounded otherwise. Among the features of our convergence analysis, we m ention that it covers the nonsmooth case, in the sense that we make no assumption of differentiability of f, and much less of Lipschitz cont inuity of its gradient. Also, we prove weak convergence of the whole s equence, rather than just boundedness of the sequence and optimality o f its weak accumulation points, thus improving over all previously kno wn convergence results. We present also convergence rate results. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.