Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures
Let $ \mathbf{X} \subseteq \mathbb{R}^n $ be a closed set, and consider the problem of computing the minimum $ f_{\min} $ of a polynomial $ f $ on $ \mathbf{X} $. Given a measure $ \mu $ supported on $ \mathbf{X} $, Lasserre (SIAM J. Optim. 21(3), 2011) proposes a decreasing sequence of upper bounds on $ f_{\min} $, each of which may be computed by solving a semidefinite program. When $ \mathbf{X} $ is compact, these bounds converge to $ f_{\min} $ under minor assumptions on $ \mu $. Later, Lasserre (Math. Program. 190, 2020) introduces a related, but far more economical sequence of upper bounds which rely on the push-forward measure of $ \mu $ by $ f $. While these new bounds are weaker a priori, they actually achieve similar asymptotic convergence rates on compact sets. In this work, we show that no such free lunch exists in the non-compact setting. While convergence of the standard bounds to $ f_{\min} $ is guaranteed when $ \mathbf{X} = \mathbb{R}^n $ and $ \mu $ is a Gaussian distribution, we prove that the bounds relying on the push-forward measure fail to converge to $ f_{\min} $ in that setting already for polynomials of degree $ 6 $.
Authors
- Manuel Wiedmer
- Lucas Slot (ORCID: https://orcid.org/0000-0003-3790-492X)
Institutions
- ETH Zurich (CH)
Publication Details
- Journal
- Numerical Algebra Control and Optimization
- Published
- 2024-09-09
- DOI
- https://doi.org/10.3934/naco.2024045
- Primary Topic
- Advanced Optimization Algorithms Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00