Pith. sign in

REVIEW 3 major objections 4 minor 69 references

Sparse Noncommutative Polynomial Optimization

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read A sparse Positivstellensatz for noncommuting variables makes semidefinite hierarchies converge with cluster-sized matrices.

desk verdict Real new sparse theory with a genuine but likely fixable gap in the main proof; worth refereeing, not citable as-is. read the letter →

arxiv 1909.00569 v3 pith:NHD2D5SE submitted 2019-09-02 math.OC math.AG

Igor Klep , Victor Magron , Janez Povh This is my paper · ORCID
classification math.OCmath.AG MSC 90C2247N1013J10
keywords noncommutativepolynomialoptimizationsparsitysemidefiniteprogrammingPositivstellensatzeigenvaluetraceGNSconstructionrunningintersectionproperty
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

The paper proves a sparse version of the noncommutative Positivstellensatz: if a polynomial in noncommuting variables is strictly positive on an operator semialgebraic set, and the variables are grouped into overlapping clusters satisfying boundedness and the running intersection property, then the polynomial lies in the sparse quadratic module generated by the cluster polynomials. From this representation theorem the authors derive semidefinite programming hierarchies whose lower bounds converge to the true minimal eigenvalue and to the type-II1 minimal trace of a noncommutative polynomial. The practical upshot is that the semidefinite programs are indexed by words in each cluster, so their size grows with cluster sizes rather than with the full exponential count in the total number of variables. A sparse GNS construction is also provided, which extracts an optimizing matrix tuple and vector when flatness and irreducibility hold.

What carries the argument

The load-bearing mechanism is amalgamation of $C^*$-algebras with specified states, applied to the GNS representations of the cluster linear functionals. Each cluster functional $L_k$ gives a Hilbert space and a tuple of operators $\hat A^k$ realizing $L_k$ on $\mathbb{R}\langle X(I_k)\rangle$; the running intersection property — each new cluster meets the union of its predecessors inside one predecessor — guarantees that the overlaps of clusters correspond to common subalgebras, and the state-preserving amalgamation theorem glues these into one operator tuple $A$ on a Hilbert space, with a cyclic vector $w$ such that $L(f)=\langle f(A)w,w\rangle$. The sparse quadratic module $M(S)_{\mathrm{sparse}} = M(S)_1 + \cdots + M(S)_p$ is the algebraic object being characterized. The running intersection property (2.7) is what makes the amalgamated representation well-defined; Example 3.4 shows that without it the representation can fail.

What would settle it

Compute the sparse hierarchy bounds for a strictly positive noncommutative polynomial on the noncommutative polydisc with chain clusters $I_k = \{k, k+1\}$ and compare them with the dense bounds or the true minimum; if any relaxation order shows a strict gap that never closes, then Theorem 3.3 or Corollary 5.9 fails. A search over random sparse polynomials with such clusters is a concrete test.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 3.3, a sparse analogue of the Helton-McCullough archimedean Positivstellensatz. Under Assumptions 2.3 and 2.4 — an archimedean bound on the tuple, a cluster decomposition of the objective and constraints, and the running intersection property — strict positivity of $f$ on $D_\infty^S$ is equivalent to membership in the sparse quadratic module $M(S)_{\mathrm{sparse}}$. This single result powers Corollaries 5.9 and 6.6, which state that the sparse eigenvalue and trace hierarchies converge to $\lambda_{\min}(f,S)$ and $\operatorname{tr}_{\min}(f,S)_{\mathrm{II}_1}$ respectively, at relaxation orders whose semidefinite matrices are built from cluster words. The paper also shows the limits of the approach: there is no sparse analogue of the unconstrained sums-of-hermitian-squares theorem, and without the running intersection property positivity alone does not force sparse membership, as Example 3.4 demonstrates.

Load-bearing premise

The whole convergence argument rests on Assumption 2.4(iii), the running intersection property relating the clusters; if that condition fails, positivity does not imply membership in the sparse module, as Example 3.4 shows with clusters {1,2}, {2,3}, {1,3}.

Editorial extensions

If this is right

  • Sparse eigenvalue relaxations converge to $\lambda_{\min}(f,S)$, so a many-variable objective that decomposes into small clusters can be certified by solving much smaller SDPs.
  • Sparse trace relaxations converge to the type-II1 trace minimum, matching the dense theory's target rather than merely approximating finite-matrix traces.
  • When the optimal Hankel and localizing matrices satisfy flatness and irreducibility, the SparseGNS algorithm outputs an explicit tuple of symmetric matrices and a unit vector attaining the optimum.
  • The unconstrained sparse eigenvalue bound is always a valid lower bound but can be strictly below the true value, because sparse sums of hermitian squares do not exhaust sparse positive polynomials (Lemma 5.2).

