2024-07-01
Hidden convexity, optimization, and algorithms on rotation matrices
Publication
Publication
Mathematics of Operations Research , Volume 50 - Issue 2 p. 1454- 1477
This paper studies hidden convexity properties associated with constrained optimization problems over the set of rotation matrices SO(n). Such problems are nonconvex because of 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 maximal in a formal sense.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.1287/moor.2023.0114 | |
| Mathematics of Operations Research | |
| Optimization for and with Machine Learning | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Ramachandran, A., Shu, K., & Wang, A. (2024). Hidden convexity, optimization, and algorithms on rotation matrices. Mathematics of Operations Research, 50(2), 1454–1477. doi:10.1287/moor.2023.0114 |
|
| See Also |
|---|
