This paper studies hidden convexity properties associated with constrained optimization problems over the set of rotation matrices $\text{ SO}(n)$. Such problems are nonconvex due to the constraint $X \in \text{ SO}(n)$. Nonetheless, we show that certain linear images of $\text{ 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 $\text{ SO}(n)$ is convex and that the projection of $\text{ SO}(n)$ onto its strict upper triangular entries is convex. These results allow us to construct exact convex reformulations for constrained optimization problems over $\text{ SO}(n)$ with a single constraint or with constraints defined by low-rank matrices. Both of these results are optimal in a formal sense.
Categories: math.OC
