Abstract

We show that various algorithms, ubiquitous in convex optimization (e.g. pro\-ximal-gradient, alternating projections and averaged projections) generate self-con\-trac\-ted sequences {xk}k∈N\{x_{k}\}_{k\in\mathbb{N}}. As a consequence, a novel universal bound for the length ∑k≥0∥xk+1−xk∥\sum_{k\ge 0}\Vert x_{k+1}-x_k\Vert can be deduced. In addition, this bound is independent of both the concrete data of the problem (sets, functions) as well as the stepsize involved, and only depends on the dimension of the space.

Author information

Contact details are reproduced from the original publication and may be historical.

Aris Daniilidis

DIM–CMM, UMI CNRS 2807, FCFM, Universidad de Chile, Santiago, Chile

arisd@dim.uchile.cl

Keywords

  • Proximal-gradient algorithm
  • alternating projection
  • self-contracted curve

Mathematics Subject Classification

52A41, 65K05; 52A05, 90C25

References

  1. L. Ambrosio, N. Gigli, G. Savare: Gradient Flows in Metric Spaces and in the Space of Probability Measures, Lectures in Mathematics, ETH Zürich, Birkhäuser, Basel (2008).Google Scholar
  2. J.-B. Baillon, P. L. Combettes, R. Cominetti: There is no variational characterization of the cycles in the method of periodic projections, J. Funct. Analysis 262 (2012) 400–408.https://doi.org/10.1016/j.jfa.2011.09.002Google Scholar
  3. H. Bauschke, J. Borwein: On the convergence of von Neumann’s alternating projection algorithm for two sets, Set-Valued Analysis 1 (1993) 185–212.https://doi.org/10.1007/BF01027691Google Scholar
  4. H. Bauschke, J. Borwein: On projection algorithms for solving convex feasibility problems, SIAM Review 38 (1996) 367–426.https://doi.org/10.1137/S0036144593251710Google Scholar
  5. H. Bauschke, P. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics, Springer, Cham (2011).https://doi.org/10.1007/978-1-4419-9467-7Google Scholar
  6. A. Beck, M. Teboulle: A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009) 183–202.https://doi.org/10.1137/080716542Google Scholar
  7. D. Bertsekas: Nonlinear Programming, 2nd ed., Athena Scientific, Belmont (1999).Google Scholar
  8. A. Daniilidis, G. David, E. Durand-Cartagena, A. Lemenant: Rectifiability of self-contracted curves in the Euclidean space and applications, J. Geom. Analysis 25 (2015) 1211–1239.https://doi.org/10.1007/s12220-013-9464-zGoogle Scholar
  9. A. Daniilidis, R. Deville, E. Durand-Cartagena, L. Rifford: Self-contracted curves in Riemannian manifolds, J. Math. Analysis Appl. 457 (2018) 1333–1352.https://doi.org/10.1016/j.jmaa.2017.04.011Google Scholar
  10. A. Daniilidis, R. Deville, E. Durand-Cartagena: Metric and geometric relaxations of self-contracted curves, J. Optim. Theory Appl. 182 (2019) 81–109.https://doi.org/10.1007/s10957-018-1408-0Google Scholar
  11. A. Daniilidis, O. Ley, S. Sabourau: Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions, J. Math. Pures Appl. 94 (2010) 183–199.https://doi.org/10.1016/j.matpur.2010.03.007Google Scholar
  12. E. Durand-Cartagena, A. Lemenant: Self-contracted curves are gradient flows of convex functions, Proc. Amer. Math. Soc. 147 (2019) 2517–2531.https://doi.org/10.1090/proc/14407Google Scholar
  13. C. Gupta, S. Balakrishnan, A. Ramdas: Path length bounds for gradient descent and flow, J. Mach. Learning Res. 22 (2021) art. no. 68.Google Scholar
  14. N. Lebedeva, S. Ohta, V. Zolotov: Self-contracted curves in spaces with weak lower curvature bound, Int. Math. Res. Notices, 11 (2021) 8623–8656.https://doi.org/10.1093/imrn/rnz347Google Scholar
  15. A. Lemenant: Rectifiability of non-Euclidean planar self-contracted curves, Confluentes Math. 8 (2016) 23–38.https://doi.org/10.5802/cml.31Google Scholar
  16. M. Longinetti, P. Manselli, A. Venturi: On steepest descent curves for quasi convex families in Rn, Math. Nachrichten 288 (2015) 420–442.https://doi.org/10.1002/mana.201300133Google Scholar
  17. P. Manselli, C. Pucci: Maximum length of steepest descent curves for quasi-convex functions, Geom. Dedicata 38 (1991) 211–227.https://doi.org/10.1007/BF00181220Google Scholar
  18. S. Ohta: Self-contracted curves in CAT(0)-spaces and their rectifiability, J. Geom. Analysis 3 (2020) 936–967.https://doi.org/10.1007/s12220-018-00126-7Google Scholar
  19. E. Stepanov, Y. Teplitskaya: Self-contracted curves have finite length, J. London Math. Soc. 96 (2017) 455–481.https://doi.org/10.1112/jlms.12068Google Scholar

Suggested citation

A. Böhm, A. Daniilidis. “Ubiquitous Algorithms in Convex Optimization Generate Self-Contracted Sequences.” Journal of Convex Analysis 29 (2022), No. 1, 119–128. https://doi.org/10.68381/jca29006

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2022. Rights now held by Banach Press LLC.