2024-04-29
Hidden convexity, optimization, and algorithms on rotation matrices
Publication
Publication
This paper studies hidden convexity properties associated with constrained optimization problems over the set of rotation matrices SO(n). Such problems are nonconvex due to the constraint X∈SO(n). Nonetheless, we show that certain linear images of SO(n) are convex, opening up the possibility for convex optimization algorithms with provable guarantees for these problems. Our main technical contributions show that any two-dimensional image of SO(n) is convex and that the projection of SO(n) onto its strict upper triangular entries is convex. These results allow us to construct exact convex reformulations for constrained optimization problems over SO(n) with a single constraint or with constraints defined by low-rank matrices. Both of these results are optimal in a formal sense.
| Additional Metadata | |
|---|---|
| doi.org/10.48550/arXiv.2304.08596 | |
| Optimization for and with Machine Learning , Towards a Quantitative Theory of Integer Programming | |
| , | |
| Organisation | Networks and Optimization |
|
Ramachandran, A., Heinrich, M., & Wang, A. L. (2024). Hidden convexity, optimization, and algorithms on rotation matrices. doi:10.48550/arXiv.2304.08596 |
|
