Finite convergence and minimizer extraction in moment relaxations with correlative sparsity

Federico Fuentes; Giovanni Fantuzzi

Finite convergence and minimizer extraction in moment relaxations with correlative sparsity

T0 review · 0 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper identifies rank conditions on moment matrices that certify finite convergence of sparse moment relaxations and yield minimizers.

desk verdict A genuinely weaker finite-convergence certificate for sparse moment relaxations, with a clean proof and an extraction algorithm; the soft spots are minor and don't threaten the main theorem. read the letter →

arxiv 2502.01410 v3 pith:2MQGUASY submitted 2025-02-03 math.OC

Giovanni Fantuzzi , Federico Fuentes This is my paper · ORCID

classification math.OC MSC 90C2290C2644A60

keywords moment-SOSrelaxationcorrelativesparsityfiniteconvergencetruncatedmomentproblemrunningintersectionpropertyflatextensionminimizerextractionpolynomialoptimization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes a sufficient condition under which the sparse moment relaxation of a polynomial optimization problem is exact, meaning its optimal value equals the true global minimum, and it explains how to recover minimizers from the relaxation's solution. The condition combines a running intersection property on the variable cliques with rank equalities on the moment matrices of each clique and on overlap submatrices. The argument solves a correlatively sparse version of the truncated moment problem: it shows the relaxation's moment vector is represented by an atomic measure whose atoms lie in the feasible set. When the relaxation is optimal, those atoms are minimizers. This matters because sparse relaxations are used to reduce the cost of moment-SOS hierarchies, and knowing that they can be certified exact at a finite order, along with a way to extract the optimizers, is what makes the approach practically useful.

What carries the argument

The load-bearing mechanism is the flat extension theorem for truncated moment sequences, applied clique by clique. For each clique, positive semidefinite moment and localizing matrices together with the rank equality $\mathrm{rank}\,M_{\Delta_i}^{\omega}(y)=\mathrm{rank}\,M_{\Delta_i}^{\omega-d_i}(y)$ produce a unique finitely atomic representing measure for the clique subvector, supported on the clique's constraint set. The running intersection property and the overlap rank condition $\mathrm{rank}\,M_{\Delta_i\cap\Delta_j}^{\omega}(y)=\mathrm{rank}\,M_{\Delta_i\cap\Delta_j}^{\omega-1}(y)$ then guarantee that these local measures have consistent marginals on clique intersections, so a measure assembly construction (an atomic version of the lemma in [11]) stitches them into a global atomic representing measure. The atomic decomposition $y=\sum_{k=1}^{r}\lambda_k\langle x_k\rangle_{\mathrm{sp}}^{2\omega}$ is the identity that yields both exactness and minimizer extraction.

What would settle it

A concrete calculation that would settle the claim: construct a correlatively sparse moment vector $y$ that satisfies the running intersection property, positive semidefiniteness, and all rank equalities in (1.4), but for which no atomic measure supported on the feasible set represents $y$. The paper's own example in section 5.3 performs the analogous test when the running intersection property fails; the same test with the property satisfied would falsify Theorem 1.1 if successful.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.1: given a correlatively sparse moment vector $y$, if the cliques satisfy the running intersection property and, for every clique $i$, the moment and localizing matrices are positive semidefinite, the rank of the clique moment matrix equals the rank of its truncated submatrix, and the rank of the overlap moment matrix equals the rank of its truncated overlap submatrix, then $y$ is represented by a finitely atomic measure supported on the feasible set, with at least as many atoms as the largest clique moment rank. Corollary 1.2 applies this to the optimal solution of the sparse moment relaxation: under the same conditions the relaxation is exact, and the atoms of the representing measure are minimizers of the original polynomial optimization problem. The paper also gives an explicit atomic assembly procedure that recovers a representing measure with maximal support, and shows via examples that the rank conditions are not redundant and that the running intersection property cannot be dropped.

Load-bearing premise

The proof assumes that the flat extension theorem applies to each clique subvector, converting algebraic rank equalities into genuinely atomic local measures; if that local representability failed, the global representing measure would not follow.

Editorial extensions

If this is right

