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

This is the authors' abstract. We don't add key points for this paper.

Projected gradient processes of the Goldstein–Levitin–Polyak type are considered for constrained minimization problems, min _Ω 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 γ (σ ) = inf \ r = F(x) - F(ξ ) x . ∈ Ω \| x - ξ \| σ \ grows with increasing σ > 0. If γ (σ ) Bσ ^ν for some $B > 0$, the processes \ Fₙ \ in question converge to inf 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ⁿ.