pith. sign in

arxiv: 2403.17241 · v2 · submitted 2024-03-25 · 🧮 math.OC

Finite convergence of the Moment-SOS hierarchy for polynomial matrix optimization

Lei Huang , Jiawang Nie This is my paper

Pith reviewed 2026-05-24 03:13 UTC · model grok-4.3

classification 🧮 math.OC
keywords polynomial matrix optimizationMoment-SOS hierarchyfinite convergenceflat truncationmoment relaxationnonlinear semidefinite programmingArchimedean property
0
0 comments X

The pith

The Moment-SOS hierarchy for polynomial matrix optimization converges in finitely many steps when nondegeneracy, strict complementarity, and second-order sufficient conditions hold at every minimizer.

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

This paper shows that the matrix Moment-SOS hierarchy reaches the exact global minimum of a polynomial matrix optimization problem after finitely many steps. The finite termination occurs under the Archimedean property together with the nondegeneracy condition, strict complementarity condition, and second-order sufficient condition at each minimizer. Flat truncation of the moment matrix provides a practical certificate that the hierarchy has terminated exactly. The results tie classical optimality theory from nonlinear semidefinite programming to the construction of moment relaxations, so that exact solutions become available from a single finite semidefinite program rather than an infinite sequence.

Core claim

Under the Archimedean property, if the nondegeneracy condition, strict complementarity condition and second order sufficient condition hold at every minimizer, then the Moment-SOS hierarchy has finite convergence. Moreover, every minimizer of the moment relaxation must exhibit flat truncation once the relaxation order is large enough, and this flat truncation serves as a detection criterion for the finite convergence.

What carries the argument

The flat truncation condition on the moment matrix in the matrix Moment-SOS hierarchy, which certifies that the relaxation has attained the exact optimal value.

If this is right

  • Exact global solutions of qualifying polynomial matrix problems can be recovered by solving one finite semidefinite program from the hierarchy.
  • The flat truncation test becomes a reliable stopping criterion that confirms exactness has been achieved.
  • Nonlinear semidefinite programming optimality theory supplies sufficient conditions that guarantee the Moment-SOS method terminates exactly.
  • Minimizers of the original problem can be extracted directly from the moment matrix once flat truncation appears.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same finite-convergence argument may apply to other polynomial optimization problems that admit a matrix-valued formulation.
  • When the optimality conditions fail at some minimizer, the hierarchy may still converge asymptotically but without a finite termination guarantee.
  • The flat truncation criterion offers a computational check that can be performed on any instance to decide whether the obtained relaxation is already exact.
  • The link between the two theories suggests that second-order sufficient conditions could be used to certify exactness in related hierarchies for scalar or vector polynomial problems.

Load-bearing premise

The nondegeneracy condition, strict complementarity condition, and second order sufficient condition must hold at every minimizer.

What would settle it

A polynomial matrix optimization problem that satisfies the Archimedean property, has the stated optimality conditions at its minimizers, yet produces moment relaxations whose optimal values keep improving with every increase in relaxation order without ever reaching the true minimum.

read the original abstract

This paper studies the matrix Moment-SOS hierarchy for solving polynomial matrix optimization. Our first result is to show the finite convergence of this hierarchy, if the nondegeneracy condition, strict complementarity condition and second order sufficient condition hold at every minimizer, under the Archimedean property. A useful criterion for detecting the finite convergence is the flat truncation. Our second result is to show that every minimizer of the moment relaxation must have a flat truncation when the relaxation order is big enough, under the above mentioned optimality conditions. These results give connections between nonlinear semidefinite optimization theory and Moment-SOS methods for solving polynomial matrix optimization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies the matrix Moment-SOS hierarchy for polynomial matrix optimization. It claims two results: (1) finite convergence of the hierarchy (and the flat-truncation property) whenever the nondegeneracy condition, strict complementarity condition, and second-order sufficient condition hold at every minimizer, under the Archimedean assumption; (2) that every minimizer of the moment relaxation must have flat truncation for sufficiently large relaxation order under the same conditions. These are presented as connecting nonlinear semidefinite optimization theory to Moment-SOS methods.

