Pith. sign in

REVIEW 3 major objections 5 minor 2 cited by

Sparse Polynomial Matrix Optimization

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper proves that term sparsity preserves the dense hierarchy's guarantees for polynomial matrix optimization, while correlative sparsity does not.

desk verdict Real advances on sparsity for polynomial matrix optimization, but the key term-sparsity convergence theorem is only proved for scalar constraints and should be treated as conditional pending a complete proof. read the letter →

arxiv 2411.15479 v3 pith:XVXSLRSI submitted 2024-11-23 math.OC

Jared Miller , Jie Wang , Feng Guo This is my paper · ORCID
classification math.OC MSC 90C2290C23
keywords polynomialmatrixoptimizationinequalitysumofsquarestermsparsitycorrelativePMIsignsymmetrymatrix-valuedmeasures
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 asks whether the sparsity shortcuts that make sum-of-squares optimization practical for scalar polynomials survive when the objects are polynomial matrices, and shows the answer is mixed. Term sparsity does survive: the paper constructs an iterative support-and-chordal-extension procedure whose block structure converges to the one forced by the common PMI sign symmetries of the objective and constraints, and proves finite convergence of the resulting sparse relaxations to the dense bounds. Correlative sparsity does not: a simple 2x2 example satisfies the Archimedean condition and running intersection property yet the adapted hierarchy never reaches the true minimum. The paper also shows how Newton polytopes shrink monomial bases, how matrix-valued measures certify optimality and extract solutions under correlative sparsity, and how chordal matrix sparsity of the objective or the constraints can be decomposed into smaller blocks. If correct, these results let practitioners solve larger polynomial matrix problems by choosing the sparsity structure that preserves convergence.

What carries the argument

The central objects are: (1) the term sparsity pattern graph, whose nodes are monomials tagged with a column index, [$\alpha$]_i, and whose edges record which monomial products can contribute to entries of F and the G_k; (2) the alternating support-extension and chordal-extension iteration, with block closure as the chordal extension, which drives the graph to the common PMI sign symmetry structure; (3) PMI sign symmetries, binary vectors $\theta$ in {-1,1}^n with P($\theta$ composed with x) = E_{P,$\theta$} composed with P(x) for a complete-bipartite sign matrix E_{P,$\theta$}, generalizing ordinary sign symmetry to matrix entries; and (4) the p-product, a blockwise trace product that replaces the scalar inner product in the matrix Positivstellensatz and lets chordal decomposition proofs carry over. Matrix-valued measures and their flatness provide the dual certificates for optimality detection and solution extraction.

What would settle it

Run the term-sparsity block-closure iteration on a polynomial matrix optimization with at least one constraint matrix of size q_k > 1 and compare its fixed block partition to the partition induced by the common PMI sign symmetries; a single example where the two differ would falsify Theorem 4.6 as stated, and a systematic search over small random polynomial matrices with planted sign symmetries could settle the general-case claim.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is that sparsity reduction for polynomial matrix optimization has a different landscape from the scalar case. The term-sparsity iteration, alternating support extension with chordal extension using block closures, stabilizes at the block structure determined by the common PMI sign symmetries of F(x), G_1(x), ..., G_m(x), and the sparse hierarchy's bounds converge finitely to the dense hierarchy's bounds. In contrast, correlative sparsity loses asymptotic convergence when the objective is a matrix: Example 5.1 exhibits a 2x2 polynomial matrix F and two box constraints satisfying the Archimedean condition and running intersection property, yet no correlatively sparse relaxation order certifies the true optimal value. The paper restores some guarantees by giving rank-flatness conditions under which the correlatively sparse relaxation proves global optimality and returns optimal points and eigenvectors. It also transfers chordal matrix-sparsity decomposition to the matrix setting by replacing the usual inner product with the p-product, yielding block-decomposed SOS certificates for objectives and constraints with sparse chordal patterns.

Load-bearing premise

The proof of the term-sparsity convergence theorem is carried out only for scalar constraints (q_1 = ... = q_m = 1), and the paper asserts that the general case with matrix constraints follows in a similar manner without supplying the details.

Editorial extensions