Reading between the lines

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

  • For clusters arising from chordal extensions of a correlation graph, the running intersection property should hold automatically, so the practical bottleneck is likely to be verifying it for user-supplied clusterings rather than the SDP size itself.
  • The same amalgamation proof strategy should extend to other positivity certificates, such as sparse convex Positivstellensätze and representations with noncommutative rational functions, giving design principles for future sparse hierarchies.
  • The strictness phenomenon in the unconstrained case suggests that users should check whether the objective is itself a sparse sum of hermitian squares before trusting the sparse bound; if not, merging clusters could improve the bound.
  • A randomized search for flat optimal solutions, already natural in dense noncommutative optimization, could make SparseGNS fully automatic; the paper indicates this route but does not implement it.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper introduces the first systematic treatment of sparsity in noncommutative polynomial optimization. It states a sparse Positivstellensatz (Theorem 3.3) under the running intersection property (RIP), builds a sparse GNS construction for extracting optimizers (Theorem 4.2), and derives converging SDP hierarchies for eigenvalue optimization (Corollary 5.9) and trace optimization (Corollary 6.6). The sparse hierarchies have matrix sizes controlled by the cluster sizes rather than by the full number of variables. The paper also gives counterexamples showing that sparsity alone is not enough (Example 3.4) and that there is no sparse analog of the Helton–McCullough SOHS theorem (Lemma 5.2), and it reports numerical experiments with the NCSOStools implementation.

Significance. If correct, the sparse Positivstellensatz and the convergent hierarchies are a substantial advance: they extend the commutative sparse SOS theory of Lasserre and Waki et al. to a noncommutative setting where dense relaxations become intractable very quickly. The companion extraction results and the explicit counterexamples clarify the exact role of RIP and irreducibility. The paper is also careful to derive the sparse Positivstellensatz from the dense Helton–McCullough theorem and operator-algebraic amalgamation, with no fitted parameters. The main obstacle is a gap in the proof of the central Theorem 3.3 and a parallel gap in Proposition 6.5; these must be repaired before the convergence claims can be considered established.

major comments (3)
  1. [Section 3, proof of Theorem 3.3, p = 2 case] The proof applies Theorem 3.1 with A = B(H(I1 ∩ I2)) and claims that there are 'canonical embeddings' ι_k : B(H(I1 ∩ I2)) → B(H(Ik)) satisfying ι_k(Â12_i) = Âk_i and that B(H(I1 ∩ I2)) contains the algebra generated by the Â12_i as a dense subset. Both assertions are false in general. For example, if I1 ∩ I2 = {1} and L12 makes X1 have two-point spectrum with H(I1 ∩ I2) two-dimensional, the algebra generated by Â12_1 is the diagonal algebra, not B(H(I1 ∩ I2)), so the density claim fails. Moreover, even when H(I1 ∩ I2) is a cyclic subspace of H(Ik), the operator Âk_i is block diagonal with respect to this subspace and its action on the complement is arbitrary; a unital *-homomorphism from B(H(I1 ∩ I2)) into B(H(Ik)) that sends Â12_i to Âk_i need not exist. Consequently, the equality j1(Â1_i) = j2(Â2_i) used to define the amalgamated tuple A is unjustified. The same defective step is invoked in the induction step for p > 2. Since Theorem 3.3 is the load-bearing input to Corollaries 5.9 and 6.6, the convergence claims are not yet supported. A likely repair is to amalgamate the universal C*-algebra generated by the intersection variables (with the state induced by L12) rather than the full B(H(I1 ∩ I2)).
  2. [Section 6, proof of Proposition 6.5] The proof of the tracial sparse Positivstellensatz has the same amalgamation problem as Theorem 3.3. After the Hahn–Banach separation step, the GNS construction is said to yield operator algebras A_k and A_jk with tracial states, and then the proof simply says 'Now amalgamate in the category of von Neumann algebras'. No state-preserving (trace-preserving) embeddings of the intersection von Neumann algebra into each A_k are constructed, and without such embeddings the amalgamation theorem does not apply. The fact that the GNS representations of tracial states give finite von Neumann algebras does not by itself identify the intersection subalgebra inside each A_k in a way that makes the amalgamation possible. Since Corollary 6.6 depends on Proposition 6.5, this gap must also be closed.
  3. [Section 4, proof of Theorem 4.2] The proof of Theorem 4.2 is written out in detail only for p = 2, and the general case is dismissed with 'the general case then follows by a simple inductive argument'. This is not sufficient, especially because the hypotheses (H1) and (H2) are stated pairwise. For p > 2, one must show that the pairwise operator algebras A(Ij ∩ Ik) and the pairwise embeddings are compatible on triple intersections, and that the constructed amalgamated representation satisfies (4.3) on the sum of all R⟨X(Ij)⟩. As written, the extraction results for p > 2, including Algorithm 4.6 and Proposition 5.11/Corollary 5.13, are not fully established. This does not affect the convergence theorems directly, but it is a claimed contribution of the paper.
