pith. machine review for the scientific record. sign in

arxiv: 2604.18785 · v1 · submitted 2026-04-20 · 🧮 math.OC

Recognition: unknown

Tropical low-rank approximation and application to optimal control of N-body systems

Marianne Akian , Stephane Gaubert , Shanqing Liu , Yang Qi
Authors on Pith no claims yet

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

classification 🧮 math.OC
keywords tropical low-rank approximationoptimal controlN-body systemsvalue functiontrajectory-based methodsdeterministic controlmonotone lower bounds
0
0 comments X

The pith

A trajectory-based tropical low-rank approximation produces monotone lower bounds that converge to the exact value function for deterministic optimal control problems at the initial state and along optimal trajectories.

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

The paper develops an approximation technique for the value function in deterministic optimal control problems, motivated by N-body systems whose action functional includes local kinetic and potential terms plus interactions. It represents the value function as a tropical tensor of small rank, meaning a supremum of a small number of additively separable functions, and refines this representation only along a sequence of relevant trajectories rather than propagating basis functions globally. This produces a monotone family of computable lower bounds whose tropical tensor rank grows at most linearly with the number of outer iterations. Under suitable regularity assumptions on the dynamics and value function, the bounds converge to the exact value at the initial state and along the optimal trajectory starting from it. In the N-body case the generated basis functions stay additively separable across subsystems, enabling structured approximations that remain effective for state dimensions up to 200.

Core claim

The authors introduce a trajectory-based tropical low-rank approximation method for the value function of deterministic optimal control problems. Rather than using global propagation of basis functions, the method improves the approximation only along sequences of relevant trajectories. The resulting family of approximations consists of monotone increasing lower bounds for the exact value function, with the tropical tensor rank increasing at most linearly in the number of outer iterations. Under suitable regularity assumptions, these lower bounds converge to the exact value at the initial state and also at every point of the optimal trajectory starting from that state. When applied to N-body

What carries the argument

Trajectory-based tropical low-rank approximation, which refines a supremum of additively separable functions only along a sequence of relevant trajectories to produce structured lower bounds for the value function.

If this is right

  • The approximations form a monotone family of lower bounds that can be computed iteratively.
  • The tropical tensor rank grows at most linearly with the number of outer iterations.
  • In N-body systems the basis functions remain additively separable across subsystems, preserving structure.
  • The method remains computationally feasible for state dimensions up to 200 within modest time budgets.
  • Convergence holds both at the initial state and along the entire optimal trajectory.

Where Pith is reading between the lines

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

  • The linear rank growth may make the approach viable for real-time control of moderately large particle systems where global methods fail.
  • The separability preservation could extend naturally to other multi-agent or networked control problems with local-plus-interaction structure.
  • If regularity can be verified in practice, the method offers a way to obtain guaranteed improving bounds without solving the full Hamilton-Jacobi-Bellman equation.
  • Similar trajectory refinement ideas might be tested on stochastic or hybrid control problems to check whether monotonicity and convergence survive added noise.

Load-bearing premise

The dynamics and value function satisfy suitable regularity assumptions that enable the convergence of the lower bounds to the exact value.

What would settle it

Numerical computation on a regular N-body system showing that the generated lower bounds fail to approach the exact value at the initial state after many iterations, or a constructed counterexample where regularity holds but convergence does not occur.

Figures

Figures reproduced from arXiv: 2604.18785 by Marianne Akian, Shanqing Liu, Stephane Gaubert, Yang Qi.