If the rank conditions hold for an optimal solution of the sparse moment relaxation, the relaxation is exact at that order: $f_{\omega}^{*}=f^{*}$.
The extraction procedure returns at least $\max_i \mathrm{rank}\,M_{\Delta_i}^{\omega}(y)$ distinct minimizers of the original polynomial optimization problem.
The recovered representing measure has maximal support among all atomic representing measures for $y$, so its atoms do not depend on the clique ordering.
The sufficient condition generalizes earlier criteria because it does not require equal ranks across cliques, nor rank-one overlap matrices, so it can detect finite convergence where previous results fail.
Sparse relaxations can be exact at relaxation orders lower than those required by dense relaxations, as illustrated by an example and formulated as a conjecture.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the rank conditions can be checked a posteriori on any solved relaxation with standard linear algebra, so the test doubles as a cheap certificate of exactness in existing moment-SOS software.
Editorial inference: the maximal-support property means the extracted atoms give the full set of minimizers detectable at that relaxation order; solving the convex program (4.13) with a linear cost can produce sparser atomic representing measures, which may correspond to subsets of minimizers.
Editorial inference: the conjecture that sparse finite convergence never needs a higher order than dense convergence, if true, would strengthen the practical case for sparse hierarchies; the interpolator-polynomial argument in the paper is a first step but does not yet handle the overlap conditions.
Editorial inference: the same flat-extension-per-clique strategy is likely to extend to sparse polynomial matrix optimization, a direction the paper explicitly leaves open.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper delivers what it promises: a new sufficient condition for finite convergence and minimizer extraction in correlatively sparse moment relaxations, strictly weaker than the prior criteria in [18] and [11]. The key relaxation is dropping the requirement that all clique moment ranks take the same value, and only asking for the overlap rank condition (1.4b) along one RIP predecessor instead of all intersecting pairs. That is a real, useful advance, and the examples show cases where the older tests simply could not certify exactness.

The proof structure is the right one. Local flat extensions give atomic measures for each clique subvector; condition (1.4b) forces the marginals to agree on the needed overlaps; and the RIP-based gluing then assembles a global atomic measure. The construction in Section 4.1 is explicit and the maximal-support result in Proposition 4.1 is a nice bonus. The examples are worked out and illustrate both the power of the new criteria and the necessity of RIP. I checked the local representability step—the weakest assumption the reader flagged—and it is legitimate: (1.4a) with PSD is exactly the flat-extension hypothesis, so the clique subvectors do have atomic representing measures.

Soft spots are minor. Proposition 3.2 is stated without the PSD assumption, though its proof uses it; this is an imprecision, not a gap, since Theorem 1.1 assumes PSD up front. Example 5.2 verifies ranks on rounded numerical data from MOSEK, which is fine as an illustration but not a rigorous numerical certificate; the theory does not depend on it. The conjecture in Section 5.4 is speculative but clearly labeled as such. I do not see a load-bearing flaw.

Who should read this: anyone working on sparse moment-SOS hierarchies, polynomial optimization, or truncated moment problems. It will be a standard reference for the weaker finite-convergence criterion. My recommendation: send it to serious peer review. It deserves publication after minor revisions, mostly cleaning up the Proposition 3.2 statement and being explicit about the numerical rounding caveat.

Referee Report

0 major / 4 minor

Summary. The paper studies moment relaxations of polynomial optimization problems with correlative sparsity. It proves a new sufficient condition for the finite convergence of such relaxations: assuming the cliques satisfy a running intersection property, if for each clique the associated moment and localizing matrices are positive semidefinite and satisfy a flat-extension rank condition (1.4a), and if a rank condition on one overlap per clique (1.4b) holds, then the sparse moment vector admits an atomic representing measure supported on the feasible set, with at least as many atoms as the largest rank of the clique moment matrices. This yields exactness of the relaxation and extraction of minimizers (Corollary 1.2). The paper also gives an explicit atomic assembly algorithm in Section 4.1, proves maximality of the support of the resulting measure (Section 4.2), and illustrates the results with examples, including a non-RIP counterexample in Section 5.3.

Significance. If the result holds, it is a solid contribution to the sparse moment-SOS literature. The criterion generalizes previous finite-convergence results of Nie et al. and Lasserre by allowing different clique ranks and requiring the overlap condition only for one predecessor per clique. The explicit atomic construction and the maximal-support theorem are new and practically useful. The paper is well written and the proofs are mostly rigorous, relying on standard flat-extension theorems. The examples in Section 5 clearly demonstrate situations where previous criteria fail but the new one succeeds.

minor comments (4)

