Global Extendability of Local Atoms in Sparse Moment Relaxations
Abstract
Moment relaxations provide lower bounds for polynomial optimization problems, while their moment matrices also carry information about solutions. For correlatively sparse relaxations, we study whether atomic candidates extracted from selected clique blocks reveal part of a global minimizer, even when the remaining blocks do not admit the same extraction certificate. We use simplicial regularity: the minimal face of a selected block in the pseudo-moment matrix cone is simplicial and generated by finite point evaluations. A value-exact chain example illustrates how a rank-one clique can identify coordinates shared by every global minimizer. We then give sufficient conditions for global extendability. If the relaxation is value exact and a selected block has maximum rank over the optimal face and satisfies simplicial regularity, then at least one of its atomic candidates is globally extendable. When all candidates satisfy the assigned clique constraints, they give a locally feasible atomic representation through the full relaxation degree. Every positive-weight atom in such a representation minimizes its clique objective given its boundary value. If the relaxation is value exact and the boundary moment block has maximum rank one over the optimal face, every such atom is globally extendable. Examples show why the additional hypotheses are needed, and numerical experiments on unicycle trajectory optimization demonstrate the effectiveness of progressive extraction and fixing.
Related
- Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs
- Benign Degeneracy for First-Order Methods in Exact Boolean Moment-SOS Relaxations
- Sparse entropic quadrature for moment equations
- The Moment Method for Computing Real Points of Sparse Polynomial Systems
- Robust Global Testing for Mean Functions in Sparse and Dense Functional and Longitudinal Data
BibTeX
@misc{sun2026global,
title = {{Global Extendability of Local Atoms in Sparse Moment Relaxations}},
author = {Haoran Sun},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17371},
eprint = {2610.17371},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17371},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Global Extendability of Local Atoms in Sparse Moment Relaxations
AU - Haoran Sun
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.17371
UR - https://arxiv.org/abs/2610.17371
AB - Moment relaxations provide lower bounds for polynomial optimization problems, while their moment matrices also carry information about solutions. For correlatively sparse relaxations, we study whether atomic candidates extracted from selected clique blocks reveal part of a global minimizer, even when the remaining blocks do not admit the same extraction certificate. We use simplicial regularity: the minimal face of a selected block in the pseudo-moment matrix cone is simplicial and generated by finite point evaluations. A value-exact chain example illustrates how a rank-one clique can identify coordinates shared by every global minimizer. We then give sufficient conditions for global extendability. If the relaxation is value exact and a selected block has maximum rank over the optimal face and satisfies simplicial regularity, then at least one of its atomic candidates is globally extendable. When all candidates satisfy the assigned clique constraints, they give a locally feasible atomic representation through the full relaxation degree. Every positive-weight atom in such a representation minimizes its clique objective given its boundary value. If the relaxation is value exact and the boundary moment block has maximum rank one over the optimal face, every such atom is globally extendable. Examples show why the additional hypotheses are needed, and numerical experiments on unicycle trajectory optimization demonstrate the effectiveness of progressive extraction and fixing.
ER -