Lipschitz continuity of the metric projection operator and convergence of gradient methods

M. V. Balashov

Sbornik. Mathematics, Tome 215 (2024) no. 4, pp. 494-510

Résumé

Various support conditions for a closed subset of a real Hilbert space $\mathcal H$ at a boundary point of this set are considered. These conditions ensure certain local Lipschitz continuity of the metric projection operator as a function of a point. The local Lipschitz continuity of the metric projection as a function of the set in the Hausdorff metric is also proved. This Lipschitz property is used to verify the linear convergence of some gradient methods (the gradient projection method and the conditional gradient method) without assuming that the function must be strongly convex (or even convex) and for not necessarily convex sets. The function is assumed to be differentiable with Lipschitz continuous gradient. Bibliography: 29 titles.

Détail

Keywords: support strong convexity condition, support weak convexity condition, gradient projection method, conditional gradient method, nonsmooth analysis.

Bibliographie

[1] R. R. Phelps, “Convex sets and nearest points”, Proc. Amer. Math. Soc., 8 (1957), 790–797 | DOI | MR | Zbl

[2] T. Abatzoglou, “The metric projection on $C^2$ manifolds in Banach spaces”, J. Approx. Theory, 26:3 (1979), 204–211 | DOI | MR | Zbl

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

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

[5] B. O. Björnestål, “Local Lipschitz continuity of the metric projection operator”, Approximation theory, Papers, VIth semester, Stefan Banach Internat. Math. Center, Warsaw, 1975, Banach Center Publ., 4, PWN–Polish Sci. Publ., Warsaw, 1979, 43–53 | DOI | MR | Zbl

[6] J. W. Daniel, “The continuity of metric projections as functions of the data”, J. Approx. Theory, 12:3 (1974), 234–239 | DOI | MR | Zbl

[7] E. S. Polovinkin and M. V. Balashov, Elements of convex and strongly convex analysis, 2nd ed., Fizmatlit, Moscow, 2007, 438 pp. (Russian) | Zbl

[8] V. I. Berdyšev (Berdyshev), “Continuity of a multivalued mapping connected with the problem of minimizing a functional”, Math. USSR-Izv., 16:3 (1981), 431–456 | DOI | MR | Zbl

[9] G. E. Ivanov, “Sharp estimates for the moduli of continuity of metric projections onto weakly convex sets”, Izv. Math., 79:4 (2015), 668–697 | DOI | MR | Zbl

[10] E. S. Levitin and B. T. Polyak, “Constrained minimization methods”, U.S.S.R. Comput. Math. Math. Phys., 6:5 (1966), 1–50 | DOI | MR | Zbl

[11] V. M. Veliov, “On the convexity of integrals of multivalued mappings: applications in control theory”, J. Optim. Theory Appl., 54:3 (1987), 541–563 | DOI | MR | Zbl

[12] G. Braun, A. Carderera, C. W. Combettes, H. Hassani, A. Karbasi, A. Mokhtari and S. Pokutta, Conditional gradient methods, arXiv: 2211.14103v1

[13] M. V. Balashov, “Maximization of a function with Lipschitz continuous gradient”, J. Math. Sci. (N.Y.), 209:1 (2015), 12–18 | DOI | MR | Zbl

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

[15] A. V. Marinov, “On uniform constants of strong uniqueness in Chebyshev approximations and fundamental results of N. G. Chebotarev”, Izv. Math., 75:3 (2011), 603–630 | DOI | MR | Zbl

[16] B. T. Polyak, “Minimization of unsmooth functionals”, U.S.S.R. Comput. Math. Math. Phys., 9:3 (1969), 14–29 | DOI | MR | Zbl

[17] D. Davis, D. Drusvyatskiy, K. J. MacPhee and C. Paquette, Subgradient methods for sharp weakly convex functions, arXiv: 1803.02461v1

[18] Xiao Li, Zhihui Zhu, A. Man-Cho So and J. D. Lee, Incremental methods for weakly convex optimization, arXiv: 1907.11687v1

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

[20] P.-A. Absil, R. Mahony and R. Sepulchre, Optimization algorithms on matrix manifolds, Princeton Univ. Press, Princeton, NJ, 2008, xvi+224 pp. | DOI | MR | Zbl

[21] M. V. Balashov, “The gradient projection algorithm for a proximally smooth set and a function with Lipschitz continuous gradient”, Sb. Math., 211:4 (2020), 481–504 | DOI | MR | Zbl

[22] M. V. Balashov, “Gradient projection method on matrix manifolds”, Comput. Math. Math. Phys., 60:9 (2020), 1403–1411 | DOI | MR | Zbl

[23] 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

[24] M. V. Balashov and M. O. Golubev, “About the Lipschitz property of the metric projection in the Hilbert space”, J. Math. Anal. Appl., 394:2 (2012), 545–551 | DOI | MR | Zbl

[25] M. V. Balashov, “Sufficient conditions for the linear convergence of an algorithm for finding the metric projection of a point onto a convex compact set”, Math. Notes, 113:5 (2023), 632–641 | DOI | MR | Zbl

[26] N. V. Efimov and S. B. Stechkin, “Approximation properties of sets in normed linear spaces”: S. B. Stechkin, Selected papers, Fizmatlit, Moscow, 1998, 270–281 (Russian) | MR | Zbl

[27] M. V. Balashov and K. Z. Biglov, “The strong convexity supporting condition and the Lipschitz condition for the metric projection”, Math. Notes, 115:2 (2024), 164–172

[28] I. Necoara, Yu. Nesterov and F. Glineur, “Linear convergence of first order methods for non-strongly convex optimization”, Math. Program., 175:1–2(A) (2019), 69–107 | DOI | MR | Zbl

[29] Y. Bello-Cruz, Guoyin Li and T. T. A. Nghia, “On the linear convergence of forward-backward splitting method: Part I — Convergence analysis”, J. Optim. Theory Appl., 188:2 (2021), 378–401 | DOI | MR | Zbl