193. Convex optimization in nonpositively curved geodesic spaces
Invited abstract in session MD-50: Variational analysis and equilibria, stream Variational analysis, equilibria and nonsmooth optimization.
Monday, 14:30-16:00Room: Parkinson B11
Authors (first author is the speaker)
| 1. | Adrian Lewis
|
| School of ORIE, Cornell University | |
| 2. | Ariel Goodwin
|
| Center for Applied Mathematics, Cornell University | |
| 3. | Genaro Lopez
|
| Análisis Matemático, Universidad de Sevilla | |
| 4. | Adriana Nicolae
|
| Babes-Bolyai University |
Abstract
In various disciplines, data sets live in Hadamard spaces: complete metric spaces with nonpositive curvature, meaning that triangles are thinner than their Euclidean analogues. Examples include manifolds like Euclidean space, hyperbolic space, and the cone of positive-definite matrices with the affine-invariant metric. However, models ranging from robotics to phylogenetics involve Hadamard spaces that are not manifolds: one interesting example is the BHV tree space, which is a complex of orthants. Hadamard spaces invite convex optimization techniques, because squared-distance functions to points are strongly convex along geodesics. We might, for example, seek to compute means or minimum enclosing balls for sets of matrices or phylogenetic trees. A fundamental challenge is the lack of any duality theory. Nonetheless, the convex geometry of Hadamard space is rich enough to support practical generalizations of the subgradient method, both in classical and incremental forms, supported by complexity analysis. In the particular case of CAT(0) cubical complexes (like tree space), practical algorithms can also rely on traditional cutting plane techniques. We also discuss the tractability of recognizing weighted means of finite sets in Hadamard spaces.
Keywords
- Convex Optimization
- Algorithms
- Non-smooth Optimization
Status: accepted
Back to the list of papers