pith. sign in

arxiv: 2604.17563 · v1 · submitted 2026-04-19 · 🧮 math.OC

Composition and tensor train structure in polynomial optimization

Lloren\c{c} Balada Gaggioli , Didier Henrion , Milan Korda This is my paper

Pith reviewed 2026-05-10 05:31 UTC · model grok-4.3

classification 🧮 math.OC
keywords polynomial optimizationmoment-SOS hierarchiescomposition structuretensor trainstate liftingsums of squaresMarkov chainsneural networks
0
0 comments X

The pith

Polynomial optimization problems with composition or tensor train structure admit two new moment-SOS hierarchies that deliver certified bounds on instances with hundreds or a thousand variables.

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

The paper focuses on polynomial optimization where the objective factors into a sequence of lower-dimensional maps, producing intermediate states whose dimension stays small. This composition or tensor-train form appears in dynamical systems, Markov chains, and neural networks. The authors construct two moment-SOS relaxations that lift these states into the hierarchy, one via chordal sparsity patterns and one via direct push-forward on measures. A sympathetic reader cares because conventional moment-SOS methods become intractable once the number of variables exceeds a few dozen, whereas the lifted versions remain tractable while preserving convergence guarantees. The central mechanism is therefore the controlled introduction of auxiliary state variables that expose the hidden low-dimensional structure.

Core claim

We study polynomial optimization problems whose objective has a composition or tensor train structure. These polynomials can be evaluated as a sequence of maps, giving rise to intermediate variables of lower dimension. We develop two moment-SOS hierarchies that exploit this composition structure in different ways. The first one, termed state-lifting chordal, is based on the correlative sparsity graph of the problem. The second one, termed state-lifting push-forward, encodes the structure at the level of the measures directly. Numerical experiments demonstrate that the proposed methods can compute certified bounds for problems with hundreds or even a thousand variables.

What carries the argument

State-lifting moment-SOS hierarchies (chordal and push-forward variants) that encode the composition or tensor-train structure by introducing auxiliary intermediate variables.

If this is right

  • Certified global bounds become computable for Markov-chain optimization problems of practical size.
  • Quantum optimal-control problems with hundreds of variables can be solved with rigorous certificates.
  • Neural-network training or verification tasks inherit the same dimension reduction and certification.
  • The hierarchies remain valid even when the ambient dimension reaches one thousand.
  • Both chordal and push-forward liftings converge to the global minimum under the stated structural assumption.

Where Pith is reading between the lines

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

  • The same lifting idea could be tested on other sequential structures such as tree-like or chain-like factorizations that arise in stochastic control.
  • Integration with existing sparse-SOS solvers might further enlarge the class of tractable problems beyond the examples shown.
  • One could examine whether the push-forward construction extends to non-polynomial compositions while keeping measure-theoretic convergence.
  • The chordal version may combine with other graph-based sparsity patterns to handle even higher-dimensional systems.

Load-bearing premise

The composition or tensor-train structure must be present and directly encodable into the moment-SOS relaxations while preserving their convergence and certification properties.

What would settle it

A concrete polynomial optimization instance whose objective visibly factors through low-dimensional maps yet one of the two lifted hierarchies fails to converge to the true optimum or produces an invalid bound.

Figures

Figures reproduced from arXiv: 2604.17563 by Didier Henrion, Lloren\c{c} Balada Gaggioli, Milan Korda.

