  This paper initiates a systematic development of a theory of non-commutative
optimization. It aims to unify and generalize a growing body of work from the
past few years which developed and analyzed algorithms for natural geodesically
convex optimization problems on Riemannian manifolds that arise from the
symmetries of non-commutative groups. These algorithms minimize the moment map
(a non-commutative notion of the usual gradient) and test membership in null
cones and moment polytopes (a vast class of polytopes, typically of exponential
vertex and facet complexity, which arise from this a priori non-convex,
non-linear setting). This setting captures a diverse set of problems in
different areas of computer science, mathematics, and physics. Several of them
were solved efficiently for the first time using non-commutative methods; the
corresponding algorithms also lead to solutions of purely structural problems
and to many new connections between disparate fields.
  In the spirit of standard convex optimization, we develop two general methods
in the geodesic setting, a first order and a second order method, which
respectively receive first and second order information on the "derivatives" of
the function to be optimized. These in particular subsume all past results. The
main technical work goes into identifying the key parameters of the underlying
group actions which control convergence to the optimum in each of these
methods. These non-commutative analogues of "smoothness" are far more complex
and require significant algebraic and analytic machinery. Despite this
complexity, the way in which these parameters control convergence in both
methods is quite simple and elegant. We show how to bound these parameters and
hence obtain efficient algorithms for null cone membership in several concrete
situations. Our work points to intriguing open problems and suggests further
research directions.
