  In this paper we derive a moment relaxation for large-scale nonsmooth
optimization problems with graphical structure and spherical constraints. In
contrast to classical moment relaxations for global polynomial optimization
that suffer from the curse of dimensionality we exploit the partially separable
structure of the optimization problem to reduce the dimensionality of the
search space. Leveraging optimal transport and Kantorovich--Rubinstein duality
we decouple the problem and derive a tractable dual subspace approximation of
the infinite-dimensional problem using spherical harmonics. This allows us to
tackle possibly nonpolynomial optimization problems with spherical constraints
and geodesic coupling terms. We show that the duality gap vanishes in the limit
by proving that a Lipschitz continuous dual multiplier on a unit sphere can be
approximated as closely as desired in terms of a Lipschitz continuous
polynomial. The formulation is applied to sphere-valued imaging problems with
total variation regularization and graph-based simultaneous localization and
mapping (SLAM). In imaging tasks our approach achieves small duality gaps for a
moderate degree. In graph-based SLAM our approach often finds solutions which
after refinement with a local method are near the ground truth solution.

Optimization and Control