Global and Asymptotic Convergence Rate Estimates for a Class of Projected Gradient Processes
J. C. Dunn · SIAM Journal on Control and Optimization · 1981
Projected gradient processes of the Goldstein–Levitin–Polyak type are considered for constrained minimization problems, $\min _\Omega F$, with $\Omega $ a convex set in a Hilbert space X and $F:X \to \mathbb{R}^1 $ 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 $ abla ^2 F$ are replaced by weaker pseudoconvexity conditions and growth conditions on F. When F has a unique minimizes in $\Omega $, convergence rates are shown to depend on how rapidly the function $\gamma (\sigma ) = \inf \{ r = F(x) - F(\xi )\mid x . \in \Omega \| {x - \xi } \| \geqq \sigma \} $ grows with increasing $\sigma > 0$. If $\gamma (\sigma ) \geqq B\sigma ^ u $ for some $B > 0$, the processes $\{ F_n \} $ in question converge to $\inf F$ like $O(n^{{{ - u } / {( u - 2)}}} )$, linearly, superlinearly, or in finitely many steps according to whether $ u > 2$, $ u = 2$, $2 > u > 1$, or $ u = 1$. The growth properties of $\gamma (\sigma )$ are in turn dependent upon the structure of F, $\Omega $ 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 $\mathbb{R}^n $.