If this is right

  • Term sparsity with block closures can be applied to PMO at any relaxation order, and the resulting lower bounds converge to the dense hierarchy's bounds in finitely many sparse iterations, so sparsification does not cost accuracy.
  • Unconstrained PMI verification can be performed with monomial bases cut down to the half-Newton polytopes of the diagonal entries, shrinking the Gram matrix without conservatism.
  • Correlative sparsity alone is not a sound reduction for matrix objectives: the paper's Example 5.1 shows the hierarchy can stay strictly below the true optimal value at every order despite Archimedean and running intersection assumptions.
  • When the correlatively sparse relaxation satisfies the flatness-type rank conditions, global optimality can be certified and optimal solutions, together with eigenvectors, can be recovered by merging atomic matrix-valued measures.
  • Matrix sparsity of the objective or of the constraints yields block-decomposed SOS representations, with the same chordal decomposition theorems as the scalar case after replacing the inner product by the p-product.

Reading between the lines

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

  • If the term-sparsity convergence theorem extends to matrix constraints as asserted, then PMI sign symmetries could be used directly as a preprocessing step, without running the iterative term-sparsity procedure, to impose block-diagonal Gram structure.
  • The correlative-sparsity counterexample suggests that any convergent sparse hierarchy for PMO must either scalarize the objective or impose additional conditions tying the matrix-valued marginals together; a natural test is whether a joint atomicity condition on the matrix-valued measure restores convergence.
  • The paper's use of the p-product to port scalar chordal decomposition results suggests a general recipe for transferring other scalar SOS theorems to matrix-valued settings, though each transfer needs independent verification.
  • A practical extension would be a heuristic that detects whether the correlatively sparse hierarchy is converging, for example by monitoring the rank of overlapping marginal moment matrices, so a user can switch to the scalarized formulation only when needed.
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.

Referee Report

3 major / 5 minor

Summary. The paper develops sparse semidefinite relaxations for polynomial matrix optimization (PMO), i.e., minimizing the smallest eigenvalue of a symmetric polynomial matrix subject to polynomial matrix inequalities. The contributions are: a Newton-polytope basis reduction for unconstrained PMIs; an iterative term-sparsity scheme for constrained PMOs together with a claimed convergence of the block structures to those determined by PMI sign symmetries; a correlative-sparsity adapted hierarchy with a counterexample showing that asymptotic convergence fails for matrix objectives, plus extraction results based on matrix-valued measures; matrix-sparsity decompositions for objective and constraint matrices; and extensive numerical experiments implemented in TSSOS.

Significance. If the main claims are fully established, the paper would provide the first systematic sparsity framework for PMO, with a practical implementation and substantial speedups on structured examples. The negative result in Example 5.1 is an important and convincing finding: it shows that the scalar correlative-sparsity convergence theory does not extend to matrix objectives under the usual Archimedean and running-intersection assumptions. The extraction theorems in Section 5 are proved in detail, and the numerical study is reproducible through the released TSSOS code. However, the central term-sparsity convergence theorem and the matrix-sparsity decomposition theorems rest on proofs that are currently omitted or only sketched, so the advertised scope of the results is larger than what the manuscript verifies.

major comments (3)
  1. [Section 4, Theorem 4.6] The proof of Theorem 4.6 is carried out only for q_1=...=q_m=1, and the general case is asserted to follow 'in a similar manner'. This is not a routine extension: the scalarization y^T F y reduces a PMO with scalar constraints to the TSSOS setting of [24], but for matrix constraints G_k(x)⪰0 with q_k>1, scalarizing the constraint would require additional z_k variables and z_k^T G_k z_k has support with four z-powers, so the support-extension condition (α+β+supp(G_k^{ℓ,w}))∩C^{(s)}_{i,j}≠∅ cannot be matched to the two-y-power support sets used in the matrix iteration. A proof needs to establish, for general q_k, the equivalence between this support-extension condition and the B_k edge criterion in (42), or Theorem 4.6 should be stated only for q_k=1. Since Theorem 4.6 is the advertised justification for term sparsity in constrained PMO, this gap is load-bearing.
  2. [Section 4, Theorem 4.4] Theorem 4.4 is stated with the proof omitted 'for conciseness'. This theorem supplies the constrained PMI-sign-symmetry block decomposition that underlies Corollary 4.5 and the convergence statement in Theorem 4.6; it is not a peripheral result. The authors should provide the full proof or an explicit citation to a published proof. As it stands, the block-diagonal representation (43) is an unverified assertion.
  3. [Section 6, Theorems 6.1-6.3] The proofs of Theorems 6.1, 6.2, and Corollary 6.3 are omitted with the instruction to replace the usual inner product by ⟨·,·⟩_p in the proofs of [42]. This is an assertion rather than a proof. The p-product is not a scalar inner product, and the Gram matrix of S_k has a block structure; one must show that the chordal decomposition of the SOS matrices and the p-product terms are compatible, and that the maximal cliques of F's sparsity graph can be lifted to the p×q_k block structure. Without these details, the matrix-sparsity decomposition theorems are not established.
