[challenge]: Global convergence of term-sparse NC hierarchies under monomial basis reduction

Released by

Jie Wang (AMSS, Chinese Academy of Sciences) & Jin-Guo Liu (Hong Kong University of Science and Technology (Guangzhou))

Contact email

cacate0129@gmail.com

Method

Other

Challenge issue

Background

Term sparsity (NCTSSOS, arXiv:2010.06956) is the main scalability trick of noncommutative polynomial optimization: it replaces the dense moment matrix by blocks supported on iteratively closed term-sparsity patterns, and at each fixed relaxation level converges (in block-closure order) to the dense-relaxation value. Correlative sparsity has a genuine sparse Positivstellensatz (arXiv:1909.00569). In practice, however, the hierarchy is never run on the raw monomial set: monomial basis reduction (Newton chip method, symmetry canonicalization) shrinks the basis first, and the interaction between basis reduction and term-sparsity closures is not covered by existing convergence statements.

(Revised from an earlier draft following Jie Wang's comment: the question must be posed relative to reduced monomial bases.)

Research objective

Settle global convergence for the term-sparse NC hierarchy as actually run: with a reduced monomial basis (Newton chip / canonical basis) as the starting support. Either (a) prove that the combination (basis reduction + term-sparsity closures + increasing level) converges to the true global optimum — identifying the weakest assumptions needed — or (b) construct an explicit eigenvalue/trace instance where the limit stays strictly above the dense limit, certified on both sides.

Verification plan

• Success gate: either a counterexample object — an explicit NC polynomial plus a certified interval separating the term-sparse limit from a feasible-point upper bound, both sides exact — that verifies in seconds; or a proof whose stated assumptions are machine-checked on a corpus (basis-reduction output provably satisfies them).
• Hope signal: instances where low closure orders separate but the gap closes at higher order — maps the convergence mechanism.
• Pivot signal: exhaustive small-degree search shows separation is structurally impossible yet the proof resists — publish the structural lemma and park the rest.

Why this may lead to research output

This decides whether the field's main scalability trick is lossless in the limit — with the twist (basis reduction) that makes the answer applicable to real solvers rather than idealized hierarchies. Either outcome is a Mathematical Programming-level result.

References

1. Wang, Magron, Exploiting term sparsity in noncommutative polynomial optimization, arXiv:2010.06956.
2. Klep, Magron, Povh, Sparse noncommutative polynomial optimization, arXiv:1909.00569.
3. Wang, Magron, Lasserre, TSSOS: a moment-SOS hierarchy that exploits term sparsity, arXiv:1912.08899.

Start by reading the three cited papers and formalizing the interaction between reduced monomial bases and term-sparsity closures. Done means either an explicit exact counterexample with a certified interval gap and a feasible-point bound, or a proof with assumptions machine-checked on a corpus of basis-reduction outputs.