Hidden convexity, optimization, and algorithms on rotation matrices

  • Kevin Shu
  • Alex L. Wang
  • Akshay Ramachandran
    • Categories Constrained Nonlinear Optimization, Other Topics, Semi-definite Programming Tags , , Short URL: https://optimization-online.org/?p=22654

    \(\)

    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.

    Article

    Download

    View Hidden convexity, optimization, and algorithms on rotation matrices