minor comments (5)
  1. [References] Reference [1] in the bibliography appears corrupted ('AboutSections Polynomial Matrix Inequality and Semidefinite Representation'); it should be corrected to the actual title.
  2. [Section 4] The sentence 'Theorem 4.2 can be further extended to the constrained case' should refer to Theorem 4.3, not Theorem 4.2.
  3. [Example 5.1] The computation L(F)=0 is asserted with 'One can easily check'; since this is the contradiction driving the counterexample, the explicit calculation should be included so the example is fully self-contained.
  4. [Table 4] In Table 4, the CS+Chordal bounds are strictly looser than the CS bounds for a range of n; a sentence explaining why the chordal closure loses tightness in this PMO example would help the reader interpret the table.
  5. [Example 3.1] The displayed matrix R in (23) is difficult to parse because of the line breaks introduced by the text layout; please typeset it as a single matrix so that the column-to-basis correspondence is clear.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivations rest on external published theorems and self-contained constructions; omitted general-case proofs are gaps, not circular reductions.

full rationale

The paper's central claims are mathematical derivations against external benchmarks, not fitted predictions or redefinitions. The term-sparsity convergence theorem (Theorem 4.6) is proved for q_k=1 by scalarizing to y^T F(x)y and invoking [24, Cor. 6.8], which is a peer-reviewed, parameter-free theorem whose assumptions do not include the matrix target; the author overlap with [24] does not make the citation circular. The general q_k>1 case is asserted 'in a similar manner' without a proof, which is a completeness gap that could affect correctness, but it is not an instance of the conclusion being identical to the input. The PMI sign-symmetry block results (Theorems 4.3 and 4.4) use the same scalarization and cite [29] and [24]; no target result is assumed. The correlative-sparsity counterexample (Example 5.1) is self-contained: it explicitly constructs Q⪰0 and a linear functional L with L(F)=0 to rule out the sparse representation, so the negative result is derived rather than assumed. The matrix-sparsity theorems in Section 6 adapt the chordal decomposition theorems of [42] by replacing the inner product with the p-product; the adaptation is asserted without full details, but no fitted quantity or target conclusion is smuggled in. The extraction and optimality-detection results in Section 5 invoke the matrix-moment flatness theorem [41, Theorem 5] as a black box; that theorem is an established external result and does not contain the PMO conclusions as assumptions. There are no empirical predictions, no parameters fitted to data, and no quantity defined in terms of the quantity it is supposed to predict. The paper's reliance on the authors' earlier TSSOS and moment papers is real but not circular: those cited results are established independently and are used as tools, not as unverified premises that force the present conclusions.

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

The central claims rest on standard positive semidefinite and sum-of-squares results, plus two unproved extensions specific to this paper: the general constraint case of the term sparsity convergence proof, and the p-product chordal decomposition. No fitted parameters or invented physical entities are used.