Significance. If the proofs hold, the results supply finite-convergence guarantees for the matrix Moment-SOS hierarchy under precisely the standard second-order optimality conditions of nonlinear SDP. This is a useful theoretical link that explains when the hierarchy terminates finitely and supplies a practical flat-truncation detection criterion. The work credits the Archimedean assumption and the three classical conditions without introducing new ad-hoc hypotheses.

minor comments (3)
  1. The abstract states the main theorem but the introduction or §2 should explicitly recall the precise statements of the nondegeneracy, strict complementarity, and SOSC conditions (with equation numbers) so that the reader can verify they match the cited nonlinear-SDP references.
  2. Notation for the matrix polynomial, the moment matrix, and the localizing matrix should be introduced once in §2 with a single consistent symbol set; several symbols appear to be redefined across sections.
  3. The statement of the flat-truncation result should include an explicit dependence on the relaxation order (e.g., “for all k ≥ K0”) rather than the informal phrase “when the relaxation order is big enough.”

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of its theoretical contribution linking nonlinear SDP optimality conditions to the matrix Moment-SOS hierarchy, and the recommendation for minor revision. No specific major comments were raised.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The central results establish finite convergence of the matrix Moment-SOS hierarchy and the flat-truncation property of minimizers, but only conditionally on the nondegeneracy, strict complementarity and second-order sufficient conditions (standard external optimality criteria from nonlinear SDP theory) together with the Archimedean assumption. These inputs are not derived from or definitionally equivalent to the convergence statement; the proof chain therefore remains independent of its own outputs. No self-definitional reductions, fitted inputs renamed as predictions, load-bearing self-citations, or ansatz smuggling appear in the stated theorems.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on three standard optimality conditions from nonlinear semidefinite programming plus the Archimedean property from real algebraic geometry; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Archimedean property
    Invoked to ensure the Moment-SOS hierarchy is well-defined and the convergence statements apply (abstract).