minor comments (4)
  1. [Section 7, Tables 1–3] The numerical experiments are described only through aggregate SDP sizes and timings; no raw SDP data, solver tolerances, or scripts are provided. This makes the reported 'surprisingly' equal bounds in Table 2 difficult to audit. It would be helpful to state the solver precision settings and to make the implementation publicly available in a reproducible form.
  2. [Algorithm 4.6, line 10] The instruction 'Compute an orthogonal P such that P^{-1}χ_k^i P = Â12_i' presupposes that the intersection algebra is the full matrix algebra; this is guaranteed only under (H2). The sentence should state explicitly that the line is executed only when (H2) has been verified.
  3. [Section 5.1, SDP (5.7)] The domain of the linear functional L is written as R⟨X(I1)⟩2d + ⋯ + R⟨X(Ip)⟩2d. Since the decomposition f = f1 + ⋯ + fp is not necessarily unique, the objective function ∑⟨Md(L,Ik), G_fk⟩ depends on the chosen Gram matrices G_fk. The text does not discuss this dependence or specify how the decomposition is fixed.
  4. [References] Reference [GdLL19] is listed as 'to appear'; it should be updated to the published version. Also, some numerical entries such as Example 5.10 are reported with many decimals but no provenance; a note on numerical rounding would improve reproducibility.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the sparse Positivstellensatz is derived from the dense Helton–McCullough theorem and external amalgamation results, not assumed; self-citations are standard background and do not carry the sparse target claim.

full rationale

The load-bearing claim is Theorem 3.3: under Assumptions 2.3 and 2.4, strict positivity on D∞_S forces membership in the sparse quadratic module M(S)sparse. Its proof does not assume the conclusion. It starts from the Hahn–Banach separation of f from M(S)sparse, applies the dense GNS representation separately on each cluster, and then amalgamates the resulting operator algebras using Theorem 3.1, which is cited to Blackadar and Voiculescu. The later convergence results, Corollaries 5.9 and 6.6, invoke Theorem 3.3 in the standard way: for λ below λmin(f,S), strict positivity implies f−λ ∈ M(S)sparse, hence feasibility of the sparse SDP; weak duality gives the reverse inequality. This is not a definitional identity because the sparse quadratic module is strictly smaller than the dense module, as Example 3.4 shows. No parameter is fitted and then renamed as a prediction; the SDP bounds are defined independently of the values they are claimed to approximate. The paper cites the authors' own book [BKP16] for standard dense GNS facts, dense convergence theorems, and NCSOStools software, but these are prior background results with stated assumptions that do not include the sparse Positivstellensatz, so under the stated rules they count as independent support and do not raise the circularity score. The skeptical concern about the existence of the embedding ι_k in the p=2 amalgamation step is a possible correctness gap in the proof, not a circularity: even if that step fails, the conclusion would not be equivalent to the input by construction. Overall, the derivation chain is self-contained with respect to the sparse claim.

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

No numbers are fitted to data and no new physical entities are introduced. The paper's assumptions are structural hypotheses (archimedeanity, RIP, flatness, irreducibility) that are stated in the theorems and checked in applications. The numerical experiments depend on unspecified randomly generated polynomials, but that is a data-availability issue, not a free parameter in the theory.