assumptions (6)
  • standard math The Archimedean property of the quadratic module Sigma_p[G] implies convergence of the dense matrix Moment-SOS hierarchy via Scherer and Hol's Positivstellensatz.
    Invoked in Section 2.4 and used throughout to justify the dense hierarchy convergence, a standard result in the field.
  • standard math Chordal decomposition theorems for sparse PSD matrices (Agler et al., Grone et al.) hold and can be applied to block matrices.
    Used in Sections 2.6 and 6 to decompose sparse semidefinite constraints; these are published theorems.
  • standard math The flatness theorem for matrix-valued measures (Theorem 2.1, from Guo and Wang) guarantees atomic representing measures.
    Used in Section 5 to detect global optimality and extract solutions from sparse moment relaxations.
  • domain assumption For scalar objectives, correlative sparsity with the running intersection property and local Archimedean conditions yields asymptotic convergence (Theorem 5.1, from Kojima and Muramatsu).
    The paper builds on this scalar result and contrasts it with the new matrix counterexample.
  • ad hoc to paper The scalarization trick y^T F(x) y preserves the term sparsity graph structure in the general constrained case with q_k > 1.
    This is the unproved extension in the proof of Theorem 4.6; the proof is only given for q_k = 1 and the general case is hand-waved as 'similar'.
  • ad hoc to paper The p-product inner product in the sum-of-squares representation preserves the chordal decomposition arguments of Zheng and Fantuzzi.
    The proof of Theorem 6.1 and Corollary 6.3 says to replace the inner product with the p-product and omit the details; this is load-bearing for the matrix sparsity results.

how reviews work

0 comments
Cite this review

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

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

A polynomial matrix inequality is a formula asserting that a polynomial matrix is positive semidefinite. Polynomial matrix optimization concerns minimizing the smallest eigenvalue of a symmetric polynomial matrix subject to a tuple of polynomial matrix inequalities. This work explores the use of sparsity methods in reducing the complexity of sum-of-squares based methods in verifying polynomial matrix inequalities or solving polynomial matrix optimization. In the unconstrained setting, Newton polytopes can be employed to sparsify the monomial basis, resulting in smaller semidefinite programs. In the general setting, we show how to exploit different types of sparsity (term sparsity, correlative sparsity, matrix sparsity) encoded in polynomial matrices to derive sparse semidefinite programming relaxations for polynomial matrix optimization. For term sparsity, we show that the block structures of the term sparsity iterations with maximal chordal extensions converge to the one determined by PMI sign symmetries. For correlative sparsity, unlike the scalar case, we provide a counterexample showing that asymptotic convergence does not hold under the Archimedean condition and the running intersection property. By employing the theory of matrix-valued measures, we establish several results on detecting global optimality and retrieving optimal solutions under correlative sparsity. The effectiveness of sparsity methods on reducing computational complexity is demonstrated on various examples of polynomial matrix optimization.

Figures

Figures reproduced from arXiv: 2411.15479 by the authors.

Figure 1
Figure 1. Different types of PMI sparsity. structure can be extended to the matrix case. When F is a polynomial matrix and G1, . . . , Gm are polyno￾mials, the work in [42] utilizes the matrix (chordal) sparsity of F to construct a sparse SOS representation for F. Note that matrix sparsity is independent of the presence of specific monomials in the nonzero entries. When F is a scalar polynomial, correlative sparsity was studi… view at source ↗
Figure 2
Figure 2. TSP graph of F(x) in (24) and its chordal/block closure 4 Term Sparsity for Constrained PMO This section will apply term sparsity techniques towards PMO constrained by PMIs. Specifically, we extend the iterative procedure on exploiting term sparsity for scalar constrained polynomial optimization [24,25] to the situation of PMO. Just as in the unconstrained case of Section 3.2, the term sparsity decomposition will pr… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Finite convergence and minimizer extraction in moment relaxations with correlative sparsity

    math.OC 2025-02 accept novelty 7.0 of 10

    Sparse moment relaxations converge finitely and yield minimizers when clique moment matrices have flat extensions and the cliques satisfy the running intersection property.

  2. Moment-SOS hierarchies for arrow-type polynomial matrix inequalities with applications to structural optimization

    math.OC 2025-09 conditional novelty 6.0 of 10

    The authors prove that arrow decomposition can be applied after forming moment-SOS relaxations of polynomial matrix inequalities, yielding convergent lower bounds and significant computational speedups in structural o...

Reference graph

Works this paper leans on