Figure 1
Figure 1. Figure 1: Gr graph for r = (3, 1, 2, 2, 1), where the black edges are the edges connecting original variables to lifted variables, and the blue lines connect lifted variables between themselves [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Graph for the CP-decomposed polynomial (as in 18) of rank 3 and in 5 variables. [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Maximum probability of a 2-state Markov chain with quadratic polynomials as prob [PITH_FULL_IMAGE:figures/full_fig_p026_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Maximum overlap achieved for different number of steps (gates) using SL [PITH_FULL_IMAGE:figures/full_fig_p028_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Range of values that the state can take at each stage of the neural network, compared [PITH_FULL_IMAGE:figures/full_fig_p032_5.png] view at source ↗
read the original abstract

We study polynomial optimization problems whose objective has a composition or tensor train structure. These polynomials can be evaluated as a sequence of maps, giving rise to intermediate variables (``states'') of dimension lower than the ambient dimension. Structures like these arise naturally in dynamical systems, Markov chains, and neural networks. We develop two moment-SOS (sums of squares) hierarchies that exploit this composition structure in different ways. The first one, termed state-lifting chordal, is based on the correlative sparsity graph of the problem. The second one, termed state-lifting push-forward, encodes the structure at the level of the measures directly. Numerical experiments demonstrate that the proposed methods can compute certified bounds for problems with hundreds or even a thousand variables. To illustrate the versatility of the hierarchies we apply them to Markov chain optimization, quantum optimal control, and neural networks.

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

2 major / 2 minor

Summary. The manuscript develops two moment-SOS hierarchies for polynomial optimization problems whose objective exhibits composition or tensor-train structure, giving rise to lower-dimensional intermediate states. The first hierarchy (state-lifting chordal) modifies the correlative sparsity graph; the second (state-lifting push-forward) encodes the composition directly via push-forward measures. Both are claimed to produce certified bounds that converge to the global minimum, and numerical experiments on Markov-chain optimization, quantum optimal control, and neural-network problems are reported to succeed on instances with hundreds to a thousand variables.

Significance. If the convergence guarantees hold and the hierarchies remain valid moment-SOS relaxations, the work would meaningfully extend the reach of certified polynomial optimization to structured high-dimensional problems arising in dynamical systems and machine learning, where standard Lasserre hierarchies become intractable.

major comments (2)
  1. [Section 4] The central convergence claim in the abstract requires that both lifted quadratic modules remain Archimedean (or satisfy Putinar's condition). Section 4 (state-lifting push-forward construction) does not contain an explicit argument showing that the push-forward measure preserves compactness of the support or the Archimedean property when the intermediate maps are non-polynomial; without this, the hierarchy may fail to converge or produce valid bounds.
  2. [Section 5, Table 2] Table 2 and the accompanying text in Section 5 report certified bounds for problems with up to 1000 variables, yet no comparison is given to the standard (non-structured) Lasserre hierarchy at the same relaxation order, nor are the extracted moment matrices or dual SOS certificates displayed; this leaves open whether the observed scalability stems from the structural exploitation or from problem-specific features.
minor comments (2)
  1. [Section 2] Notation for the intermediate state variables (denoted x_k in Section 2) is introduced without an explicit dimension table, making it difficult to track how the ambient dimension n relates to the state dimensions d_k across the composition chain.
  2. [Section 5] The abstract states that the methods 'compute certified bounds,' but the experimental section does not report the duality gap or the numerical rank of the moment matrices used to extract solutions; adding these diagnostics would strengthen the certification claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address each major comment point by point below, indicating where revisions will be made to strengthen the presentation and clarify the theoretical foundations.

read point-by-point responses

  1. Referee: [Section 4] The central convergence claim in the abstract requires that both lifted quadratic modules remain Archimedean (or satisfy Putinar's condition). Section 4 (state-lifting push-forward construction) does not contain an explicit argument showing that the push-forward measure preserves compactness of the support or the Archimedean property when the intermediate maps are non-polynomial; without this, the hierarchy may fail to converge or produce valid bounds.

    Authors: We agree that an explicit argument is needed to confirm that the push-forward construction preserves the Archimedean property, especially since the manuscript includes examples (such as neural networks) where intermediate maps may be non-polynomial. In the revised version, we will add a new lemma in Section 4 establishing that, under the assumptions of compact support for the original measure and continuous intermediate maps, the push-forward measure inherits compactness and the Archimedean property from the original quadratic module. This will ensure the convergence guarantees hold and will be cross-referenced in the abstract and introduction. revision: yes

  2. Referee: [Section 5, Table 2] Table 2 and the accompanying text in Section 5 report certified bounds for problems with up to 1000 variables, yet no comparison is given to the standard (non-structured) Lasserre hierarchy at the same relaxation order, nor are the extracted moment matrices or dual SOS certificates displayed; this leaves open whether the observed scalability stems from the structural exploitation or from problem-specific features.

    Authors: We acknowledge that direct comparisons on the largest instances are infeasible, as the standard Lasserre hierarchy produces moment matrices whose size grows exponentially with the number of variables and quickly exceeds available memory and time. To address the concern, we will add a new subsection in Section 5 with comparisons on smaller instances (up to 50 variables) drawn from the same problem classes, where both the standard and structured hierarchies can be run at the same relaxation orders. These will quantify the computational savings and bound quality improvements attributable to the state-lifting. We will also display representative moment matrices and the associated dual SOS certificates for one moderate-sized example to verify that the reported bounds are indeed certified. revision: partial

Circularity Check

0 steps flagged

No circularity: hierarchies extend standard moment-SOS theory via explicit structural encoding

full rationale

The paper introduces two new moment-SOS hierarchies (state-lifting chordal and state-lifting push-forward) that encode composition/tensor-train structure into the correlative sparsity graph or the measure space. These modifications are defined directly from the problem data and the intermediate state maps; the convergence claims rest on applying the existing Lasserre/Putinar theory to the resulting lifted problems rather than deriving the bounds from any fitted parameter or self-referential definition. No step reduces a claimed result to an input by construction, and no load-bearing uniqueness theorem or ansatz is imported solely via self-citation. The derivation chain remains self-contained against the standard moment-SOS framework.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the work relies on standard moment-SOS assumptions such as the existence of representing measures and convergence of the hierarchy under suitable conditions; no free parameters or invented entities are explicitly introduced in the summary.

axioms (1)
  • domain assumption Standard assumptions of the moment-SOS hierarchy (existence of representing measures and convergence properties) hold when the composition structure is exploited.
    Implicit in the claim that the new hierarchies compute certified bounds.

pith-pipeline@v0.9.0 · 5445 in / 1157 out tokens · 39004 ms · 2026-05-10T05:31:19.211104+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

36 extracted references · 36 canonical work pages

  1. [1]

    Henrion, M

    D. Henrion, M. Korda, and J. B. Lasserre,The Moment-SOS Hierarchy. World Scientific, 2020

    work page 2020

  2. [2]

    Magron and J

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

    work page 2023

  3. [3]

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

    H. Waki, S. Kim, M. Kojima, and M. Muramatsu, “Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity,”SIAM Journal on Optimization, vol. 17, no. 1, pp. 218–242, 2006

    work page 2006

  4. [4]

    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

    work page 2006

  5. [5]

    Hern´ andez-Lerma and J

    O. Hern´ andez-Lerma and J. B. Lasserre,Discrete-time Markov control processes: basic optimality criteria, Springer, 2012

    work page 2012

  6. [6]

    Tensor-train decomposition,

    I. V. Oseledets, “Tensor-train decomposition,”SIAM Journal on Scientific Computing, vol. 33, no. 5, pp. 2295–2317, 2011

    work page 2011

  7. [7]

    Global optimization of low-rank polynomials , url =

    L. Balada Gaggioli, D. Henrion, and M. Korda, “Global optimization of low-rank polyno- mials,” arXiv:2512.08394, 2025

    work page arXiv 2025

  8. [8]

    Tensor rank and the ill-posedness of the best low-rank ap- proximation problem,

    V. de Silva and L.-H. Lim, “Tensor rank and the ill-posedness of the best low-rank ap- proximation problem,”SIAM Journal on Matrix Analysis and Applications, vol. 30, no. 3, pp. 1084–1127, 2008

    work page 2008

  9. [9]

    Convex geometric motion planning of multi-body systems on lie groups via variational integrators and sparse moment relaxation,

    S. Teng, A. Jasour, R. Vasudevan, and M. Ghaffari, “Convex geometric motion planning of multi-body systems on lie groups via variational integrators and sparse moment relaxation,” The International Journal of Robotics Research, vol. 44, no. 10-11, pp. 1784–1813, 2025

    work page 2025

  10. [10]

    Fast and certifiable trajectory opti- mization,

    S. Kang, X. Xu, J. Sarva, L. Liang, and H. Yang, “Fast and certifiable trajectory opti- mization,”The 16th International Workshop on the Algorithmic Foundations of Robotics, 2024. 33

    work page 2024

  11. [11]

    Convex computation of the maximum controlled invariant set for polynomial control systems,

    M. Korda, D. Henrion, and C. N. Jones, “Convex computation of the maximum controlled invariant set for polynomial control systems,”SIAM Journal on Control and Optimization, vol. 52, no. 5, pp. 2944–2969, 2014

    work page 2014

  12. [12]

    Tensor-product approximation of high-dimensional func- tions,

    S. Dolgov and B. N. Khoromskij, “Tensor-product approximation of high-dimensional func- tions,”SIAM Journal on Scientific Computing, vol. 34, no. 3, pp. A3016–A3038, 2013

    work page 2013

  13. [13]

    Global optimization with polynomials and the problem of moments,

    J. B. Lasserre, “Global optimization with polynomials and the problem of moments,”SIAM Journal on Optimization, vol. 11, no. 3, pp. 796–817, 2001

    work page 2001

  14. [14]

    Exploiting sparsity in semidefinite programming via matrix completion,

    M. Fukuda, M. Kojima, K. Murota, and K. Nakata, “Exploiting sparsity in semidefinite programming via matrix completion,”Mathematical Programming, vol. 79, no. 1-3, pp. 235– 253, 2001

    work page 2001

  15. [15]

    Generalized lagrangian duals and sum of squares relaxations for polynomial optimization problems with structured sparsity,

    S. Kim, M. Kojima, and H. Waki, “Generalized lagrangian duals and sum of squares relaxations for polynomial optimization problems with structured sparsity,”SIAM Journal on Optimization, vol. 20, no. 3, pp. 1465–1488, 2009

    work page 2009

  16. [16]

    Chordal graphs and semidefinite optimization,

    L. Vandenberghe and M. S. Andersen, “Chordal graphs and semidefinite optimization,” Foundations and Trends in Optimization, Vol. 1, No. 4, pp. 241–433, 2014

    work page 2014

  17. [17]

    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, Volume 89, pages 399–403, 2007

    work page 2007

  18. [18]

    Convergence rates for sums-of-squares hier- archies with correlative sparsity,

    M. Korda, V. Magron, and R. Rios-Zertuche, “Convergence rates for sums-of-squares hier- archies with correlative sparsity,”Mathematical Programming, vol. 209, no. 1, pp. 435–473, 2025

    work page 2025

  19. [19]

    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

  20. [20]

    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, pp. 1–26, 2022

    work page 2022

  21. [21]

    Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks,

    M. Korda, M. Laurent, V. Magron, and A. Steenkamp, “Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks,”Mathematical Programming, vol. 205, pp. 703–744, 2024

    work page 2024

  22. [22]

    Optimization of polynomials with sparsity encoded in a few linear forms,

    J. B. Lasserre, “Optimization of polynomials with sparsity encoded in a few linear forms,” IFAC-PapersOnLine, vol. 55, no. 30, pp. 383–387, 2022

    work page 2022

  23. [23]

    Finite convergence and minimizer extraction in moment relaxations with correlative sparsity , url =

    G. Fantuzzi and F. Fuentes, “Finite convergence and minimizer extraction in moment relaxations with correlative sparsity,” arXiv:2502.01410, 2025

    work page arXiv 2025

  24. [24]

    Nonlinear optimal control via occu- pation measures and lmi relaxations,

    J. B. Lasserre, D. Henrion, C. Prieur, and E. Tr´ elat, “Nonlinear optimal control via occu- pation measures and lmi relaxations,”SIAM Journal on Control and Optimization, vol. 47, no. 4, pp. 1643–1666, 2008

    work page 2008

  25. [25]

    J. B. Lasserre,Moments, Positive Polynomials and Their Applications, vol. 1 ofImperial College Press Optimization Series. Imperial College Press, 2010

    work page 2010

  26. [26]

    A semidefinite programming approach to the generalized problem of mo- ments,

    J. B. Lasserre, “A semidefinite programming approach to the generalized problem of mo- ments,”Mathematical Programming, vol. 112, no. 1, pp. 65–92, 2008

    work page 2008

  27. [27]

    Julia: A fresh approach to numerical computing,

    J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A fresh approach to numerical computing,”SIAM Review, vol. 59, no. 1, pp. 65–98, 2017. 34

    work page 2017

  28. [28]

    TSSOS: A Julia library to exploit sparsity for large-scale poly- nomial optimization,

    V. Magron and J. Wang, “TSSOS: A Julia library to exploit sparsity for large-scale poly- nomial optimization,” arXiv:2103.00915, 2021

    work page arXiv 2021

  29. [29]

    E. D. Andersen, K. D. Andersen. The Mosek Interior Point Optimizer for Linear Program- ming: An Implementation of the Homogeneous Algorithm. In: Frenk, H., Roos, K., Terlaky, T., Zhang, S. (eds) High Performance Optimization. Applied Optimization, Springer, 2000

    work page 2000

  30. [30]

    D. A. Levin, Y. Peres, and E. L. Wilmer,Markov Chains and Mixing Times. American Mathematical Society, 2009

    work page 2009

  31. [31]

    Training Schr¨ odinger’s cat: quantum optimal control: Strategic report on current status, visions and goals for research in europe,

    S. J. Glaser, U. Boscain, T. Calarco, C. P. Koch, W. K¨ ockenberger, R. Kosloff, I. Kuprov, B. Luy, S. Schirmer, T. Schulte-Herbr¨ uggen, D. Sugny, and F. K. Wilhelm, “Training Schr¨ odinger’s cat: quantum optimal control: Strategic report on current status, visions and goals for research in europe,”The European Physical Journal D, vol. 69, Dec. 2015

    work page 2015

  32. [32]

    Globally optimal control of quantum dynamics,

    D. I. Bondar, L. Balada Gaggioli, G. Korpas, J. Mareˇ cek, J. Vala, and K. Jacobs, “Globally optimal control of quantum dynamics,”Phys. Rev. Res., vol. 7, p. 043202, Nov 2025

    work page 2025

  33. [33]

    Unitary gate synthesis via polynomial optimization,

    L. Balada Gaggioli, D. I. Bondar, J. Vala, R. Ovsiannikov, and J. Mareˇ cek, “Unitary gate synthesis via polynomial optimization,” arXiv:2508.01356, 2025

    work page arXiv 2025

  34. [34]

    Goodfellow, Y

    I. Goodfellow, Y. Bengio, and A. Courville,Deep Learning. MIT Press, 2016

    work page 2016

  35. [35]

    Stability and performance verification of dynamical systems controlled by neu- ral networks: Algorithms and complexity,

    M. Korda, “Stability and performance verification of dynamical systems controlled by neu- ral networks: Algorithms and complexity,”IEEE Control Systems Letters, vol. 6, pp. 3265– 3270, 2022

    work page 2022

  36. [36]

    Semialgebraic optimization for lipschitz constants of relu networks,

    T. Chen, J. B. Lasserre, V. Magron, and E. Pauwels, “Semialgebraic optimization for lipschitz constants of relu networks,” inAdvances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, eds.), vol. 33, pp. 19189– 19200, Curran Associates, Inc., 2020. 35

    work page 2020