Horoballs and the subgradient method
This work addresses optimization challenges in non-Euclidean spaces for researchers in mathematical optimization and geometry, though it is incremental as it adapts existing methods to a restricted class of objectives.
The paper tackles convex optimization in Hadamard spaces by developing a subgradient algorithm that uses horospherical convexity instead of traditional manifold assumptions, proving a complexity result independent of curvature bounds and applying it to the minimal enclosing ball problem.
To explore convex optimization on Hadamard spaces, we consider an iteration in the style of a subgradient algorithm. Traditionally, such methods assume that the underlying spaces are manifolds and that the objectives are geodesically convex: the methods are described using tangent spaces and exponential maps. By contrast, our iteration applies in a general Hadamard space, is framed in the underlying space itself, and relies instead on horospherical convexity of the objective level sets. For this restricted class of objectives, we prove a complexity result of the usual form. Notably, the complexity does not depend on a lower bound on the space curvature. We illustrate our subgradient algorithm on the minimal enclosing ball problem in Hadamard spaces.