1422. Geodesic Programs
Invited abstract in session WC-35: Cardinality-constrained optimization with guarantees, stream Continuous and mixed-integer nonlinear programming: theory and algorithms.
Wednesday, 12:30-14:00Room: Michael Sadler LG15
Authors (first author is the speaker)
| 1. | Johannes Manstein
|
| Interdisciplinary Center for Scientific Computing, Universität Heidelberg |
Abstract
The classical simplex algorithm solves linear programs in Euclidean spaces by moving along the edges of a polyhedral feasible set. We explore an extension to a class of problems on Riemannian manifolds, which we call geodesic programs. In this setting, the feasible set is a convex polyhedron defined using the exponential map, so straight lines in the Euclidean setting are replaced by geodesics. We analyze the types of manifolds where this approach is applicable, the classes of objective functions and polyhedra for which a global minimizer can be found, and compare the properties of geodesic programs with classical linear programs. Finally, we describe an explicit simplex algorithm adapted to the Riemannian setting and examine its behavior.
Keywords
- Convex Optimization
- Programming, Linear
- Algorithms
Status: accepted
Back to the list of papers