[Section 3.1, Proposition 3.2] The proposition as stated omits the positive semidefiniteness assumption (1.3) that is used in its proof via Lemma 3.1. Without PSD the statement is false: for n=2 with cliques {1} and {2}, omega=2, take y0=0, y_{01}=1, and all other entries zero. Then y_{Delta_1}=0 but y is nonzero, and the rank equalities (1.4) hold. The statement should include the PSD assumption, or the proof of Theorem 1.1 should instead observe directly that PSD plus y nonzero forces y0>0, hence every clique subvector is nonzero.
[Section 1.3 and surrounding text] There are several cross-reference typos: 'Theorem 1.2' in the paragraph after Corollary 1.2 and in Section 1.3 should be 'Corollary 1.2'; 'Theorem 3.3' in Section 3.2 should be 'Lemma 3.3'; and 'Theorem 3.1' in the proof of Proposition 3.2 should be 'Lemma 3.1'.
[Section 3.2 and Section 4.2] The uniqueness of the local clique measure mu_{Delta_i} follows from (1.4a) because d_i >= 1 implies rank M^omega_{Delta_i} = rank M^{omega-1}_{Delta_i} (by monotonicity of ranks of principal submatrices). This observation is used implicitly in the maximality proof in Section 4.2; it would be helpful to state it explicitly, since it justifies the claim that any other atomic representing measure has the same clique marginals.
[Section 5.2.1, equations (5.11)] The shaded submatrices indicating M^{omega-d_i}_{Delta_i}(y) are not visible in the plain-text rendering; the reader must infer the principal submatrix block. A textual description of the submatrix indices would improve readability.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: Theorem 1.1 and Corollary 1.2 rest on external flat-extension and RIP-gluing theorems, not on self-citations or fitted inputs.

full rationale

The derivation chain is self-contained in the relevant sense: the rank conditions (1.4a) and (1.4b) are checked on the SDP solution y, not fitted to force the desired conclusion, and the representing-measure conclusion follows from external classical results. In Section 3.2, the clique subvectors are represented atomically by invoking standard truncated-moment theorems (Curto-Fialkow and Laurent, cited as [4] and [12]), and Lemma 3.3 obtains consistent marginals from the uniqueness clause of the flat-extension theorem. The assembly of local measures into a global measure uses Lasserre's RIP-based gluing lemma [11, Lemma 6.4], which is independent of the authors and is further made algorithmic in Section 4.1 with an explicit atomic concatenation. Corollary 1.2 then derives f_omega^* = f^* from the atomic decomposition by a direct inequality, not by definition or by a fitted parameter. The only self-citation is [28], a survey reference in a background list, which is not load-bearing. The paper also honestly labels Conjecture 5.1 as a conjecture rather than a proved consequence. The sole imprecision is Proposition 3.2's statement omitting the PSD hypothesis that its proof uses; this is a statement-level correctness issue, not circularity, because Theorem 1.1 explicitly assumes PSD in (1.3). No equation in the paper reduces to its own inputs by construction, and no prediction is a renamed fit.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

There are no fitted parameters and no newly postulated entities. The central theorem depends on standard truncated moment theory and one prior gluing lemma, both external to the authors; the paper supplies an atomic construction of the gluing step, so the reliance is not circular.

assumptions (4)

standard math Flat extension theorem for truncated K-moment sequences (Curto-Fialkow, Laurent): positive semidefinite moment and localizing matrices plus rank equality imply a unique finitely atomic representing measure supported on the constraint set.
Invoked in Section 3.2 for each clique subvector y_Delta_i to obtain the local measures mu_Delta_i; the paper does not reprove this theorem.
standard math Lasserre's measure assembly lemma (Lasserre 2006, Lemma 6.4): under (RIP), local measures with consistent marginals on one predecessor clique can be assembled into a global measure.
Cited and used in Section 3.2; the paper also gives an independent atomic version of the gluing construction in Section 4.1.
standard math Richter's theorem and Tchakaloff-type arguments: any representing measure for a truncated moment sequence can be replaced by a finitely atomic representing measure.
Used in Section 3.2, citing [21, Satz 4] and [13, Theorem 5.9], to reduce arbitrary representing measures to atomic ones.
domain assumption The cliques can be reordered so that the running intersection property holds; if no reordering satisfies (RIP), the theorem is not claimed to apply.
Theorem 1.1 assumes (RIP) as a hypothesis, and Section 5.3 gives a counterexample showing the conclusion fails when (RIP) does not hold.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Finite convergence and minimizer extraction in moment relaxations with correlative sparsity." pith.science (2026). https://pith.science/paper/2MQGUASY

