Geodesic
On the Gradient Projection Method for Weakly Convex Functions on a Proximally Smooth Set
Matematičeskie zametki, Tome 108 (2020) no. 5, pp. 657-668.

Voir la notice de l'article provenant de la source Math-Net.Ru

Let a weakly convex function (in the general case, nonconvex and nonsmooth) satisfy the quadratic growth condition. It is proved that the gradient projection method for minimizing such a function on a set converges with linear rate on a proximally smooth (nonconvex) set of special form (for example, on a smooth manifold), provided that the weak convexity constant of the function is less than the constant in the quadratic growth condition and the constant of proximal smoothness for the set is sufficiently large. The connection between the quadratic growth condition on the function and other conditions is discussed.
Keywords: weak convexity, quadratic growth, gradient projection method, proximal smoothness, nonsmooth analysis. 
@article{MZM_2020_108_5_a1,
     author = {M. V. Balashov},
     title = {On the {Gradient} {Projection} {Method} for {Weakly} {Convex} {Functions} on a {Proximally} {Smooth} {Set}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {657--668},
     publisher = {mathdoc},
     volume = {108},
     number = {5},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2020_108_5_a1/}
}
TY  - JOUR
AU  - M. V. Balashov
TI  - On the Gradient Projection Method for Weakly Convex Functions on a Proximally Smooth Set
JO  - Matematičeskie zametki
PY  - 2020
SP  - 657
EP  - 668
VL  - 108
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2020_108_5_a1/
LA  - ru
ID  - MZM_2020_108_5_a1
ER  - 
%0 Journal Article
%A M. V. Balashov
%T On the Gradient Projection Method for Weakly Convex Functions on a Proximally Smooth Set
%J Matematičeskie zametki
%D 2020
%P 657-668
%V 108
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2020_108_5_a1/
%G ru
%F MZM_2020_108_5_a1
M. V. Balashov. On the Gradient Projection Method for Weakly Convex Functions on a Proximally Smooth Set. Matematičeskie zametki, Tome 108 (2020) no. 5, pp. 657-668. http://geodesic.mathdoc.fr/item/MZM_2020_108_5_a1/

[1] B. T. Polyak, “Gradientnye metody minimizatsii funktsionalov”, Zh. vychisl. matem. i matem. fiz., 3:4 (1963), 643–653 | MR | Zbl

[2] E. S. Levitin, B. T. Polyak, “Metody minimizatsii pri nalichii ogranichenii”, Zh. vychisl. matem. i matem. fiz., 6:5 (1966), 787–823 | MR | Zbl

[3] B. T. Polyak, Vvedenie v optimizatsiyu, Nauka, M, 1983 | Zbl

[4] D. Davis, D. Drusvyatskiy, K. J. MacPhee, C. Paquette, Subgradient Methods for Sharp Weakly Convex Functions, 2018, arXiv: 1803.02461v1

[5] X. Li, Zh. Zhu, A. Man-Cho So, J. D. Lee, Incremental Methods for Weakly Convex Optimization, 2019, arXiv: 1907.11687v1

[6] H. Karimi, J. Nutini, M. Schmidt, “Linear convergence of gradient and proximal-gradient methods under the Polyak–Lojasiewicz condition”, Machine Learning and Knowledge Discovery in Databases, Lecture Notes in Comput. Sci., 9851, Springer, Cham, 2016 | DOI

[7] D. Drusvyatskiy, A. S. Lewis, “Error bounds, quadratic growth, and linear convergence of proximal methods”, Math. Oper. Res., 43:3 (2018), 919–948 | MR | Zbl

[8] J.-P. Vial, “Strong and weak convexity of sets and functions”, Math. Oper. Res., 8:2 (1983), 231–259 | MR | Zbl

[9] F. H. Clarke, R. J. Stern, P. R. Wolenski, “Proximal smoothness and lower-$C^{2}$ property”, J. Convex Anal., 2:1-2 (1995), 117–144 | MR | Zbl

[10] Zh.-P. Oben, I. Ekland, Prikladnoi nelineinyi analiz, Mir, M., 1988 | MR | Zbl

[11] R. A. Poliquin, R. T. Rockafellar, L. Thibault, “Local differentiability of distance functions”, Trans. Amer. Math. Soc., 352:11 (2000), 5231–5249 | MR | Zbl

[12] M. Bounkhel, L. Thibault, “On various notions of regularity of sets in nonsmooth analysis”, Nonlinear Anal., 48:2 (2002), 223–246 | MR | Zbl

[13] P.-A. Absil, J. Malick, “Projection-like retractions on matrix manifolds”, SIAM J. Optim., 22:1 (2012), 135–158 | MR | Zbl

[14] R. T. Rockafellar, R. J. B. Wets, Variational Analysis, Springer-Verlag, Berlin, 2009 | DOI | Zbl

[15] M. V. Balashov, “Metod proektsii gradienta na matrichnykh mnogoobraziyakh”, Zh. vychisl. matem. i matem. fiz., 60:9 (2020), 1453–1461

[16] Yu. E. Nesterov, Vvedenie v vypukluyu optimizatsiyu, MTsMNO, M, 2010

[17] M. V. Balashov, “About the gradient projection algorithm for a strongly convex function and a proximally smooth set”, J. Convex Anal., 24:2 (2017), 493–500 | MR | Zbl

[18] J.-P. Aubin, A. Cellina, Differential Inclusions, Springer-Verlag, Berlin, 1984 | MR | Zbl

[19] H. Liu, W. Wu, A. M.-Ch. So, “Quadratic optimization with orthogonality Constraints: explicit Lojasiewicz exponent and linear convergence of line-search methods”, ICML'16: Proceedings of the 33rd International Conference on International Conference on Machine Learning, Proc. Machine Learning Res., 48, 2016, 1158–1167

[20] M. V. Balashov, “Metod proektsii gradienta dlya proksimalno gladkogo mnozhestva i funktsii s nepreryvnym po Lipshitsu gradientom”, Matem. sb., 211:4 (2020), 3–26 | DOI | Zbl

[21] R. Schneider, A. Uschmajew, “Convergence results for projected line search methods on varieties of low-rank matrices via Lojasiewicz inequality”, SIAM J. Optim., 25:1 (2015), 622–646 | MR | Zbl

[22] M. V. Balashov, B. T. Polyak, A. A. Tremba, “Gradient projection and conditional gradient methods for constrained nonconvex minimization”, Numer. Funct. Anal. Optim., 41:7 (2019), 822–849 | MR