61 extracted references · 60 canonical work pages · cited by 2 Pith papers

  1. [24]

    TSSOS: A moment-SOS hierarchy that exploits term sparsity,

    J. Wang, V. Magron, and J.-B. Lasserre, “TSSOS: A moment-SOS hierarchy that exploits term sparsity,” SIAM Journal on optimization, vol. 31, no. 1, pp. 30–58, 2021

    work page 2021

  2. [42]

    Sum-of-squares chordal decomposition of polynomial matrix inequalities,

    Y. Zheng and G. Fantuzzi, “Sum-of-squares chordal decomposition of polynomial matrix inequalities,” Mathematical Programming, vol. 197, no. 1, pp. 71–108, 2023

    work page 2023

  3. [1]

    AboutSections Polynomial Matrix Inequality and Semidefinite Representation,

    J. Nie, “AboutSections Polynomial Matrix Inequality and Semidefinite Representation,”Mathematics of Operations Research, vol. 36, no. 3, pp. 398–415, 2011

    work page 2011

  4. [2]

    Linear matrix inequality representation of sets,

    J. W. Helton and V. Vinnikov, “Linear matrix inequality representation of sets,”Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, vol. 60, no. 5, pp. 654–674, 2007

    work page 2007

  5. [3]

    Inner Approximations for Polynomial Matrix Inequalities and Robust Stability Regions,

    D. Henrion and J.-B. Lasserre, “Inner Approximations for Polynomial Matrix Inequalities and Robust Stability Regions,”IEEE Transactions on Automatic Control, vol. 57, no. 6, pp. 1456–1467, 2011

    work page 2011

  6. [4]

    Global optimality in minimum compliance topology optimization of frames and shells by moment-sum-of-squares hierarchy,

    M. Tyburec, J. Zeman, M. Kruˇ z ´ ık, and D. Henrion, “Global optimality in minimum compliance topology optimization of frames and shells by moment-sum-of-squares hierarchy,”Structural and Multidisciplinary Optimization, vol. 64, no. 4, pp. 1963–1981, 2021

    work page 1963

  7. [5]

    Frequency-domain identification of discrete-time systems using sum-of-rational optimization,

    M. Abdalmoaty, J. Miller, M. Yin, and R. S. Smith, “Frequency-domain identification of discrete-time systems using sum-of-rational optimization,”IF AC-PapersOnLine, vol. 58, no. 15, pp. 121–126, 2024

    work page 2024

  8. [6]

    Analysis of input-affine dynamical systems using parameterized robust coun- terparts,

    J. Miller and M. Sznaier, “Analysis of input-affine dynamical systems using parameterized robust coun- terparts,”IEEE Transactions on Automatic Control, 2025

    work page 2025

