Solving Moment and Polynomial Optimization Problems on Sobolev Spaces

Didier Henrion, Alessandro RudiSIAM J. Optim 2025 · DOI

TL;DR

This paper introduces a novel framework for solving polynomial optimization problems (POPs) on Sobolev spaces, extending the powerful moment-SOS hierarchy to infinite-dimensional settings. The authors develop a method to handle these complex problems by reformulating them in the space of Fourier coefficients, enabling the use of semidefinite programming techniques for global convergence guarantees.

What Problem Does This Paper Address?

Polynomial optimization problems (POPs) are a fundamental class of optimization problems with wide-ranging applications. The moment-SOS hierarchy, a powerful tool for solving POPs, has traditionally been limited to finite-dimensional settings. However, many real-world problems, particularly those arising in calculus of variations and partial differential equations, are naturally formulated on infinite-dimensional function spaces, such as Sobolev spaces. These infinite-dimensional POPs pose significant challenges due to their inherent complexity. This paper addresses the critical need to extend the capabilities of the moment-SOS hierarchy to tackle these challenging infinite-dimensional POPs on Sobolev spaces, aiming to provide a computationally tractable approach with global convergence guarantees.

Methods

The core of the paper's contribution lies in its innovative use of Fourier embedding to transform infinite-dimensional problems into a more manageable form. The authors leverage harmonic analysis to reformulate the moment problem on Sobolev spaces into a problem on the space of Fourier coefficients. This transformation allows them to define inner and outer semidefinite approximations of the Sobolev moment cone. These approximations are crucial for constructing the infinite-dimensional moment-SOS hierarchy. The paper then details how these approximations can be used to solve both "harmonic" and "algebraic" Sobolev POPs. For harmonic POPs, the problem is reduced to a linear problem on a truncated cone of moments. For algebraic POPs, which can involve non-linearities in function values and derivatives, the approach also relies on Fourier coefficients and moment hierarchies. The paper also discusses solution recovery, showing how to reconstruct the representing measure from its moments.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Infinite and Finite Dimensions: The most significant insight is the successful translation of infinite-dimensional moment problems on Sobolev spaces into a form amenable to finite-dimensional semidefinite programming techniques via Fourier coefficients. This is a major step towards solving complex optimization problems that were previously intractable.
  • Sobolev Moment Cone Approximations: The development of inner and outer semidefinite approximations for the Sobolev moment cone is a key technical contribution. These approximations are essential for constructing the moment-SOS hierarchy and provide a way to bound the true solution.
  • Harmonic vs. Algebraic POPs: The paper clearly distinguishes between "harmonic" POPs (where the objective function's harmonic degree is finite) and "algebraic" POPs (which can involve non-linearities in function values and derivatives, potentially leading to infinite harmonic degrees). This distinction is important for tailoring the solution approach.
  • Global Convergence Guarantees: A critical outcome of this framework is the provision of global convergence guarantees for solving these infinite-dimensional POPs. This is a significant advantage over many heuristic or local optimization methods.

Key Results

  • The paper establishes an equivalence between solving the Sobolev moment problem on a Sobolev ball and solving a corresponding Fourier moment problem on an ellipsoid.
  • It provides a method for constructing semidefinite representable outer and inner approximations of the Sobolev moment cone.
  • The paper demonstrates how to apply the moment-SOS hierarchy to solve both harmonic and algebraic Sobolev POPs, providing lower and upper bounds that converge to the true optimal value.
  • The authors present examples illustrating the application of their framework, including a harmonic Sobolev POP and an algebraic Sobolev POP, showing how the method can find global minimizers.

Limitations and Future Work

  • Computational Complexity: While the framework provides theoretical guarantees, the practical computational complexity of solving these infinite-dimensional problems, even with approximations, is a significant consideration. The size of the semidefinite programs can grow rapidly with the relaxation degrees.
  • General Domains and Spaces: The current work focuses on Sobolev spaces on the torus. The authors suggest that the approach can be generalized to other spaces like Sobolev spaces on general domains, Besov or Triebel-Lizorkin spaces, and other quasi-Banach spaces with Schauder bases.
  • Applications: The paper highlights that applications to nonlinear calculus of variations problems and optimal control involving nonlinear partial differential equations remain to be investigated. This is a promising avenue for future research.
  • Solution Recovery: While the paper discusses solution recovery, extending techniques like the Christoffel-Darboux kernel to Sobolev spaces for approximating the support of a measure is mentioned as an interesting area for future work.

Summary updated

BibTeX
@article{henrion2025solving,
  author = {Didier Henrion and Alessandro Rudi},
  title = {{Solving Moment and Polynomial Optimization Problems on Sobolev Spaces}},
  journal = {SIAM J. Optim.},
  year = {2025},
  doi = {10.1137/24m163133x},
}
Figure