Error bound conditions and convergence of optimization methods on smooth and proximally smooth manifolds

Abstract

We analyse the convergence of the gradient projection algorithm, which is finalized with the Newton method, to a stationary point for the problem of nonconvex constrained optimization $\underset{x\in S}{min}f\left(x\right)$ with a proximally smooth set $S=\{x\in {\mathbb{R}}^n:g(x)=0\},g:{\mathbb{R}}^n\to {\mathbb{R}}^m$ and a smooth function f. We propose new Error bound (EB) conditions for the gradient projection method which lead to the convergence domain of the Newton method. We prove that these EB conditions are typical for a wide class of optimization problems. It is possible to reach high convergence rate of the algorithm by switching to the Newton method.

Keywords:

• Error bound condition
• gradient projection algorithm
• Newton's method
• nonconvex optimization
• proximal smoothness

2010 Mathematics Subject Classifications:

• Primary: 90C26
• 65K05
• Secondary: 46N10
• 65K10

Acknowledgements

The authors are grateful to B. T. Polyak for useful comments and suggestions. The authors are grateful to the anonymous referees for numerous comments and suggestions.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 This condition can be weakened and we can demand compactness for the intersection of some lower level set for f with S. Let $x_0\in S$ be an initial starting point in context of numerical methods. Then one can assume that the intersection of the boundary of the set S and the lower level set ${\mathcal{L}}_f\left(f\right(x_0\left)\right)=\{x\in {\mathbb{R}}^n:f(x)\le f(x_0\left)\right\}$ is empty and the intersection of the set S and the lower level set ${\mathcal{L}}_f\left(f\right(x_0\left)\right)$ is compact.

2 In a finite dimensional space continuity of the mapping $U_S\left(R\right)\ni x\to P_{S}x$ can be omitted. This follows from uniqueness and upper semicontinuity of the metric projection [28, Ch. 3, § 1, Proposition 23].

3 We can treat ${\sigma }_0$ as minimal singular value of matrices $F^{\prime }\left(z\right){|}_{z=[x_{\ast },{\lambda }_{x_{\ast }}]},x_{\ast }\in \mathrm{\Omega }$ (it coincides with minimal by absolute value eigenvalue, $\mathrm{\Lambda }(\cdot )$ denotes the spectrum of a matrix): ${\sigma }_0\ge \underset{x_{\ast }\in \mathrm{\Omega }}{max}\parallel F^{\prime }(x_{\ast },{\lambda }_{x_{\ast }}{)}^{-1}\parallel =(\underset{x_{\ast }\in \mathrm{\Omega }}{min}{\sigma }_{min}\left(F^{\prime }\right(x_{\ast },{\lambda }_{x_{\ast }}\left)\right){)}^{-1}=(\underset{x_{\ast }\in \mathrm{\Omega },\lambda \in \mathrm{\Lambda }\left(F\right(x_{\ast },{\lambda }_{x_{\ast }}\left)\right)}{min}|\lambda |{)}^{-1}.$

4 Sometimes called the Polyak–Lojasiewicz condition or the Kurdyka–Lojasiewicz condition $\mu \parallel f^{\prime }\left(x\right){\parallel }^{\alpha }\ge f\left(x\right)-f_{min}$, $\alpha \ge 1$.

5 It is sufficient to demand Lipschitz continuity of $F^{\prime }(x,{\lambda }_x)$ in some neighbourhood of stationary points. This leads to one more restriction of the value β from above. Moreover, we can consider weaker condition $\parallel F^{\prime }(x,{\lambda }_x)-F^{\prime }(x_{\ast },{\lambda }_{x_{\ast }})\parallel \le L_{1,Fx}\parallel x-x_{\ast }\parallel$, where $x_{\ast }$ is the nearest stationary point to the point $x\in S$.

Additional information

Funding

The work was supported by Russian Science Foundation (Project 16-11-10015).