pith-pipeline@v0.9.0 · 5624 in / 1231 out tokens · 33826 ms · 2026-05-24T03:13:30.382482+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages

  1. [1]

    Springer, Berlin (1998)

    Bochnak, J., Coste, M., Roy, M.: Real Algebraic Geometry . Springer, Berlin (1998)

    work page 1998

  2. [2]

    Cimpriˆ c, J.: Real algebraic geometry for matrices over commutative rings. J. Algebra 359, 89–103 (2012)

    work page 2012

  3. [3]

    Curto, R., Fialkow, L.: Truncated K–moment problems in s everal variables. J. Oper. Theory 54, 189–226 (2005)

    work page 2005

  4. [4]

    De Klerk, E., Laurent, M.: On the Lasserre hierarchy of se midefinite programming relaxations of convex polynomial optimization problems. SIAM J. Optim. 21, 824–832 (2011)

    work page 2011

  5. [5]

    Deliba¸ sı, A., Henrion, D.: Hermite matrix in Lagrange b asis for scaling static output feedback polynomial matrix inequalities. Int. J. Control 83(12), 2494–2505 (2010)

    work page 2010

  6. [6]

    Dorsch, D., G´ omez, W., Shikhman, V.: Sufficient optimali ty conditions hold for almost all nonlinear semidefinite programs. Math. Program. 158 (1–2), 77–97 (2016)

    work page 2016

  7. [7]

    Forsgren, A.: Optimality conditions for nonconvex semi definite programming. Math. Pro- gram. 105–128 (2000)

    work page 2000

  8. [8]

    Gribling, S., de Laat, D., Laurent, M.: Lower bounds on ma trix factorization ranks via noncommutative polynomial optimization. Found. Comput. Math. 19(5), 1013-1070 (2019)

    work page 2019

  9. [9]

    Linear Algebra Appl 648, 1-55 (2022)

    Gribling, S., Laurent, M., Steenkamp, A.: Bounding the s eparable rank via polynomial opti- mization. Linear Algebra Appl 648, 1-55 (2022)

    work page 2022

  10. [10]

    Lecture Notes in Computer Science , Vol

    Heller, J., Henrion, D., Pajdla, T.: Stable radial dist ortion calibration by polynomial matrix inequalities programming. Lecture Notes in Computer Science , Vol. 9003, 307–321 (2015)

    work page 2015

  11. [11]

    In Positive polynomials in control , 293.C310, Lecture Notes in Control and Inform

    Henrion, D., Lasserre, J.: Detecting global optimalit y and extracting solutions in Gloptipoly. In Positive polynomials in control , 293.C310, Lecture Notes in Control and Inform. Sci., 312, Springer (2005)

    work page 2005

  12. [12]

    : Convergent relaxations of p olynomial matrix inequalities and static output feedback

    Henrion, D., Lasserre, J. : Convergent relaxations of p olynomial matrix inequalities and static output feedback. IEEE Trans. Autom. Control 51, 192–202 (2006)

    work page 2006

  13. [13]

    : Inner approximations for po lynomial matrix inequalities and robust stability regions

    Henrion, D., Lasserre, J. : Inner approximations for po lynomial matrix inequalities and robust stability regions. IEEE Trans. Autom. Control 57(6), 1456–1467 (2011)

    work page 2011

  14. [14]

    W orld Scientific, Cam- bridge (2020) FINITE CONVERGENCE OF THE MATRIX MOMENT-SOS HIERARCHY 31

    Henrion, D., Korda, M., Lasserre, J.: The Moment-SOS Hi erarchy: Lectures in Probability, Statistics, Computational Geometry, Control And Nonlinea r Pdes. W orld Scientific, Cam- bridge (2020) FINITE CONVERGENCE OF THE MATRIX MOMENT-SOS HIERARCHY 31

    work page 2020

  15. [15]

    Hillar, C., Nie, J.: An elementary and constructive pro of of Hilbert’s 17th Problem for matrices, Proc. Amer. Math. Soc. 136, 73–76 (2008)

    work page 2008

  16. [16]

    Optim Lett 17, 1263–1270 (2023)

    Huang, L.: Optimality conditions for homogeneous poly nomial optimization on the unit sphere. Optim Lett 17, 1263–1270 (2023)

    work page 2023

  17. [17]

    Huang, L., Nie, J., Yuan, Y.: Homogenization for polyno mial optimization with unbounded sets. Math. Program. 200, 105–145 (2023)

    work page 2023

  18. [18]

    J Sci Comput 95, 15 (2023)

    Huang, L., Nie, J., Yuan, Y.: Generalized truncated mom ent problems with unbounded sets. J Sci Comput 95, 15 (2023)

    work page 2023

  19. [19]

    arXiv preprint, 2023

    Huang, L., Nie, J., Yuan, Y.: Finite convergence of Mome nt-SOS relaxations with non-real radical ideals. arXiv preprint, 2023. arxiv.org/abs/2309.15398

    work page arXiv 2023

  20. [20]

    Indiana Univ

    Klep, I., Schweighofer, M.: Pure states, positive matr ix polynomials and sums of hermitian squares. Indiana Univ. Math. J. 59(3), 857–874 (2010)

    work page 2010

  21. [21]

    Korda, M., Laurent, M., Margon, V., Steenkamp, A.: Expl oiting ideal-sparsity in the gener- alized moment problem with application to matrix factoriza tion ranks. Math. Program. 205 (1), 703-744 (2004)

    work page 2004

  22. [22]

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

    work page 2001

  23. [23]

    Lasserre, J.: Convexity in semi-algebraic geometry an d polynomial optimization. SIAM J. Optim. 19, 1995–2014 (2009)

    work page 1995

  24. [24]

    Lasserre, J.: An Introduction to Polynomial and Semi-algebraic Optimiza tion, Cambridge University Press, Cambridge (2015)

    work page 2015

  25. [25]

    Lasserre, J., Laurent, M., Rostalski, P.: Semidefinite characterization and computation of zero-dimensional real radical ideals. Found. Comput. Math. 8, 607–647 (2008)

    work page 2008

  26. [26]

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

    work page 2005

  27. [27]

    Laurent, M.: Semidefinite representations for finite va rieties. Math. Program. 109, 1–26 (2007)

    work page 2007

  28. [28]

    In: Emerging Applications of Algebraic Geometry of IMA Volumes in Mathematics and its Ap- plications, 149: 157–270

    Laurent, M.: Sums of squares, moment matrices and optim ization over polynomials. In: Emerging Applications of Algebraic Geometry of IMA Volumes in Mathematics and its Ap- plications, 149: 157–270. Springer (2009)

    work page 2009

  29. [29]

    Annales de la Faculte des Sciences Toulouse 15, 599–609 (2006)

    Marshall, M.: Representation of non-negative polynom ials with finitely many zeros. Annales de la Faculte des Sciences Toulouse 15, 599–609 (2006)

    work page 2006

  30. [30]

    American Mathematical Society, Providence (2008)

    Marshall, M.: Positive Polynomials and Sums of Squares . American Mathematical Society, Providence (2008)

    work page 2008

  31. [31]

    Nie, J.: Polynomial matrix inequality and semidefinite representation. Math. Oper. Res. 36(3), 398–415 (2011)

    work page 2011

  32. [32]

    Program., 142, 485–510 (2013)

    Nie, J.: Certifying convergence of Lasserre’s hierarc hy via flat truncation, Math. Program., 142, 485–510 (2013)

    work page 2013

  33. [33]

    Nie, J.: Polynomial optimization with real varieties. SIAM J. Optim. 23(3), 1634–1646 (2013)

    work page 2013

  34. [34]

    Nie, J.: Optimality conditions and finite convergence o f Lasserre’s hierarchy. Math. Program. 146(1-2), 97–121 (2014)

    work page 2014

  35. [35]

    SIAM, Phi ladelphia (2023)

    Nie, J.: Moment and Polynomial Optimization. SIAM, Phi ladelphia (2023)

    work page 2023

  36. [36]

    Nie, J., Ranestad, K., Sturmfels, B.: The algebraic deg ree of semidefinite programming. Math. Program. 122, 379–405 (2010)

    work page 2010

  37. [37]

    Indiana Univ

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

    work page 1993

  38. [38]

    Scheiderer, C.: Sums of squares on real algebraic curve s. Math. Z. , 245, 725–760 (2003)

    work page 2003

  39. [39]

    Scheiderer, C.: Distinguished representations of non -negative polynomials. J. Algebra , 289, 558–573 (2005)

    work page 2005

  40. [40]

    In: Emerging Applications of Algebraic Geometry of IMA Volumes in Mathem atics and its Applications , 149: 271–324

    Scheiderer, C.: Positivity and sums of squares: A guide to recent results. In: Emerging Applications of Algebraic Geometry of IMA Volumes in Mathem atics and its Applications , 149: 271–324. Springer (2009)

    work page 2009

  41. [41]

    Scherer, C., Hol, C.: Matrix sum-of-squares relaxatio ns for robust semi-definite programs. Math. Program. 107, 189–211 (2006)

    work page 2006

  42. [42]

    In: Emerging Applications of Algebraic Geometry of IMA Volumes in Mathematics and its Applications , 149: 325–350

    Schm¨ udgen, K.: Noncommutative real algebraic geomet ry: Some basic concepts and first ideas. In: Emerging Applications of Algebraic Geometry of IMA Volumes in Mathematics and its Applications , 149: 325–350. Springer (2009)

    work page 2009

  43. [43]

    Shapiro, A.: First and second order analysis of nonline ar semidefinite programs. Math. Pro- gram. 77(2), 301–320 (1997) 32 LEI HUANG AND JIA W ANG NIE

    work page 1997

  44. [44]

    Shapiro, A.: On uniqueness of Lagrange multipliers in o ptimization problems subject to cone constraints. SIAM J. Optim. 7(2), 508–518 (1997)

    work page 1997

  45. [45]

    Sun, D.: The strong second order sufficient condition and constraint nondegeneracy in non- linear semidefinite programming and their implications. Math. Oper. Res. 31(4), 761–776 (2006)

    work page 2006

  46. [46]

    Zheng, Y., Fantuzzi, G.: Sum-of-squares chordal decom position of polynomial matrix in- equalities. Math. Program. 197, 71–108 (2023) Lei Huang,Department of Mathematics, University of Californ ia San Diego, 9500 Gilman Drive, La Jolla, CA, USA, 92093. Email address : huanglei@lsec.cc.ac.cn Jiaw ang Nie, Department of Mathematics, University of Califo rni...

    work page 2023