Contraction Analysis of Geodesically Convex Optimization

Research paper by Patrick M. Wensing, Jean-Jacques E. Slotine

Indexed on: 18 Jun '18Published on: 18 Jun '18Published in: arXiv - Mathematics - Optimization and Control


Optimization is central to a wide array of problems across machine learning, estimation, automatic control, design, and many other areas. Convex optimization represents a subset of these instances where problems admit global solutions, which can often be computed using off-the-shelf solvers. Recently, increased attention has focused on geodesic convexity, or g-convexity. By endowing $\mathbb{R}^n$ with a Riemannian metric, non-convex problems can be transformed into convex ones over the induced Riemannian manifold. The main contribution of this paper is to provide a bridge between g-convexity and contraction analysis of nonlinear dynamical systems. Specifically, we show the equivalence between geodesic convexity and contraction of natural gradient flows. Given this result, existing tools from analysis and synthesis of nonlinear contracting systems can be considered to both discover and efficiently optimize g-convex functions. In addition, the contraction perspective allows one to easily apply results to non-autonomous systems, and to recursively build large optimization structures out of simpler elements.