Figure 1
Figure 1. Figure 1: Optimal trajectories for equally spaced initial posi [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The approximate value of the total action functional [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Representative random-initialization experiment with [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Large-scale experiment with random initial positions [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
read the original abstract

We study the approximation of the value function of deterministic optimal control problems with fixed initial state, motivated by \(N\)-body systems. In this setting, the action functional consists of local kinetic and potential terms, along with an interaction potential. We exploit this structure to approximate the value function using a tropical tensor of small rank, i.e.\ a supremum of a small number of additively separable functions. We propose a trajectory-based tropical low-rank approximation method. Rather than propagating basis functions globally, as in usual tropical numerical methods, the approximation of the value function is improved only along a sequence of relevant trajectories. The resulting approximations form a monotone family of computable lower bounds for the exact value function, with the tropical tensor rank increasing at most linearly with the number of outer iterations. Under suitable regularity assumptions, we show that at the initial state, and also at the optimal trajectory starting from this state, the lower bounds converge to the exact value. In the $N$-body setting, the generated basis functions remain additively separable across subsystems, thereby yielding a structured tropical low-rank approximation. Numerical experiments on $N$-body systems with Coulomb-type repulsion illustrate the effectiveness of the approach up to state dimension \(200\), within a half hour time budget.

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 paper proposes a trajectory-based tropical low-rank approximation method for the value function of deterministic optimal control problems with fixed initial state, motivated by N-body systems. It represents the value function as a tropical tensor (supremum of additively separable functions) and improves the approximation only along sequences of relevant trajectories rather than globally. This yields a monotone family of computable lower bounds whose tropical rank grows at most linearly with outer iterations. Under suitable regularity assumptions on the dynamics and value function, the lower bounds converge to the exact value at the initial state and along the associated optimal trajectory. In the N-body setting, additive separability across subsystems is preserved. Numerical experiments on systems with Coulomb-type repulsion demonstrate effectiveness up to state dimension 200.

Significance. If the convergence result holds, the method provides a scalable approach to high-dimensional optimal control by exploiting additive structure and restricting updates to trajectories, avoiding the curse of dimensionality while delivering monotone lower bounds and linear rank growth. The preservation of separability for N-body subsystems is a notable structural advantage. The approach builds on tropical geometry in a way that appears independent of fitted parameters, with explicit bounds on rank growth.

major comments (2)
  1. [Abstract / Convergence theorem] The convergence claim in the abstract (and presumably the main theorem) relies on 'suitable regularity assumptions' on the dynamics and value function, but these are not stated explicitly or shown to be verifiable in the N-body setting. This is load-bearing for the central theoretical result; without the precise conditions and a sketch of how they imply pointwise convergence at the initial state and optimal trajectory, the proof cannot be assessed.
  2. [Numerical experiments section] Numerical experiments (up to dimension 200) report success within a half-hour budget but provide no baseline comparisons (e.g., against standard dynamic programming, other low-rank methods, or global tropical approximations) and no error analysis or convergence rates in the reported runs. This weakens the claim of effectiveness, as it is unclear whether the observed performance is due to the trajectory restriction or other factors.
minor comments (2)
  1. [Introduction / Method] Notation for the tropical tensor rank and the distinction between local kinetic/potential terms versus interaction potential could be clarified with an explicit example in the N-body case.
  2. [N-body application] The statement that 'the generated basis functions remain additively separable across subsystems' would benefit from a short proof or reference to how the trajectory-based update preserves this property.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and positive evaluation of the paper's significance. We address the major comments below and will incorporate revisions to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Abstract / Convergence theorem] The convergence claim in the abstract (and presumably the main theorem) relies on 'suitable regularity assumptions' on the dynamics and value function, but these are not stated explicitly or shown to be verifiable in the N-body setting. This is load-bearing for the central theoretical result; without the precise conditions and a sketch of how they imply pointwise convergence at the initial state and optimal trajectory, the proof cannot be assessed.

    Authors: We agree that the assumptions need to be made explicit for the convergence result to be fully assessable. In the revised version, we will include a new subsection detailing the precise regularity assumptions (such as local Lipschitz continuity of the dynamics, boundedness and continuity of the running cost, and semi-concavity of the value function). We will also add a proof sketch explaining how these conditions ensure the monotone convergence of the lower bounds to the exact value at the initial state and along the optimal trajectory. Regarding verifiability in the N-body setting, we will show that the Coulomb-type interaction potentials satisfy these assumptions for suitable choices of parameters, as the potentials are smooth and the dynamics are polynomial. revision: yes

  2. Referee: [Numerical experiments section] Numerical experiments (up to dimension 200) report success within a half-hour budget but provide no baseline comparisons (e.g., against standard dynamic programming, other low-rank methods, or global tropical approximations) and no error analysis or convergence rates in the reported runs. This weakens the claim of effectiveness, as it is unclear whether the observed performance is due to the trajectory restriction or other factors.

    Authors: This is a valid observation. Standard dynamic programming is intractable for dimensions beyond small values due to the curse of dimensionality, so direct comparison is not feasible for d=200. However, we will enhance the numerical section by including error analysis: specifically, we will report the evolution of the approximation error at the initial state over iterations, demonstrating the convergence rate empirically. For smaller dimensions (e.g., d=10 or 20), we will add comparisons with a global tropical low-rank approximation method to highlight the efficiency gains from the trajectory-based approach. We will also discuss why the trajectory restriction is key to scalability. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper constructs a trajectory-based tropical low-rank approximation for the value function of deterministic optimal control problems, exploiting the additive separability of local kinetic/potential and interaction terms in N-body systems. It generates a monotone family of lower bounds by updating basis functions only along relevant trajectories, with tropical rank growing at most linearly in outer iterations. Convergence to the exact value at the initial state and optimal trajectory is established under stated regularity assumptions on the dynamics and value function. No load-bearing step reduces by construction to a fitted parameter, self-citation chain, or renamed input; the method is independent of the reported numerics and relies on standard tropical geometry without smuggling ansatzes or uniqueness theorems from prior self-work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on regularity assumptions for convergence and the structural decomposition of the action functional into local and interaction terms.

axioms (1)
  • domain assumption Suitable regularity assumptions on the value function and system dynamics
    Invoked to guarantee convergence of the lower bounds at the initial state and optimal trajectory.

pith-pipeline@v0.9.0 · 5526 in / 1038 out tokens · 33880 ms · 2026-05-10T03:41:38.354332+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

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

  1. PI-SONet: A Physics-Informed Symplectic Operator Network for Real-Time Optimal Control of Multi-Agent Systems

    math.OC 2026-05 unverdicted novelty 6.0

    PI-SONet trains a single structure-preserving operator network to deliver sub-second approximations to Pontryagin Maximum Principle solutions for parameterized multi-agent optimal control problems.

Reference graph

Works this paper leans on

40 extracted references · 2 canonical work pages · cited by 1 Pith paper

  1. [1]

    W. H. Fleming and H. M. Soner,Controlled Markov processes and viscosity solutions, ser. Stochastic Modelling and Applied Probability. (a) Trajectories forN= 30. (b) Mean and maximum radii. (c) Value ofV(x 0, T). Fig. 3: Representative random-initialization experiment with 30agents and terminal cost. (a) Trajectories forN= 100. (b) Mean and maximum radii. ...

    2006

  2. [2]

    Bardi and I

    M. Bardi and I. Capuzzo-Dolcetta,Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Birkh ¨auser Boston, 2008

    2008

  3. [3]

    Viscosity solutions of Hamilton- Jacobi equations,

    M. G. Crandall and P.-L. Lions, “Viscosity solutions of Hamilton- Jacobi equations,”Trans. Am. Math. Soc., vol. 277, pp. 1–42, 1983

    1983

  4. [4]

    Some properties of viscosity solutions of Hamilton-Jacobi equations,

    M. G. Crandall, L. C. Evans, and P.-L. Lions, “Some properties of viscosity solutions of Hamilton-Jacobi equations,”Trans. Am. Math. Soc., vol. 282, pp. 487–502, 1984

    1984

  5. [5]

    Pontryagin’s principle for state- constrained control problems governed by parabolic equations with unbounded controls,

    J. P. Raymond and H. Zidani, “Pontryagin’s principle for state- constrained control problems governed by parabolic equations with unbounded controls,”SIAM J. Control Optim., vol. 36, no. 6, pp. 1853– 1879, 1998

    1998

  6. [6]

    Pontryagin’s principle for time-optimal problems,

    J.-P. Raymond and H. Zidani, “Pontryagin’s principle for time-optimal problems,”J. Optim. Theory Appl., vol. 101, no. 2, pp. 375–402, 1999

    1999

  7. [7]

    Two approximations of solutions of Hamilton-Jacobi equations,

    M. G. Crandall and P.-L. Lions, “Two approximations of solutions of Hamilton-Jacobi equations,”Math. Comput., vol. 43, pp. 1–19, 1984

    1984

  8. [8]

    Falcone and R

    M. Falcone and R. Ferretti,Semi-Lagrangian approximation schemes for linear and Hamilton-Jacobi equations. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2014

    2014

  9. [9]

    A max-plus-based algorithm for a Hamilton–Jacobi–Bellman equation of nonlinear filtering,

    W. H. Fleming and W. M. McEneaney, “A max-plus-based algorithm for a Hamilton–Jacobi–Bellman equation of nonlinear filtering,”SIAM J. Control Optim., vol. 38, no. 3, pp. 683–710, 2000

    2000

  10. [10]

    McEneaney,Max-Plus Methods for Nonlinear Control and Estima- tion, ser

    W. McEneaney,Max-Plus Methods for Nonlinear Control and Estima- tion, ser. Systems & Control: Foundations & Applications. Boston: Birkh¨auser-Verlag, 2006

    2006

  11. [11]

    The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis,

    M. Akian, S. Gaubert, and A. Lakhoua, “The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis,”SIAM Journal on Control and Optimization, vol. 47, no. 2, pp. 817–848, 2008

    2008

  12. [12]

    M ´ethode des ´el´ements finis max-plus pour la r ´esolution num´erique de probl `emes de commande optimale d ´eterministe,

    A. Lakhoua, “M ´ethode des ´el´ements finis max-plus pour la r ´esolution num´erique de probl `emes de commande optimale d ´eterministe,” Ph.D. dissertation, Universit´e Paris 6, 2007

    2007

  13. [13]

    A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs,

    W. M. McEneaney, “A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs,”SIAM J. Control Optim., vol. 46, no. 4, pp. 1239–1276, 2007

    2007

  14. [14]

    Contraction of Riccati flows applied to the convergence analysis of a max-plus curse-of-dimensionality-free method,

    Z. Qu, “Contraction of Riccati flows applied to the convergence analysis of a max-plus curse-of-dimensionality-free method,”SIAM J. Control Optim., vol. 52, no. 5, pp. 2677–2706, 2014

    2014

  15. [15]

    A stochastic algorithm for deterministic multistage optimization problems,

    M. Akian, J.-P. Chancelier, and B. Tran, “A stochastic algorithm for deterministic multistage optimization problems,”Annals of Operations Research, vol. 345, no. 1, pp. 1–38, 2025

    2025

  16. [16]

    Neural network architectures using min-plus algebra for solving certain high-dimensional optimal control problems and hamilton–jacobi pdes,

    J. Darbon, P. M. Dower, and T. Meng, “Neural network architectures using min-plus algebra for solving certain high-dimensional optimal control problems and hamilton–jacobi pdes,”Mathematics of Control, Signals, and Systems, vol. 35, no. 1, pp. 1–44, 2023

    2023

  17. [17]

    V . P. Maslov,M ´ethodes op ´eratorielles. Mir, 1987

    1987

  18. [18]

    Zero-sum repeated games: accelerated algorithms and tropical best-approximation,

    O. Saadi, “Zero-sum repeated games: accelerated algorithms and tropical best-approximation,” Ph.D. dissertation, Institut Polytechnique de Paris, 2021

    2021

  19. [19]

    Tropical linear regression and mean payoff games: or, how to measure the distance to equilibria,

    M. Akian, S. Gaubert, Y . Qi, and O. Saadi, “Tropical linear regression and mean payoff games: or, how to measure the distance to equilibria,” SIAM J. Discrete Math., vol. 37, no. 2, pp. 632–674, 2023

    2023

  20. [20]

    Curse-of- complexity attenuation in the curse-of-dimensionality-free method for hjb pdes,

    W. M. McEneaney, A. Deshpande, and S. Gaubert, “Curse-of- complexity attenuation in the curse-of-dimensionality-free method for hjb pdes,” in2008 American Control Conference. IEEE, 2008, pp. 4684–4690

    2008

  21. [21]

    A max-plus based randomized algorithm for solving a class of HJB PDEs,

    Z. Qu, “A max-plus based randomized algorithm for solving a class of HJB PDEs,” in53rd IEEE Conference on Decision and Control, Dec. 2014, pp. 1575–1580

    2014

  22. [22]

    From a monotone probabilistic scheme to a probabilistic max-plus algorithm for solving Hamilton-Jacobi-Bellman equations,

    M. Akian and E. Fodjo, “From a monotone probabilistic scheme to a probabilistic max-plus algorithm for solving Hamilton-Jacobi-Bellman equations,” inHamilton-Jacobi-Bellman Equations: Numerical Meth- ods and Applications in Optimal Control, D. Kalise, K. Kunisch, and Z. Rao, Eds. De Gruyter, 2018

    2018

  23. [23]

    Multi-stage stochastic optimization applied to energy planning,

    M. V . Pereira and L. M. Pinto, “Multi-stage stochastic optimization applied to energy planning,”Mathematical programming, vol. 52, no. 1, pp. 359–375, 1991

    1991

  24. [24]

    Analysis of stochastic dual dynamic programming method,

    A. Shapiro, “Analysis of stochastic dual dynamic programming method,”European Journal of Operational Research, vol. 209, no. 1, pp. 63–72, 2011

    2011

  25. [25]

    On the convergence of decomposition methods for multistage stochastic convex programs,

    P. Girardeau, V . Leclere, and A. B. Philpott, “On the convergence of decomposition methods for multistage stochastic convex programs,” Mathematics of Operations Research, vol. 40, no. 1, pp. 130–145, 2015

    2015

  26. [26]

    Inexact cuts in stochastic dual dynamic programming,

    V . Guigues, “Inexact cuts in stochastic dual dynamic programming,” SIAM Journal on Optimization, vol. 30, no. 1, pp. 407–438, 2020

    2020

  27. [27]

    A survey of point-based POMDP solvers,

    G. Shani, J. Pineau, and R. Kaplow, “A survey of point-based POMDP solvers,”Autonomous Agents and Multi-Agent Systems, vol. 27, no. 1, pp. 1–51, 2013

    2013

  28. [28]

    An efficient dp algorithm on a tree-structure for finite horizon optimal control problems,

    A. Alla, M. Falcone, and L. Saluzzi, “An efficient dp algorithm on a tree-structure for finite horizon optimal control problems,”SIAM Journal on Scientific Computing, vol. 41, no. 4, pp. A2384–A2406, 2019

    2019

  29. [29]

    A tree structure algorithm for optimal control problems with state constraints,

    ——, “A tree structure algorithm for optimal control problems with state constraints,”Rend. Mat. Appl., VII. Ser., vol. 41, no. 3-4, pp. 193–221, 2020

    2020

  30. [30]

    Optimistic planning algorithms for state-constrained optimal control problems,

    O. Bokanowski, N. Gammoudi, and H. Zidani, “Optimistic planning algorithms for state-constrained optimal control problems,”Computers & Mathematics with Applications, vol. 109, pp. 158–179, 2022

    2022

  31. [31]

    A multilevel fast marching method for the minimum time problem,

    M. Akian, S. Gaubert, and S. Liu, “A multilevel fast marching method for the minimum time problem,”SIAM Journal on Control and Optimization, vol. 62, no. 6, pp. 2963–2991, 2024

    2024

  32. [32]

    An adaptative multi-level max-plus method for deterministic optimal control problems,

    ——, “An adaptative multi-level max-plus method for deterministic optimal control problems,” inProceedings of the 22nd IFAC World Congress, Yokohama, Japan, 2023, also arXiv preprint:2304.10342

    work page arXiv 2023

  33. [33]

    The principle of least action and fundamental solutions of mass-spring and N-body two-point boundary value problems,

    W. M. McEneaney and P. M. Dower, “The principle of least action and fundamental solutions of mass-spring and N-body two-point boundary value problems,”SIAM J. Control Optim., vol. 53, no. 5, pp. 2898– 2933, 2015

    2015

  34. [34]

    Tensor decomposition methods for high-dimensional Hamilton-Jacobi-Bellman equations,

    S. Dolgov, D. Kalise, and K. K. Kunisch, “Tensor decomposition methods for high-dimensional Hamilton-Jacobi-Bellman equations,” SIAM J. Sci. Comput., vol. 43, no. 3, pp. a1625–a1650, 2021

    2021

  35. [35]

    Approximating the stationary Bellman equation by hierarchical tensor products,

    M. Oster, L. Sallandt, and R. Schneider, “Approximating the stationary Bellman equation by hierarchical tensor products,”J. Comput. Math., vol. 42, no. 3, pp. 638–661, 2024

    2024

  36. [36]

    Curse of dimensionality reduction in max-plus based approximation methods: Theoretical estimates and improved pruning algorithms,

    S. Gaubert, W. McEneaney, and Z. Qu, “Curse of dimensionality reduction in max-plus based approximation methods: Theoretical estimates and improved pruning algorithms,” in50th IEEE Conference on Decision and Control and European Control Conference. IEEE, 2011, pp. 1054–1061

    2011

  37. [37]

    Bundle-based pruning in the max-plus curse of dimensionality free method,

    S. Gaubert, Z. Qu, and S. Sridharan, “Bundle-based pruning in the max-plus curse of dimensionality free method,” inProceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems July 7-11, 2014. Groningen, The Netherland, 2014, pp. 166–172

    2014

  38. [38]

    The turnpike property in finite-dimensional nonlinear optimal control,

    E. Tr ´elat and E. Zuazua, “The turnpike property in finite-dimensional nonlinear optimal control,”J. Differ. Equations, vol. 258, no. 1, pp. 81–114, 2015

    2015

  39. [39]

    Linear quadratic optimal control turnpike in finite and infinite dimension: two-term expansion of the value function,

    V . Aˇskovi´c, E. Tr´elat, and H. Zidani, “Linear quadratic optimal control turnpike in finite and infinite dimension: two-term expansion of the value function,”Systems & Control Letters, vol. 188, p. 105803, 2024

    2024

  40. [40]

    Turnpike in optimal control and beyond: a survey,

    E. Tr ´elat and E. Zuazua, “Turnpike in optimal control and beyond: a survey,”arXiv preprint:2503.20342, 2025

    work page arXiv 2025