@misc{pith2026250201410,
  author       = {Pith},
  title        = {Pith review of: Finite convergence and minimizer extraction in moment relaxations with correlative sparsity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2MQGUASY}},
  note         = {Machine review of arXiv:2502.01410}
}

read the original abstract

We identify a new sufficient condition for the finite convergence of moment relaxations of polynomial optimization problems with correlative sparsity. This condition, which follows from a solution to a correlatively sparse version of the classical truncated moment problem, requires that certain moment matrices admit a flat extension and that the variable cliques underpinning the relaxation satisfy a "running intersection" property. We also describe an algorithm that, when these conditions are met, extracts at least as many minimizers for the original polynomial optimization problem as the largest rank of the moment matrices in its relaxation. Our results, along with the necessity of the running intersection property, are illustrated with examples.

Figures

Figures reproduced from arXiv: 2502.01410 by the authors.

**Figure 5.1.** Atom concatenation strategy for the example of section 5.2. An atom (a, b) for µ∆i is concatenated with an atom (c, d) for µ∆i+1 if b = c. Each colored paths leads to a different minimizer for (5.9), which is an atom of the representing measure µ in (5.15). 5.2.2. Detecting finite convergence. Using the moment matrices reported above, one can check that the rank conditions in (1.4a) and (1.4b) hold with rank Mω ∆1 … view at source ↗

