Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds

DOI10.1007/S10957-017-1093-4zbMATH Open1400.90277arXiv1609.04869OpenAlexW2522924238WikidataQ115382559 ScholiaQ115382559MaRDI QIDQ2363571FDOQ2363571

Authors: J. G. Melo, G. C. Bento, O. P. Ferreira 

Publication date: 20 July 2017

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Abstract: This paper considers optimization problems on Riemannian manifolds and analyzes iteration-complexity for gradient and subgradient methods on manifolds with non-negative curvature. By using tools from the Riemannian convex analysis and exploring directly the tangent space of the manifold, we obtain different iteration-complexity bounds for the aforementioned methods, complementing and improving related results. Moreover, we also establish iteration-complexity bound for the proximal point method on Hadamard manifolds.

Full work available at URL: https://arxiv.org/abs/1609.04869

Recommendations

• Iteration-complexity of the subgradient method on Riemannian manifolds with lower bounded curvature
• First order methods for optimization on Riemannian manifolds
• Subgradient algorithm on Riemannian manifolds
• Gradient method for optimization on Riemannian manifolds with lower bounded curvature
• The study of the subgradient algorithm and its convergence on Riemannian manifolds

zbMATH Keywords

complexityRiemannian manifoldgradient methodproximal point methodsubgradient method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Introductory lectures on convex optimization. A basic course.
• The Geometry of Algorithms with Orthogonality Constraints
• Title not available (Why is that?)
• Optimization Techniques on Riemannian Manifolds
• Title not available (Why is that?)
• Smooth nonlinear optimization of \(\mathbb R^n\)
• Monotone Operators and the Proximal Point Algorithm
• Title not available (Why is that?)
• On the Riemannian geometry defined by self-concordant barriers and interior-point methods.
• The proximal point algorithm in metric spaces
• Subgradient algorithm on Riemannian manifolds
• Steepest descent method with a generalized Armijo search for quasiconvex functions on Riemannian manifolds
• \(\varepsilon\)-subgradient algorithms for locally Lipschitz functions on Riemannian manifolds
• Weak sharp minima on Riemannian manifolds
• Monotone vector fields and the proximal point algorithm on Hadamard manifolds
• Subgradient method for convex feasibility on Riemannian manifolds
• Title not available (Why is that?)
• Proximal Point Algorithm On Riemannian Manifolds
• Title not available (Why is that?)
• Proximal point method for a special class of nonconvex functions on Hadamard manifolds
• Convex- and monotone-transformable mathematical programming problems and a proximal-like point method
• A new approach to the proximal point method: convergence on general Riemannian manifolds
• A subgradient method for multiobjective optimization on Riemannian manifolds
• The Gradient Projection Method Along Geodesics
• Local convergence of the proximal point method for a special class of nonconvex functions on Hadamard manifolds
• A proximal point algorithm for DC functions on Hadamard manifolds
• Minimizing a differentiable function over a differential manifold
• Subgradient projection algorithms for convex feasibility on Riemannian manifolds with lower bounded curvatures
• Linear Convergence of Subgradient Algorithm for Convex Feasibility on Riemannian Manifolds

Cited In (34)

• An accelerated first-order method for non-convex optimization on manifolds
• Riemannian proximal gradient methods
• Iteration-complexity and asymptotic analysis of steepest descent method for multiobjective optimization on Riemannian manifolds
• Computing second-order points under equality constraints: revisiting Fletcher's augmented Lagrangian
• Gradient Method for Optimization on Riemannian Manifolds with Lower Bounded Curvature
• A communication-efficient and privacy-aware distributed algorithm for sparse PCA
• Smoothing algorithms for nonsmooth optimization over the Stiefel manifold with applications to the graph Fourier basis problem
• A projection algorithm for pseudomonotone vector fields with convex constraints on Hadamard manifolds
• First Order Methods for Optimization on Riemannian Manifolds
• An active-set proximal quasi-Newton algorithm for ℓ₁-regularized minimization over a sphere constraint
• Simple algorithms for optimization on Riemannian manifolds with constraints
• Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
• Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• A brief introduction to manifold optimization
• Subgradient projection algorithms for convex feasibility on Riemannian manifolds with lower bounded curvatures
• An adaptive Riemannian gradient method without function evaluations
• Adaptive regularization with cubics on manifolds
• Iterative Method with Inertia for Variational Inequalities on Hadamard Manifolds with Lower Bounded Curvature
• Title not available (Why is that?)
• Riemannian stochastic variance-reduced cubic regularized Newton method for submanifold optimization
• Traub-type high order iterative procedures on Riemannian manifolds
• Title not available (Why is that?)
• A Projected Subgradient Method for the Computation of Adapted Metrics for Dynamical Systems
• Riemannian optimization with a preconditioning scheme on the generalized Stiefel manifold
• A modified proximal point method for DC functions on Hadamard manifolds
• Proximal gradient method for nonconvex and nonsmooth optimization on Hadamard manifolds
• A Dynamic Smoothing Technique for a Class of Nonsmooth Optimization Problems on Manifolds
• Iteration-complexity of the subgradient method on Riemannian manifolds with lower bounded curvature
• Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
• Proximal gradient algorithm with trust region scheme on Riemannian manifold
• Riemannian optimization via Frank-Wolfe methods
• Path-based incremental target level algorithm on Riemannian manifolds
• Proximal Point Algorithm On Riemannian Manifolds

This page was built for publication: Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds

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