Journal of Convex Analysis 29 (2022), No. 1, 119--128
Copyright Heldermann Verlag 2022
Ubiquitous Algorithms in Convex Optimization Generate Self-Contracted Sequences
Axel Böhm
Faculty of Mathematics, University of Vienna, 1090 Vienna, Austria
axel.boehm@univie.ac.at
Aris Daniilidis
DIM--CMM, UMI CNRS 2807, FCFM, Universidad de Chile, Santiago, Chile
arisd@dim.uchile.cl
[Abstract-pdf]
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 $\{x_{k}\}_{k\in\mathbb{N}}$. As a consequence, a novel universal bound for the \emph{length} \ $\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.
Keywords: Proximal-gradient algorithm, alternating projection, self-contracted curve.
MSC: 52A41, 65K05; 52A05, 90C25.
[ Fulltext-pdf (111 KB)] for subscribers only.