Gradient method for optimization on Riemannian manifolds with lower bounded curvature

DOI10.1137/18M1180633zbMATH Open1429.90051arXiv1806.02694OpenAlexW2981099578WikidataQ115246931 ScholiaQ115246931MaRDI QIDQ5237307FDOQ5237307

Authors: Maurício Silva Louzeiro, L. F. Prudente, O. P. Ferreira 

Publication date: 17 October 2019

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: The gradient method for minimize a differentiable convex function on Riemannian manifolds with lower bounded sectional curvature is analyzed in this paper. The analysis of the method is presented with three different finite procedures for determining the stepsize, namely, Lipschitz stepsize, adaptive stepsize and Armijo's stepsize. The first procedure requires that the objective function has Lipschitz continuous gradient, which is not necessary for the other approaches. Convergence of the whole sequence to a minimizer, without any level set boundedness assumption, is proved. Iteration-complexity bound for functions with Lipschitz continuous gradient is also presented. Numerical experiments are provided to illustrate the effectiveness of the method in this new setting and certify the obtained theoretical results. In particular, we consider the problem of finding the Riemannian center of mass and the so-called Karcher's mean. Our numerical experiences indicate that the adaptive stepsize is a promising scheme that is worth considering.

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

Recommendations

• Iteration-complexity of the subgradient method on Riemannian manifolds with lower bounded curvature
• Subgradient algorithms on Riemannian manifolds of lower bounded curvatures
• Convergence Analysis of Gradient Algorithms on Riemannian Manifolds without Curvature Constraints and Application to Riemannian Mass
• First order methods for optimization on Riemannian manifolds
• Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds

zbMATH Keywords

convex programmingRiemannian manifoldgradient methoditeration-complexity boundlower bounded curvature

Mathematics Subject Classification ID

Convex programming (90C25) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Benchmarking optimization software with performance profiles.
• Introductory lectures on convex optimization. A basic course.
• Gradient methods for minimizing composite functions
• The Geometry of Algorithms with Orthogonality Constraints
• Title not available (Why is that?)
• The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem
• Title not available (Why is that?)
• Optimization Techniques on Riemannian Manifolds
• Title not available (Why is that?)
• Smooth nonlinear optimization of \(\mathbb R^n\)
• Step-sizes for the gradient method
• Title not available (Why is that?)
• On the Riemannian geometry defined by self-concordant barriers and interior-point methods.
• Title not available (Why is that?)
• Geometric means
• Contributions to the study of monotone vector fields
• Non-existence of continuous convex functions on certain Riemannian manifolds
• On the convergence of gradient descent for finding the Riemannian center of mass
• Variational inequalities for set-valued vector fields on Riemannian manifolds: convexity of the solution set and the proximal point algorithm
• Weak sharp minima on Riemannian manifolds
• Title not available (Why is that?)
• Title not available (Why is that?)
• Statistics on the manifold of multivariate normal distributions: theory and application to diffusion tensor MRI processing
• The Gradient Projection Method Along Geodesics
• Concepts and techniques of optimization on the sphere
• Lattices in spaces of nonpositive curvature
• Full convergence of the steepest descent method with inexact line searches
• Conic geometric optimization on the manifold of positive definite matrices
• Computing the Karcher mean of symmetric positive definite matrices
• A survey and comparison of contemporary algorithms for computing the matrix geometric mean
• Minimizing a differentiable function over a differential manifold
• Domains of positivity
• Optimal placement of a deposit between markets: Riemann-Finsler geometrical approach
• Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds
• Global rates of convergence for nonconvex optimization on manifolds
• Subgradient projection algorithms for convex feasibility on Riemannian manifolds with lower bounded curvatures
• Linear convergence of subgradient algorithm for convex feasibility on Riemannian manifolds
• A framework for generalising the Newton method and other iterative methods from Euclidean space to manifolds
• Title not available (Why is that?)

Cited In (34)

• Nonlinear evolution equations via resolvent operators on Hadamard manifolds
• Nonsmooth nonconvex optimization on Riemannian manifolds via bundle trust region algorithm
• Iteration-complexity and asymptotic analysis of steepest descent method for multiobjective optimization on Riemannian manifolds
• Title not available (Why is that?)
• Constraint qualifications and optimality criteria for nonsmooth multiobjective programming problems on Hadamard manifolds
• On the relationship between the Kurdyka-Łojasiewicz property and error bounds on Hadamard manifolds
• Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds
• Numerical approaches for constrained and unconstrained, static optimization on the special Euclidean group \(\mathsf{SE}(3)\)
• Convexity of sets and quadratic functions on the hyperbolic space
• Optimality conditions and duality for multiobjective semi-infinite optimization problems with switching constraints on Hadamard manifolds
• Fenchel conjugate via Busemann function on Hadamard manifolds
• An adaptive Riemannian gradient method without function evaluations
• Proximal point method for quasiconvex functions in Riemannian manifolds
• Convergence Analysis of Gradient Algorithms on Riemannian Manifolds without Curvature Constraints and Application to Riemannian Mass
• Iterative algorithms for monotone variational inequality and fixed point problems on Hadamard manifolds
• Constraint qualifications and optimality conditions for nonsmooth multiobjective mathematical programming problems with vanishing constraints on Hadamard manifolds via convexificators
• A strongly convergent proximal point method for vector optimization
• Dynamical systems for solving variational inclusion and fixed point problems on Hadamard manifolds
• Title not available (Why is that?)
• On the convergence of gradient descent for finding the Riemannian center of mass
• A trust region method for solving multicriteria optimization problems on Riemannian manifolds
• Riemannian stochastic variance-reduced cubic regularized Newton method for submanifold optimization
• Fenchel duality theory and a primal-dual algorithm on Riemannian manifolds
• Variational inequalities governed by strongly pseudomonotone vector fields on Hadamard manifolds
• Iterative algorithm for singularities of inclusion problems in Hadamard manifolds
• Operator-valued formulas for Riemannian gradient and Hessian and families of tractable metrics in Riemannian optimization
• A modified proximal point method for DC functions on Hadamard manifolds
• Well-posedness of an interaction model on Riemannian manifolds
• Proximal gradient method for nonconvex and nonsmooth optimization on Hadamard manifolds
• Iteration-complexity of the subgradient method on Riemannian manifolds with lower bounded curvature
• Constraint qualifications for nonsmooth multiobjective programming problems with switching constraints on Hadamard manifolds
• Computing Riemannian center of mass on Hadamard manifolds
• First order methods for optimization on Riemannian manifolds
• Path-based incremental target level algorithm on Riemannian manifolds

Uses Software

• Matrix Means Toolbox

This page was built for publication: Gradient method for optimization on Riemannian manifolds with lower bounded curvature

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