assumptions (7)
  • standard math The separation theorem (Hahn-Banach/Eidelheit-Kakutani) applies to the infinite-dimensional cone M(S)sparse and yields a nonzero positive linear functional when f is outside the cone.
    Invoked in the proof of Theorem 3.3 directly after the contradiction assumption; it is background convex analysis.
  • standard math C*-algebra amalgamation with states (Blackadar; Voiculescu, Theorem 3.1) produces a common C*-algebra D glued over the overlap algebras.
    The proofs of Theorem 3.3 and Theorem 4.2 both call on this theorem to combine the GNS representations built on each cluster.
  • standard math Dense noncommutative representation and Positivstellensatz results (Helton-McCullough [HM04], BKP16 Theorem 1.27 and 1.69) are correct and apply to the local restrictions L|R⟨X(Ik)⟩.
    Used as black boxes for the base case and for the finite-dimensional GNS construction on each cluster; these are prior results, not the paper's target.
  • domain assumption Boundedness and archimedeanity of the quadratic module (Assumption 2.3 and the added quadratic constraints (2.5)) hold for the semialgebraic sets considered.
    Without archimedeanity the sparse Positivstellensatz and convergence corollaries are not claimed; this is an explicit hypothesis of Theorems 3.3, 4.2, and Corollaries 5.9 and 6.6.
  • domain assumption The clusters I1,...,Ip satisfy the running intersection property (2.7), which is part of Assumption 2.4(iii).
    Example 3.4 shows a positive sparse polynomial outside the sparse module when RIP fails; the proof uses RIP to identify the overlap algebra at each induction step.
  • domain assumption For optimizer extraction, each overlap representation has no common invariant subspaces (H2), so the overlap algebra is a full matrix algebra by Burnside's theorem.
    This is sufficient for finite-dimensional amalgamation in Theorem 4.2; Example 4.4 shows finite-dimensional amalgamation can fail when H2 fails. It is a checkable but non-generic condition.
  • standard math Skolem-Noether and Burnside classification of homomorphisms from full matrix algebras is available.
    Used in Theorem 4.2 to conjugate the intersection blocks into ampliations and to identify irreducible real algebras with full matrix algebras.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sparse Noncommutative Polynomial Optimization." pith.science (2026). https://pith.science/paper/NHD2D5SE

@misc{pith2026190900569,
  author       = {Pith},
  title        = {Pith review of: Sparse Noncommutative Polynomial Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NHD2D5SE}},
  note         = {Machine review of arXiv:1909.00569}
}
read the original abstract

This article focuses on optimization of polynomials in noncommuting variables, while taking into account sparsity in the input data. A converging hierarchy of semidefinite relaxations for eigenvalue and trace optimization is provided. This hierarchy is a noncommutative analogue of results due to Lasserre [SIAM J. Optim. 17(3) (2006), pp. 822--843] and Waki et al. [SIAM J. Optim. 17(1) (2006), pp. 218--242]. The Gelfand-Naimark-Segal (GNS) construction is applied to extract optimizers if flatness and irreducibility conditions are satisfied. Among the main techniques used are amalgamation results from operator algebra. The theoretical results are utilized to compute lower bounds on minimal eigenvalue and trace of noncommutative polynomials from the literature.

Figures

Figures reproduced from arXiv: 1909.00569 by the authors.

Figure 1
Figure 1. Illustration of Theorem 3.1 in the case I = {1, 2}. For k = 1, . . . , p, let us define M(S) k := (X K i=1 a ⋆ i siai : K ∈ N , ai ∈ RhX(Ik)i, si ∈ (S ∩ Sym RhX(Ik)i) ∪ {1} ) , and M(S) sparse := M(S) 1 + · · · + M(S) p (3.1) . Next, we state the main foundational result of this paper. Theorem 3.3. Let S ∪ {f} ⊆ Sym RhXi and let DS be as in (2.6) with the addi￾tional quadratic constraints (2.5). Suppose Assumption 2… view at source ↗
Figure 2
Figure 2. Amalgamation for the case p = 2. For all g ∈ RhXi, we now set L˜(g) := hg(A)ξ, ξi. We claim that L˜ extends L k . Indeed, for g ∈ RhX(Ik)i we have L˜(g) = hg(A)ξ, ξi = hg(π(jk(Aˆk )))ξ, ξi = hπ(g(jk(Aˆk )))ξ, ξi = ϕ(g(jk(Aˆk ))) = ϕ(jk(g(Aˆk ))) = ϕk(g(Aˆk )) = L k (g). The above equalities come from the fact that nc polynomials commute with homo￾morphisms (here π, ιk), since they are linear combination of products … view at source ↗
Figure 3
Figure 3. Amalgamation of finite-dimensional C ⋆ -algebras The linear functional L induces linear functionals Lˇk , Lˇ12 on A(Ik), A(I1 ∩ I2) given by B 7→ tr(Bv k (v k ) T ) and C 7→ tr(Cv 12(v 12) T ), respectively. Write v k = Prk/r12 j=1 e k j ⊗ u k j for the standard basis vectors e k j ∈ R rk/r12 and some vectors u k j ∈ R r12 . Then for C ∈ A(I1 ∩ I2) = Mr12 (R) we have Lˇ12(C) = tr(Cv 12(v 12) T ) = Lˇk (Irk/r12 ⊗ C) … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

