optimization on manifolds

Accelerated Gradient Dynamics on Riemannian Manifolds: Faster Rate and Trajectory Convergence

  • Tejas Natu
  • Camille Castera
  • Jalal Fadili
  • Peter Ochs
    • Categories Convex Optimization, Optimization in Data Science Tags , , ,

    In order to minimize a differentiable geodesically convex function, we study a second-order dynamical system on Riemannian manifolds with an asymptotically vanishing damping term of the form \(\alpha/t\). For positive values of \(\alpha\), convergence rates for the objective values and convergence of trajectory is derived. We emphasize the crucial role of the curvature of the … Read more

    Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds

  • David H. Gutman
  • Nam Ho-Nguyen
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

    We extend coordinate descent to manifold domains, and provide convergence analyses for geodesically convex and non-convex smooth objective functions. Our key insight is to draw an analogy between coordinate blocks in Euclidean space and tangent subspaces of a manifold. Hence, our method is called tangent subspace descent (TSD). The core principle behind ensuring convergence of … Read more

    A Riemannian Conjugate Gradient Algorithm with Implicit Vector Transport for Optimization on the Stiefel Manifold

  • Hugo Lara
  • Harry Oviedo
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    In this paper, a reliable curvilinear search algorithm for solving optimization problems over the Stiefel manifold is presented. This method is inspired by the conjugate gradient method, with the purpose of obtain a new direction search that guarantees descent of the objective function in each iteration. The merit of this algorithm lies in the fact … Read more

    An implementation of the steepest descent method using retractions on riemannian manifolds

  • Ever Cruzado
  • Erik Alex Papa Quiroz
    • Categories Global Optimization Tags , , ,

    In 2008 Absil et al. published a book with optimization methods in Riemannian manifolds. The authors developed steepest descent, Newton, trust-region and conjugate gradients methods using an approximation of the geodesic called retraction. In this paper we present implementations of the of steepest descent method of Absil et al. using Matlab software. We show the … Read more

    Low-rank matrix completion via preconditioned optimization on the Grassmann manifold

  • Pierre-Antoine Absil
  • Nicolas Boumal
    • Categories Constrained Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , , , , , , , ,

    We address the numerical problem of recovering large matrices of low rank when most of the entries are unknown. We exploit the geometry of the low-rank constraint to recast the problem as an unconstrained optimization problem on a single Grassmann manifold. We then apply second-order Riemannian trust-region methods (RTRMC 2) and Riemannian conjugate gradient methods … Read more

    An implicit trust-region method on Riemannian manifolds

  • Pierre-Antoine Absil
  • Kyle A. Gallivan
  • C. G. Baker
    • Categories Constrained Nonlinear Optimization Tags , ,

    We propose and analyze an “implicit” trust-region method in the general setting of Riemannian manifolds. The method is implicit in that the trust-region is defined as a superlevel set of the ratio of the actual over predicted decrease in the objective function. Since this method potentially requires the evaluation of the objective function at each … Read more