Show all 61 references
  1. [7]

    LMI techniques for optimization over polynomials in control: a survey,

    G. Chesi, “LMI techniques for optimization over polynomials in control: a survey,”IEEE transactions on Automatic Control, vol. 55, no. 11, pp. 2500–2510, 2010

    2010

  2. [8]

    Some NP-complete problems in quadratic and nonlinear programming,

    K. G. Murty and S. N. Kabadi, “Some NP-complete problems in quadratic and nonlinear programming,” Tech. Rep., 1985

    1985

  3. [9]

    dReal: An SMT solver for nonlinear theories over the reals,

    S. Gao, S. Kong, and E. M. Clarke, “dReal: An SMT solver for nonlinear theories over the reals,” in International conference on automated deduction. Springer, 2013, pp. 208–214

    2013

  4. [10]

    Blekherman, P

    G. Blekherman, P. A. Parrilo, and R. R. Thomas,Semidefinite Optimization and Convex Algebraic Geometry. SIAM, 2012

    2012

  5. [11]

    There are Significantly More Nonnegative Polynomials than Sums of Squares,

    G. Blekherman, “There are Significantly More Nonnegative Polynomials than Sums of Squares,”Israel Journal of Mathematics, vol. 153, no. 1, pp. 355–380, 2006

    2006

  6. [12]

    Positive Polynomials on Compact Semi-algebraic Sets,

    M. Putinar, “Positive Polynomials on Compact Semi-algebraic Sets,”Indiana University Mathematics Journal, vol. 42, no. 3, pp. 969–984, 1993

    1993

  7. [13]

    On the Effective Putinar’s Positivstellensatz and Moment Approximation,

    L. Baldi and B. Mourrain, “On the Effective Putinar’s Positivstellensatz and Moment Approximation,” Mathematical Programming, vol. 200, no. 1, pp. 71–103, 2023

    2023

  8. [14]

    Sum of squares relaxations for robust polynomial semi-definite programs,

    C. Hol and C. Scherer, “Sum of squares relaxations for robust polynomial semi-definite programs,” IF AC Proceedings Volumes, vol. 38, no. 1, pp. 451–456, 2005

    2005

  9. [15]

    Exploiting Sparsity in Complex Polynomial Optimization,

    J. Wang and V. Magron, “Exploiting Sparsity in Complex Polynomial Optimization,”Journal of Opti- mization Theory and Applications, vol. 192, no. 1, pp. 335–359, 2022

    2022

  10. [16]

    “Positive

    J. W. Helton, ““Positive” noncommutative polynomials are sums of squares,”Annals of Mathematics, pp. 675–694, 2002. 27

    2002

  11. [17]

    Constrained Polynomial Optimization Problems with Noncommuting Variables,

    K. Cafuta, I. Klep, and J. Povh, “Constrained Polynomial Optimization Problems with Noncommuting Variables,”SIAM Journal on Optimization, vol. 22, no. 2, pp. 363–383, 2012

    2012

  12. [18]

    Symmetry in Tur´ an sums of squares polynomials from flag algebras,

    A. Raymond, M. Singh, and R. R. Thomas, “Symmetry in Tur´ an sums of squares polynomials from flag algebras,”Algebraic Combinatorics, vol. 1, no. 2, pp. 249–274, 2018

    2018

  13. [19]

    J. B. Lasserre,Moments, Positive Polynomials And Their Applications, ser. Imperial College Press Optimization Series. World Scientific Publishing Company, 2009

    2009

  14. [20]

    Harmonic hierarchies for polynomial optimization,

    S. Cristancho and M. Velasco, “Harmonic hierarchies for polynomial optimization,”SIAM Journal on Optimization, vol. 34, no. 1, pp. 590–615, 2024

    2024

  15. [21]

    Magron and J

    V. Magron and J. Wang,Sparse Polynomial Optimization Theory and Practice. World Scientific, 2023

    2023

  16. [22]

    Chordal and factor-width decompositions for scal- able semidefinite and polynomial optimization,

    Y. Zheng, G. Fantuzzi, and A. Papachristodoulou, “Chordal and factor-width decompositions for scal- able semidefinite and polynomial optimization,”Annual Reviews in Control, vol. 52, pp. 243–279, 2021

    2021

  17. [23]

    Sums of Squares and Semidefinite Program Re- laxations for Polynomial Optimization Problems with Structured Sparsity,

    H. Waki, S. Kim, M. Kojima, and M. Muramatsu, “Sums of Squares and Semidefinite Program Re- laxations for Polynomial Optimization Problems with Structured Sparsity,”SIAM J. Optim., vol. 17, no. 1, pp. 218–242, 2006

    2006

  18. [25]

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

    J. Wang, V. Magron, and J. B. Lasserre, “Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension,”SIAM Journal on Optimization, vol. 31, no. 1, pp. 114–141, 2021

    2021

  19. [26]

    Exploiting term sparsity in noncommutative polynomial optimization,

    J. Wang and V. Magron, “Exploiting term sparsity in noncommutative polynomial optimization,”Com- putational Optimization and Applications, vol. 80, no. 2, pp. 483–521, 2021

    2021

  20. [27]

    Extremal PSD forms with few terms,

    B. Reznick, “Extremal PSD forms with few terms,”Duke Mathematical Journal, vol. 45, no. 2, p. 363–374, Jun 1978

    1978

  21. [28]

    Symmetry groups, semidefinite programs, and sums of squares,

    K. Gatermann and P. A. Parrilo, “Symmetry groups, semidefinite programs, and sums of squares,” Journal of Pure and Applied Algebra, vol. 192, no. 1-3, pp. 95–128, 2004

    2004

  22. [29]

    Pre-and post-processing sum-of-squares programs in practice,

    J. Lofberg, “Pre-and post-processing sum-of-squares programs in practice,”IEEE transactions on au- tomatic control, vol. 54, no. 5, pp. 1007–1011, 2009

    2009

  23. [30]

    Exploiting algebraic structure in sum of squares programs,

    P. A. Parrilo, “Exploiting algebraic structure in sum of squares programs,” inPositive polynomials in control. Springer, 2005, pp. 181–194

    2005

  24. [31]

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

    J. Wang, V. Magron, J. B. Lasserre, and N. H. A. Mai, “CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization,”ACM Transactions on Mathematical Software, vol. 48, no. 4, pp. 1–26, 2022

    2022

  25. [32]

    Exploiting Sign Symmetries in Minimizing Sums of Rational Func- tions,

    F. Guo, J. Wang, and J. Zheng, “Exploiting Sign Symmetries in Minimizing Sums of Rational Func- tions,”arXiv preprint arXiv:2405.09419, 2024

    2024 arXiv

  26. [33]

    Amoebas, nonnegative polynomials and sums of squares supported on circuits,

    S. Iliman and T. De Wolff, “Amoebas, nonnegative polynomials and sums of squares supported on circuits,”Research in the Mathematical Sciences, vol. 3, pp. 1–35, 2016

    2016

  27. [34]

    Relative entropy relaxations for signomial optimization,

    V. Chandrasekaran and P. Shah, “Relative entropy relaxations for signomial optimization,”SIAM J. Optim., vol. 26, no. 2, pp. 1147–1173, 2016

    2016

  28. [35]

    A second order cone characterization for sums of nonnegative circuits,

    J. Wang and V. Magron, “A second order cone characterization for sums of nonnegative circuits,” in Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, 2020, pp. 450–457

    2020

  29. [36]

    Sonc optimization and exact nonnegativity certificates via second-order cone programming,

    V. Magron and J. Wang, “Sonc optimization and exact nonnegativity certificates via second-order cone programming,”Journal of Symbolic Computation, vol. 115, pp. 346–370, 2023. 28

    2023

  30. [37]

    Kojima,Sums of squares relaxations of polynomial semidefinite programs

    M. Kojima,Sums of squares relaxations of polynomial semidefinite programs. Inst. of Technology, 2003

    2003

  31. [38]

    Convergent relaxations of polynomial matrix inequalities and static output feedback,

    D. Henrion and J.-B. Lasserre, “Convergent relaxations of polynomial matrix inequalities and static output feedback,”IEEE Transactions on Automatic Control, vol. 51, no. 2, pp. 192–202, 2006

    2006

  32. [39]

    Convergence rates of S.O.S. hierarchies for polynomial semidefinite pro- grams,

    H. A. Tran and K.-C. Toh, “Convergence rates of S.O.S. hierarchies for polynomial semidefinite pro- grams,”arXiv preprint arXiv:2406.12013, 2024

    2024

  33. [40]

    Tightness of the matrix Moment-SOS hierarchy,

    L. Huang and J. Nie, “Tightness of the matrix Moment-SOS hierarchy,”arXiv preprint arXiv:2403.17241, 2024

    2024 arXiv

  34. [41]

    A Moment-Sum-of-Squares Hierarchy for Robust Polynomial Matrix Inequality Optimization with Sum-of-Squares Convexity,

    F. Guo and J. Wang, “A Moment-Sum-of-Squares Hierarchy for Robust Polynomial Matrix Inequality Optimization with Sum-of-Squares Convexity,”Mathematics of Operations Research, 2024

    2024

  35. [43]

    A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones,

    M. Kojima and M. Muramatsu, “A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones,”Computational Optimization and Applications, vol. 42, no. 1, pp. 31– 41, 2009

    2009

  36. [44]

    Sparse polynomial optimization with matrix constraints,

    J. Nie, Z. Qu, X. Tang, and L. Zhang, “Sparse polynomial optimization with matrix constraints,”

  37. [45]

    Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion,

    S. Kim, M. Kojima, M. Mevissen, and M. Yamashita, “Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion,”Mathematical programming, vol. 129, no. 1, pp. 33–68, 2011

    2011

  38. [46]

    Term-sparse polynomial optimization for the design of frame structures,

    M. Handa, M. Tyburec, and M. Koˇ cvara, “Term-sparse polynomial optimization for the design of frame structures,” 2025. [Online]. Available: https://arxiv.org/abs/2503.20915

    2025 arXiv

  39. [47]

    Matrix Sum-of-Squares Relaxations for Robust Semi-Definite Programs,

    C. W. Scherer and C. W. Hol, “Matrix Sum-of-Squares Relaxations for Robust Semi-Definite Programs,” Mathematical programming, vol. 107, no. 1, pp. 189–211, 2006

    2006

  40. [48]

    Closures of Quadratic Modules,

    J. Cimpri˘ c, M. Marshall, and T. Netzer, “Closures of Quadratic Modules,”Automatica, vol. 183, no. 1, pp. 445–474, 2011

    2011

  41. [49]

    On the complexity of Putinar’s Positivstellensatz,

    J. Nie and M. Schweighofer, “On the complexity of Putinar’s Positivstellensatz,”Journal of Complexity, vol. 23, no. 1, pp. 135–150, 2007

    2007

  42. [50]

    Minimum-weight triangulation is NP-hard,

    W. Mulzer and G. Rote, “Minimum-weight triangulation is NP-hard,”Journal of the ACM (JACM), vol. 55, no. 2, pp. 1–29, 2008

    2008

  43. [51]

    Treewidth computations I. upper bounds,

    H. L. Bodlaender and A. M. Koster, “Treewidth computations I. upper bounds,”Information and Computation, vol. 208, no. 3, pp. 259–275, 2010

    2010

  44. [52]

    Positive semidefinite matrices with a given sparsity pattern,

    J. Agler, W. Helton, S. McCullough, and L. Rodman, “Positive semidefinite matrices with a given sparsity pattern,”Linear Algebra and its Applications, vol. 107, pp. 101–149, 1988

    1988

  45. [53]

    Positive definite completions of partial hermitian matrices,

    R. Grone, C. R. Johnson, E. M. S´ a, and H. Wolkowicz, “Positive definite completions of partial hermitian matrices,”Linear Algebra and its Applications, vol. 58, pp. 109–124, 1984

    1984

  46. [54]

    L¨ ofberg,Block diagonalization of matrix-valued sum-of-squares programs

    J. L¨ ofberg,Block diagonalization of matrix-valued sum-of-squares programs. Link¨ oping University Electronic Press, 2008

    2008

  47. [55]

    On matrix-valued monge–kantorovich optimal mass transport,

    L. Ning, T. T. Georgiou, and A. Tannenbaum, “On matrix-valued monge–kantorovich optimal mass transport,”IEEE transactions on automatic control, vol. 60, no. 2, pp. 373–382, 2014

    2014

  48. [56]

    Convergent SDP-relaxations in polynomial optimization with sparsity,

    J. B. Lasserre, “Convergent SDP-relaxations in polynomial optimization with sparsity,”SIAM Journal on Optimization, vol. 17, no. 3, pp. 822–843, 2006. 29

    2006

  49. [57]

    A note on the representation of positive polynomials with structured sparsity,

    D. Grimm, T. Netzer, and M. Schweighofer, “A note on the representation of positive polynomials with structured sparsity,”Archiv der Mathematik, vol. 89, no. 5, pp. 399–403, 2007

    2007

  50. [58]

    TSSOS: a Julia library to exploit sparsity for large-scale polynomial opti- mization,

    V. Magron and J. Wang, “TSSOS: a Julia library to exploit sparsity for large-scale polynomial opti- mization,”The sixteenth Effective Methods in Algebraic Geometry conference, 2021

    2021

  51. [59]

    The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm,

    E. D. Andersen and K. D. Andersen, “The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm,” inHigh Performance Optimization, ser. Applied Optimization. Springer US, 2000, vol. 33, pp. 197–232

    2000

  52. [60]

    Chordal sparsity in control and optimization of large-scale systems,

    Y. Zheng, “Chordal sparsity in control and optimization of large-scale systems,” Ph.D. dissertation, University of Oxford, 2019. 30 A An alternative exploitation of constraint matrix sparsity Here, we provide another way to exploit constraint matrix sparsity. We first extend T...

    2019

  53. [2024]

    Available: https://arxiv.org/abs/2411.18820

    [Online]. Available: https://arxiv.org/abs/2411.18820

Pith tools

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