Ubiquitous algorithms in convex optimization generate self-contracted sequences

MaRDI QIDQ3391375zbMATH OpenFDO

Authors Axel Böhm, A. Daniilidis

Publication date 28 March 2022

Full work available at URL https://arxiv.org/abs/2003.04201, https://www.heldermann.de/JCA/JCA29/JCA291/jca29006.htm

zbMATH Keywords

alternating projectionproximal-gradient algorithmself-contracted curve

Mathematics Subject Classification ID

Convex sets without dimension restrictions (aspects of convex geometry) (52A05) Numerical mathematical programming methods (65K05) Convex programming (90C25)

Abstract: In this work we show that various algorithms, ubiquitous in convex optimization (e.g. proximal-gradient, alternating projections and averaged projections) generate self-contracted sequences ${x_k}_{kinmathbbN}$. As a consequence, a novel universal bound for the emph{length} ($su{m}_{kge0}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.

Recommendations

• Convergence of generalized contraction-proximal point algorithms for solving unconstrained convex optimization problems
• Rectifiability of self-contracted curves in the Euclidean space and applications
• Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions
• An Optimal Algorithm for Constrained Differentiable Convex Optimization
• Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization

Cites work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions
• Convex analysis and monotone operator theory in Hilbert spaces
• Gradient flows in metric spaces and in the space of probability measures
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• Maximum length of steepest descent curves for quasi-convex functions
• Metric and geometric relaxations of self-contracted curves
• On Projection Algorithms for Solving Convex Feasibility Problems
• On steepest descent curves for quasi convex families in Rn
• On the convergence of von Neumann's alternating projection algorithm for two sets
• Path length bounds for gradient descent and flow
• Rectifiability of non Euclidean planar self-contracted curves
• Rectifiability of self-contracted curves in the Euclidean space and applications
• Self-contracted curves are gradient flows of convex functions
• Self-contracted curves have finite length
• Self-contracted curves in CAT(0)-spaces and their rectifiability
• Self-contracted curves in Riemannian manifolds
• Self-contracted curves in spaces with weak lower curvature bound
• There is no variational characterization of the cycles in the method of periodic projections

Cited in

(1)

• Global convergence of the gradient method for functions definable in o-minimal structures

This page was built for publication: Ubiquitous algorithms in convex optimization generate self-contracted sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3391375)