Global and Asymptotic Convergence Rate Estimates for a Class of Projected Gradient Processes

Projected gradient processes of the Goldstein–Levitin–Polyak type are considered for constrained minimization problems, _ F, with a convex set in a Hilbert space X and F: X R¹ a differentiable functional. Global and local convergence theorems are established for a large class of these processes, including those generated with implicit step length rules proposed by Bertsekas and Goldstein. In this analysis, traditional uniform strong positivity conditions on the Hessian ² F are replaced by weaker pseudoconvexity conditions and growth conditions on F. When F has a unique minimizes in, convergence rates are shown to depend on how rapidly the function () = \ r = F (x) - F () x. \| {x - \| \} grows with increasing > 0. If () B ^ for some B > 0, the processes \ Fₙ \ in question converge to F like O (n^{{ - / (- 2) }}), linearly, superlinearly, or in finitely many steps according to whether > 2, = 2, 2 > > 1, or = 1. The growth properties of () are in turn dependent upon the structure of F, and the norm on X. Close connections also exist here with a hierarchy of extremal types constructed in a recent study of conditional gradient algorithms, and with long-standing notions of singularity for constrained optimal control problems and unconstrained minimization problems on Rⁿ.