Convex relaxations for large-scale graphically structured nonconvex problems with spherical constraints: An optimal transport approach

Robin Kenis, Emanuel Laude, Panagiotis PatrinosarXiv 2023 · DOI · arXiv

Abstract

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.

Introduction

Many real-world optimization problems involve variables constrained to manifolds rather than flat Euclidean space. A classic example is the unit sphere ($S^m$): in satellite imaging (InSAR), data is represented as phases (points on a circle); in robotics (SLAM), orientations are represented as rotation matrices. When these variables are linked together in a graphical structure—such as pixels in a grid or poses in a trajectory—the resulting optimization problem is usually nonconvex and nonsmooth.

Traditional global optimization tools, like the Lasserre moment hierarchy, are theoretically powerful but practically limited for large-scale tasks because their computational cost explodes as the number of variables increases. Conversely, local optimization methods often converge to poor local minima. This paper proposes a "middle ground": a convex relaxation that is computationally tractable for millions of variables while maintaining high accuracy by exploiting the underlying geometry of the manifold.

Methodology

The proposed framework exploits the partially separable structure of the problem to bypass the curse of dimensionality. Instead of analyzing the entire high-dimensional space at once, the method focuses on local interactions through several key steps:

  1. Local Marginal Polytope Relaxation: The problem is lifted into the space of probability measures, restricted to local marginals (measures on single variables and pairs of connected variables).
  2. Optimal Transport (OT) Duality: Coupling terms between variables are rephrased as an optimal transport problem. Specifically, the authors use Kantorovich–Rubinstein duality to transform the primal problem into a dual problem involving Lipschitz continuous functions. This allows the handling of non-polynomial, non-smooth costs like geodesic distance.
  3. Polynomial Subspace Approximation: To make the infinite-dimensional dual problem solvable, these functions are approximated using spherical harmonics (polynomials on a sphere).
  4. Sum-of-Squares (SOS) Certificates: The requirement that a polynomial must be non-negative is converted into a set of Linear Matrix Inequalities (LMIs), which can be solved efficiently using standard semidefinite programming (SDP) solvers.

Experimental Results

The approach was evaluated on several distinct tasks, demonstrating both accuracy and scalability:

  • Imaging Tasks: In synthetic $S^1$ denoising and real-world Vesuvius InSAR data, the approach achieved very small relative duality gaps (ranging from $10^{-2}$ to $10^{-4}$), indicating that the relaxation is very close to the true global optimum.
  • Chromaticity Denoising: The method successfully handled denoising and inpainting tasks on $S^2$ (color space), demonstrating a significantly lower memory footprint than classical sparse moment relaxations.
  • Pose Graph Optimization (PGO): For standard SLAM benchmarks, the relaxation provided a high-quality initialization. When followed by local refinement, the results were nearly identical to the ground truth, even in noisy scenarios.

Key Insights

  • Natural Convexification: The "Degree 1" relaxation preserves the underlying manifold geometry even at the lowest level of the hierarchy, unlike naive methods that simply flatten the sphere into a square.
  • Vanishing Duality Gap: The authors provide a mathematical proof that as the degree of the polynomial approximation increases, the gap between the relaxation and the true solution vanishes at a rate of $O(1/n)$.
  • Structure over Size: Exploiting graph sparsity allows the method to scale to problems with millions of variables that were previously untouchable by moment-based methods.

Limitations and Future Work

While the relaxation is exact for tree-structured graphs, it is not necessarily tight for graphs with complex loops. For problems like SLAM, the relaxation often requires a local "polishing" step to reach the final solution. Future work will involve developing specialized solvers that further exploit the specific structure of these manifold-constrained problems to reduce the computational overhead of SDP solvers as the polynomial degree increases.

Summary updated

Abstract

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.
BibTeX
@misc{kenis2023convex,
  author = {Robin Kenis and Emanuel Laude and Panagiotis Patrinos},
  title = {{Convex relaxations for large-scale graphically structured nonconvex problems with spherical constraints: An optimal transport approach}},
  year = {2023},
  eprint = {2308.00079},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2308.00079},
}
Figure