69 extracted references · 66 canonical work pages

  1. [1]

    Anjos and Jean B

    Miguel F. Anjos and Jean B. Lasserre, editors. Handbook on Semidefinite, Conic and Polynomial Optimization , volume 166. Springer Science & Business Media, 2011

    work page 2011

  2. [2]

    A course in convexity , volume 54 of Graduate Studies in Mathematics

    Alexander Barvinok. A course in convexity , volume 54 of Graduate Studies in Mathematics . American Mathematical Society, Providence, RI, 2002

    2002

  3. [3]

    The tracial moment problem and trace-optimization of polynomials

    Sabine Burgdorf, Kristijan Cafuta, Igor Klep, and Janez Povh. The tracial moment problem and trace-optimization of polynomials. Math. Program. , 137(1-2, Ser. A):557--578, 2013

    work page 2013

  4. [4]

    Linear Matrix Inequalities in System and Control Theory , volume 15 of Studies in Applied Mathematics

    Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. Linear Matrix Inequalities in System and Control Theory , volume 15 of Studies in Applied Mathematics . SIAM , Philadelphia, PA, June 1994

    work page 1994

  5. [5]

    Optimization of polynomials in non-commuting variables

    Sabine Burgdorf, Igor Klep, and Janez Povh. Optimization of polynomials in non-commuting variables . SpringerBriefs in Mathematics. Springer, [Cham], 2016

    work page 2016

  6. [6]

    Blackadar

    Bruce E. Blackadar. Weak expectations and nuclear C^ -algebras. Indiana Univ. Math. J. , 27(6):1021--1026, 1978

    work page 1978

  7. [7]

    Monotonic converging variational approximations to the functional integrals in quantum statistical mechanics

    Daniel Bessis, Pierre Moussa, and Matteo Villani. Monotonic converging variational approximations to the functional integrals in quantum statistical mechanics. J. Math. Phys. , 16(11):2318--2325, 1975

    work page 1975

  8. [8]

    An introduction to central simple algebras and their applications to wireless communication , volume 191 of Mathematical Surveys and Monographs

    Gr\' e gory Berhuy and Fr\' e d\' e rique Oggier. An introduction to central simple algebras and their applications to wireless communication , volume 191 of Mathematical Surveys and Monographs . American Mathematical Society, Providence, RI, 2013

    work page 2013

