On the convergence of projected gradient processes to singular critical points (Q1821692): Difference between revisions

The projected gradient methods treated here generate iterates by the rule \(x_{k+1}=P_{\Omega}(x_ k-s_ k\nabla F(x_ k))\), \(x_ 1\in \Omega\), where \(\Omega\) is a closed convex set in a real Hilbert space X, \(s_ k\) is a positive real number determined by Goldstein's condition, \(P_{\Omega}\) projects X into \(\Omega\), F is a differentiable function whose minimum is sought in \(\Omega\), and \(\nabla F\) is locally Lipschitz continuous. Asymptotic stability and convergence rate theorems are proved for singular local minimizers \(\xi\) in the interior of \(\Omega\), or more generally, in some open facet in \(\Omega\). The stability theorem requires that: (i) \(\xi\) is a proper local minimizer and F grows uniformly in \(\Omega\) near \(\xi\) ; (ii) -\(\nabla F(\xi)\) lies in the relative interior of the cone \({\mathcal K}_{\xi}\) of outer normals to \(\Omega\) at \(\xi\) ; and (iii) \(\xi\) is an isolated critical point and the defect \(\| P_{\Omega}(x-\nabla F(x))-x\|\) grows uniformly within the facet containing \(\xi\). The convergence rate theorem imposes (i) and (ii), and also requires that: (iv) F is \(C^ 4\) near \(\xi\) and grows no slower than \(\| x-\xi \| ^ 4\) within the facet; and (v) the projected Hessian operator \(P_{{\mathcal T}_{\xi}}\nabla _ 2F(\xi)| _{{\mathcal T}_{\xi}}\) is positive-definite on its range in the subspace \({\mathcal T}_{\xi}\) orthogonal to \({\mathcal K}_{\xi}\). Under these conditions, \(\{x_ k\}\) converges to \(\xi\) from nearby starting points \(x_ 1\), with \(F(x_ k)-F(\xi)=O(k^{-2})\) and \(\| x_ k-\xi \| =O(k^{- 1/2})\). No explicit or implied local pseudoconvexity or level set compactness demands are imposed on F in this analysis. Furthermore, condition (v) and the uniform growth stipulations in (i) and (iii) are redundant in \({\mathbb{R}}^ n\).