**Figure 5.** [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 26 canonical work pages

[18]

J. Nie, Z. Qu, X. Tang, and L. Zhang. A characterization for tightness of the sparse moment-SOS hierarchy.Math. Program., 2025

work page 2025
[11]

J. B. Lasserre. Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim., 17(3):822–843, 2006. 16 FINITE CONVERGENCE IN SPARSE MOMENT RELAXATIONS

work page 2006
[1]

Baldi and B

L. Baldi and B. Mourrain. Exact moment representation in polynomial optimization. J. Symbolic Comput., 129:Paper No. 102403, 32, 2025. ISSN 0747-7171

work page 2025
[2]

Blekherman and L

G. Blekherman and L. Fialkow. The core variety and representing measures in the truncated moment problem.J. Operator Theory, 84(1):185–209, 2020. ISSN 0379- 4024

work page 2020
[3]

Blekherman and C

G. Blekherman and C. Riener. Symmetric non-negative forms and sums of squares. Discrete Comput. Geom., 65(3):764–799, 2021

work page 2021
[4]

R. E. Curto and L. A. Fialkow. The truncated complexK-moment problem.Trans. Amer. Math. Soc., 352(6):2825–2855, 2000

work page 2000
[5]

L. A. Fialkow. The truncatedK-moment problem: A survey. InOperator theory: the state of the art, volume 18 ofTheta Ser. Adv. Math., pages 25–51. Theta, Bucharest, 2016

work page 2016
[6]

L. A. Fialkow. The core variety of a multisequence in the truncated moment problem. J. Math. Anal. Appl., 456(2):946–969, 2017. ISSN 0022-247X

work page 2017

Show all 29 references

[7]

Gatermann and P

K. Gatermann and P. A. Parrilo. Symmetry groups, semidefinite programs, and sums of squares.J. Pure Appl. Algebra, 192(1-3):95–128, 2004

2004
[8]

Henrion and J.-B

D. Henrion and J.-B. Lasserre. Detecting global optimality and extracting solutions in GloptiPoly. InPositive polynomials in control, volume 312 ofLect. Notes Control Inf. Sci., pages 293–310. Springer, Berlin, 2005

2005
[9]

Korda, V

M. Korda, V. Magron, and R. Ríos-Zertuche. Convergence rates for sums-of-squares hierarchies with correlative sparsity.Math. Program., 209(1-2, Ser. A):435–473, 2025. ISSN 0025-5610

2025
[10]

J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11(3):796–817, 2001

2001
[12]

M. Laurent. Revisiting two theorems of Curto and Fialkow on moment matrices. Proc. Amer. Math. Soc., 133(10):2965–2976, 2005

2005
[13]

Laurent.Sums of squares, moment matrices and optimization over polynomials, volume 149 ofIMA Vol

M. Laurent.Sums of squares, moment matrices and optimization over polynomials, volume 149 ofIMA Vol. Math. Appl., pages 157–270. Springer, New York, 2009

2009
[14]

J. Löfberg. Pre-and post-processing sum-of-squares programs in practice.IEEE Trans. Automatic Control, 54:1007–1011, 2009

2009
[15]

Magron and J

V. Magron and J. Wang.Sparse polynomial optimization—theory and practice, vol- ume 5 ofSeries on Optimization and its Applications. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2023

2023
[16]

Miller, J

J. Miller, J. Wang, and F. Guo. Sparse polynomial matrix optimization. arXiv:2411.15479 [math.OC], 2024

2024 arXiv
[17]

MOSEK ApS.The MOSEK Optimization Toolbox for MATLAB, version 10.1.24,
[19]

P. A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Math. Program., 96(2, Ser. B):293–320, 2003

2003
[20]

M. Putinar. Positive polynomials on compact semi-algebraic sets.Indiana Univ. Math. J., 42(3):969–984, 1993

1993
[21]

H. Richter. Parameterfreie Abschätzung und Realisierung von Erwartungswerten.Bl. Deutsch. Ges. Versicherungsmath., 3:147–162, 1957. ISSN 0012-0200

1957
[22]

Riener, T

C. Riener, T. Theobald, L. J. Andrén, and J. B. Lasserre. Exploiting symmetries in SDP-relaxations for polynomial optimization.Math. Oper. Res., 38(1):122–141, 2013

2013
[23]

H. Waki, S. Kim, M. Kojima, and M. Muramatsu. Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim., 17(1):218–242, 2006

2006
[24]

J. Wang, H. Li, and B. Xia. A new sparse SOS decomposition algorithm based on term sparsity. InISSAC’19—Proceedings of the 2019 ACM International Symposium on Symbolic and Algebraic Computation, pages 347–354. ACM, New York, 2019

2019
[25]

J. Wang, V. Magron, and J.-B. Lasserre. TSSOS: a moment-SOS hierarchy that exploits term sparsity.SIAM J. Optim., 31(1):30–58, 2021

2021
[26]

J. Wang, V. Magron, and J.-B. Lasserre. Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension.SIAM J. Optim., 31(1):114–141, 2021

2021
[27]

J. Wang, V. Magron, J. B. Lasserre, and N. H. A. Mai. CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization.ACM Trans. Math. Software, 48(4):Art. 42, 26, 2022

2022
[28]

Zheng, G

Y. Zheng, G. Fantuzzi, and A. Papachristodoulou. Chordal and factor-width decom- positions for scalable semidefinite and polynomial optimization.Annu. Rev. Control, 52:243–279, 2021

2021
[2025]

URL https://docs.mosek.com/10.1/toolbox/index.html

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [18]

J. Nie, Z. Qu, X. Tang, and L. Zhang. A characterization for tightness of the sparse moment-SOS hierarchy.Math. Program., 2025

work page 2025

[2] [11]

J. B. Lasserre. Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim., 17(3):822–843, 2006. 16 FINITE CONVERGENCE IN SPARSE MOMENT RELAXATIONS

work page 2006

[3] [1]

Baldi and B

L. Baldi and B. Mourrain. Exact moment representation in polynomial optimization. J. Symbolic Comput., 129:Paper No. 102403, 32, 2025. ISSN 0747-7171

work page 2025

[4] [2]

Blekherman and L

G. Blekherman and L. Fialkow. The core variety and representing measures in the truncated moment problem.J. Operator Theory, 84(1):185–209, 2020. ISSN 0379- 4024

work page 2020

[5] [3]

Blekherman and C

G. Blekherman and C. Riener. Symmetric non-negative forms and sums of squares. Discrete Comput. Geom., 65(3):764–799, 2021

work page 2021

[6] [4]

R. E. Curto and L. A. Fialkow. The truncated complexK-moment problem.Trans. Amer. Math. Soc., 352(6):2825–2855, 2000

work page 2000

[7] [5]

L. A. Fialkow. The truncatedK-moment problem: A survey. InOperator theory: the state of the art, volume 18 ofTheta Ser. Adv. Math., pages 25–51. Theta, Bucharest, 2016

work page 2016

[8] [6]

L. A. Fialkow. The core variety of a multisequence in the truncated moment problem. J. Math. Anal. Appl., 456(2):946–969, 2017. ISSN 0022-247X

work page 2017