Show all 69 references
  1. [9]

    Jean R. S. Blair and Barry Peyton. An introduction to chordal graphs and clique trees. In Graph theory and sparse matrix computation , volume 56 of IMA Vol. Math. Appl. , pages 1--29. Springer, New York, 1993

    1993

  2. [10]

    Introduction to noncommutative algebra

    Matej Bresar. Introduction to noncommutative algebra . Universitext. Springer, Cham, 2014

    2014

  3. [11]

    Conn, Nicholas I

    Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint. Testing a class of methods for solving minimization problems with simple bounds on the variables. Math. Comp. , 50(182):399--430, 1988

    1988

  4. [12]

    N CSOS tools: a computer algebra system for symbolic and numerical computation with noncommutative polynomials

    Kristijan Cafuta, Igor Klep, and Janez Povh. N CSOS tools: a computer algebra system for symbolic and numerical computation with noncommutative polynomials. Optim. Methods Softw. , 26(3):363--380, 2011

    2011

  5. [13]

    Constrained polynomial optimization problems with noncommuting variables

    Kristijan Cafuta, Igor Klep, and Janez Povh. Constrained polynomial optimization problems with noncommuting variables. SIAM J. Optim. , 22(2):363--383, 2012

    2012

  6. [14]

    Semialgebraic Optimization for Bounding Lipschitz Constants of ReLU Networks

    Tong Chen, Jean-Bernard Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic Optimization for Bounding Lipschitz Constants of ReLU Networks . arXiv preprint arXiv:2002.03657 , 2020

    2002 arXiv

  7. [15]

    Exploiting sparsity in semidefinite programming via matrix completion

    Mituhiro Fukuda, Masakazu Kojima, Kazuo Murota, and Kazuhide Nakata. Exploiting sparsity in semidefinite programming via matrix completion. I . G eneral framework. SIAM J. Optim. , 11(3):647--674, 2000/01

    2000

  8. [16]

    Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization

    Sander Gribling, David de Laat, and Monique Laurent. Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization. Math. Program. , 170(1, Ser. B):5--42, 2018

    2018

  9. [17]

    Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

    Sander Gribling, David de Laat, and Monique Laurent. Lower bounds on matrix factorization ranks via noncommutative polynomial optimization. Found. Comput. Math. , to appear 2019

    2019

  10. [18]

    A note on the representation of positive polynomials with structured sparsity

    David Grimm, Tim Netzer, and Markus Schweighofer. A note on the representation of positive polynomials with structured sparsity. Archiv der Mathematik , 89(5):399--403, 2007

    2007

  11. [19]

    William Helton

    J. William Helton. `` P ositive'' noncommutative polynomials are sums of squares. Ann. of Math. (2) , 156(2):675--694, 2002

    2002

  12. [20]

    William Helton, Igor Klep, and Scott McCullough

    J. William Helton, Igor Klep, and Scott McCullough. The convex P ositivstellensatz in a free algebra. Adv. Math. , 231(1):516--534, 2012

    2012

  13. [21]

    Glopti P oly 3: moments, optimization and semidefinite programming

    Didier Henrion, Jean-Bernard Lasserre, and Johan L\" o fberg. Glopti P oly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. , 24(4-5):761--779, 2009

    2009

  14. [22]

    Approximate volume and integration for basic semialgebraic sets

    Didier Henrion, Jean-Bernard Lasserre, and Carlo Savorgnan. Approximate volume and integration for basic semialgebraic sets. SIAM Rev. , 51(4):722--743, 2009

    2009

  15. [23]

    William Helton and Scott A

    J. William Helton and Scott A. McCullough. A P ositivstellensatz for non-commutative polynomials. Trans. Amer. Math. Soc. , 356(9):3721--3737, 2004

    2004

  16. [24]

    Ordered linear spaces

    Graham Jameson. Ordered linear spaces. In Ordered linear spaces , pages 1--39. Springer, 1970

    1970

  17. [25]

    Application of polynomial optimization to electricity transmission networks

    C\' e dric Josz. Application of polynomial optimization to electricity transmission networks . Theses, Universit \'e Pierre et Marie Curie - Paris VI , July 2016

    2016

  18. [26]

    Anneaux pr\' e ordonn\' e s

    Jean-Louis Krivine. Anneaux pr\' e ordonn\' e s. J. Analyse Math. , 12:307--326, 1964

    1964

  19. [27]

    Sums of H ermitian squares and the BMV conjecture

    Igor Klep and Markus Schweighofer. Sums of H ermitian squares and the BMV conjecture. J. Stat. Phys. , 133(4):739--760, 2008

    2008

  20. [28]

    A first course in noncommutative rings , volume 131

    Tsit-Yuen Lam. A first course in noncommutative rings , volume 131. Springer Science & Business Media, 2013

    2013

  21. [29]

    Global optimization with polynomials and the problem of moments

    Jean-Bernard Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim. , 11(3):796--817, 2000/01

    2000

  22. [30]

    Convergent SDP -relaxations in polynomial optimization with sparsity

    Jean-Bernard Lasserre. Convergent SDP -relaxations in polynomial optimization with sparsity. SIAM J. Optim. , 17(3):822--843, 2006

    2006

  23. [31]

    Matrix completion problems

    Monique Laurent. Matrix completion problems. In Christodoulos A. Floudas and Panos M. Pardalos, editors, Encyclopedia of Optimization , pages 1967--1975. Springer, 2009

    1967

  24. [32]

    Sums of squares, moment matrices and optimization over polynomials

    Monique Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry , volume 149 of IMA Vol. Math. Appl. , pages 157--270. Springer, New York, 2009

    2009

  25. [33]

    Peter D. Lax. Differential equations, difference equations and matrix theory. Comm. Pure Appl. Math. , 11:175--194, 1958

    1958

  26. [34]

    Semidefinite programming and integer programming

    Monique Laurent and Franz Rendl. Semidefinite programming and integer programming. Handbooks in Operations Research and Management Science , 12:393--514, 2005

    2005

  27. [35]

    Lieb and Robert Seiringer

    Elliott H. Lieb and Robert Seiringer. Equivalent forms of the B essis- M oussa- V illani conjecture. J. Statist. Phys. , 115(1-2):185--190, 2004

    2004

  28. [36]

    A bounded degree SOS hierarchy for polynomial optimization

    Jean-Bernard Lasserre, Kim-Chuan Toh, and Shouguang Yang. A bounded degree SOS hierarchy for polynomial optimization. EURO J. Comput. Optim. , 5(1-2):87--117, 2017

    2017

  29. [37]

    Interval Enclosures of Upper Bounds of Roundoff Errors Using Semidefinite Programming

    Victor Magron. Interval Enclosures of Upper Bounds of Roundoff Errors Using Semidefinite Programming . ACM Trans. Math. Softw. , 44(4):41:1--41:18, June 2018

    2018

  30. [38]

    Factorization of operator-valued polynomials in several non-commuting variables

    Scott McCullough. Factorization of operator-valued polynomials in several non-commuting variables. Linear Algebra Appl. , 326(1-3):193--203, 2001

    2001

  31. [39]

    Certified roundoff error bounds using semidefinite programming

    Victor Magron, George Constantinides, and Alastair Donaldson. Certified roundoff error bounds using semidefinite programming. ACM Trans. Math. Software , 43(4):Art. 34, 31, 2017

    2017

  32. [40]

    A numerical algorithm for block-diagonal decomposition of matrix * -algebras with application to semidefinite programming

    Kazuo Murota, Yoshihiro Kanno, Masakazu Kojima, and Sadayoshi Kojima. A numerical algorithm for block-diagonal decomposition of matrix * -algebras with application to semidefinite programming. Jpn. J. Ind. Appl. Math. , 27(1):125--160, 2010

    2010

  33. [41]

    N. H. A. Mai, J.-B. Lasserre, and V. Magron. A sparse version of Reznick's Positivstellensatz . arXiv preprint arXiv:2002.05101 , 2020. Submitted

    2002 arXiv

  34. [42]

    http://www.mosek.com/

    The MOSEK optimization software . http://www.mosek.com/

  35. [43]

    Noncommutative sums of squares

    Scott McCullough and Mihai Putinar. Noncommutative sums of squares. Pacific J. Math. , 218(1):167--171, 2005

    2005

  36. [44]

    Stephen G. Nash. Newton-type minimization via the L \' a nczos method. SIAM J. Numer. Anal. , 21(4):770--788, 1984

    1984

  37. [45]

    Exploiting sparsity in semidefinite programming via matrix completion

    Kazuhide Nakata, Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima, and Kazuo Murota. Exploiting sparsity in semidefinite programming via matrix completion. II . I mplementation and numerical results. Math. Program. , 95(2, Ser. B):303--327, 2003

    2003

  38. [46]

    The A -truncated K -moment problem

    Jiawang Nie. The A -truncated K -moment problem. Found. Comput. Math. , 14(6):1243--1276, 2014

    2014

  39. [47]

    A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations

    Miguel Navascu \'e s, Stefano Pironio, and Antonio Ac \' n. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New J. Phys. , 10(7):073013, 2008

    2008

  40. [48]

    Hyperbolic polynomials and generalized C lifford algebras

    Tim Netzer and Andreas Thom. Hyperbolic polynomials and generalized C lifford algebras. Discrete Comput. Geom. , 51(4):802--814, 2014

    2014

  41. [49]

    Convergent relaxations of polynomial optimization problems with noncommuting variables

    Stefano Pironio, Miguel Navascu \'e s, and Antonio Ac \' n. Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM J. Optim. , 20(5):2157--2180, 2010

    2010

  42. [50]

    Positive polynomials on compact semi-algebraic sets

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

    1993

  43. [51]

    P\' a l and Tam\' a s V\' e rtesi

    K\' a roly F. P\' a l and Tam\' a s V\' e rtesi. Quantum bounds on B ell inequalities. Phys. Rev. A (3) , 79(2):022120, 12, 2009

    2009

  44. [52]

    Extremal PSD forms with few terms

    Bruce Reznick. Extremal PSD forms with few terms. Duke Math. J. , 45(2):363--374, 1978

    1978

  45. [53]

    Exploiting symmetries in SDP -relaxations for polynomial optimization

    Cordian Riener, Thorsten Theobald, Lina Jansson Andr\' e n, and Jean-Bernard Lasserre. Exploiting symmetries in SDP -relaxations for polynomial optimization. Math. Oper. Res. , 38(1):122--141, 2013

    2013

  46. [54]

    Skelton, Tetsuya Iwasaki, and Karolos M

    Robert E. Skelton, Tetsuya Iwasaki, and Karolos M. Grigoriadis. A unified algebraic approach to linear control design . The Taylor & Francis Systems and Control Book Series. Taylor & Francis, Ltd., London, 1998

    1998

  47. [55]

    Herbert R. Stahl. Proof of the BMV conjecture. Acta Math. , 211(2):255--290, 2013

    2013

  48. [56]

    Jos F. Sturm. Using S e D u M i 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. , 11/12(1-4):625--653, 1999

    1999

  49. [57]

    Theory of operator algebras

    Masamichi Takesaki. Theory of operator algebras. III , volume 127 of Encyclopaedia of Mathematical Sciences . Springer-Verlag, Berlin, 2003. Operator Algebras and Non-commutative Geometry, 8

    2003

  50. [58]

    u t\" u nc\

    Reha H. T\" u t\" u nc\" u , Kim-Chuan Toh, and Michael J. Todd. Solving semidefinite-quadratic-linear programs using SDPT 3. Math. Program. , 95(2, Ser. B):189--217, 2003

    2003

  51. [59]

    Exploiting sparsity for semi-algebraic set volume computation

    Matteo Tacchi, Tillmann Weisser, Jean-Bernard Lasserre, and Didier Henrion. Exploiting sparsity for semi-algebraic set volume computation. preprint arXiv:1902.02976 , 2019

    1902 arXiv

  52. [60]

    Dykema, and Alexandru Nica

    Dan-Virgil Voiculescu, Kenneth J. Dykema, and Alexandru Nica. Free random variables , volume 1 of CRM Monograph Series . American Mathematical Society, Providence, RI, 1992

    1992

  53. [61]

    Symmetries of some reduced free product C^ -algebras

    Dan-Virgil Voiculescu. Symmetries of some reduced free product C^ -algebras. In Operator algebras and their connections with topology and ergodic theory ( B u s teni, 1983) , volume 1132 of Lecture Notes in Math. , pages 556--588. Springer, Berlin, 1985

    1983

  54. [62]

    Algorithm 950: N cpol2sdpa-sparse semidefinite programming relaxations for polynomial optimization problems of noncommuting variables

    Peter Wittek. Algorithm 950: N cpol2sdpa-sparse semidefinite programming relaxations for polynomial optimization problems of noncommuting variables. ACM Trans. Math. Software , 41(3):Art. 21, 12, 2015

    2015

  55. [63]

    Algorithm 883: sparse POP ---a sparse semidefinite programming relaxation of polynomial optimization problems

    Hayato Waki, Sunyoung Kim, Masakazu Kojima, Masakazu Muramatsu, and Hiroshi Sugimoto. Algorithm 883: sparse POP ---a sparse semidefinite programming relaxation of polynomial optimization problems. ACM Trans. Math. Software , 35(2):Art. 15, 13, 2009

    2009

  56. [64]

    Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity

    Hayato Waki, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu. Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. , 17(1):218--242, 2006

    2006

  57. [65]

    Sparse- BSOS : a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity

    Tillmann Weisser, Jean-Bernard Lasserre, and Kim-Chuan Toh. Sparse- BSOS : a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity. Math. Program. Comput. , 10(1):1--32, 2018

    2018

  58. [66]

    TSSOS: A Moment-SOS hierarchy that exploits term sparsity

    Jie Wang, Victor Magron, and Jean-Bernard Lasserre. TSSOS: A Moment-SOS hierarchy that exploits term sparsity . arXiv preprint arXiv:1912.08899 , 2019

    1912 arXiv

  59. [67]

    Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension

    Jie Wang, Victor Magron, and Jean-Bernard Lasserre. Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension . arXiv preprint arXiv:2003.03210 , 2020

    2003 arXiv

  60. [68]

    CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization

    Jie Wang, Victor Magron, Jean-Bernard Lasserre, and Ngoc Hoang Anh Mai. CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization . arXiv preprint arXiv:2005.02828 , 2020

    2005 arXiv

  61. [69]

    Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0)

    Makoto Yamashita, Katsuki Fujisawa, and Masakazu Kojima. Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0). volume 18, pages 491--505. 2003. The Second Japanese-Sino Optimization Meeting, Part II (Kyoto, 2002)

    2003

Pith tools

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