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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures

Manuel Wiedmer, Lucas Slot
Numerical Algebra Control and Optimization
Advanced Optimization Algorithms Research
article

Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures

Manuel Wiedmer, Lucas Slot
article en

Abstract

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 $.

Numerical Algebra Control and OptimizationVol. 16(0)
ETH Zurich (CH)
Openalex Percentile: Top 77%
Advanced Optimization Algorithms Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures — Manuel Wiedmer, Lucas Slot · Numerical Algebra Control and Optimization (2024) | TGRS Research Map | TGRS