Lecture SS 17 Selected Topics in Scientific Computing

Riemannian Optimization

Lecturer
Dr. Seyedehsomayeh Hosseini

Due to its wide range of applications, optimization on manifolds, or Riemannian optimization, is a fast growing research topic in the field of nonlinear optimization. In considering an optimization problem on a Riemannian manifold, fundamental challenges occur due to the nonlinear nature of the manifold. Indeed, any method which is based on the linear structure of the spaces-that is, virtually any method known in optimization- breaks down. A manifold is locally isomorphic to a linear space via chart maps. For this reason one might wonder whether it is enough to simply work in a chart domain and use classical linear algorithms. Unfortunately, such an approach does in general not lead to useful algorithms: First of all symmetries of the underlying Riemannian manifold will in general not be respected by such algorithms. Moreover, there often does not exist a canonical useful representation for charts. But more fundamentally, localizing to a chart inevitably leads to distortions in the metric which leads to much slower convergence. Finally, we are interested in establishing global convergence of the algorithms. Such a property is clearly out of reach by working in a chart domain, which is a local procedure. It is also clear that the mathematical analysis of global convergence requires global arguments from Riemannian geometry and cannot be deduced from corresponding linear results. For all those reasons, together with the evident need for efficient and reliable Riemannian optimization algorithms, the construction of intrinsic algorithms has become a thriving area of research in the past few years. Intended topics include:

  • Smooth optimization methods such as the steepest descent method, Newton’s method, trust-region methods and conjugate gradient methods
  • Derivative-free schemes such as the Powell’s method, direct local search methods and particle swarm optimization algorithms

Recommended literature:

  • P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press , 2008.
  • C. Udriste, Convex Functions and Optimization Methods on Riemannian Manifolds, Mathematics and its Applications, 297. Kluwer Academic Publishers Group, Dordrecht, 1994.

Prerequisites:

analysis and linear algebra (Bachelor level), smooth optimization methods (Steepest descent methods, Newton methods etc.). Numerische Mathematik (V2E1, V2E2), Wissenschaftliches Rechnen I (V3E1/F4E1).

Date & time: Wednesday14:15 to 15:45, Wegelerstr. 6, Room 5.002
Begin: Wednesday,19.04.2017