Spectral analysis of the logit mapping and implications for stochastic user equilibrium algorithms
Pith reviewed 2026-05-25 05:55 UTC · model grok-4.3
The pith
The Jacobian of the logit mapping decomposes into an annihilator and a matrix with non-positive eigenvalues under monotone separable costs.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The Jacobian of the logit mapping decomposes into two matrices, one annihilating differences of feasible path flow vectors and the other with all non-positive real eigenvalues when link costs are monotone non-decreasing and separable. This decomposition enables an adaptive constant step-size MSA with global convergence and asymptotic linear rate 1-s, plus a Newton method that exploits the Jacobian structure for tractable computation on large networks.
What carries the argument
Decomposition of the Jacobian of the logit mapping into an annihilator matrix and a factor whose eigenvalues are all non-positive reals.
If this is right
- MSA with fixed step size s converges globally and achieves asymptotic linear rate 1-s.
- An adaptive rule for the step size preserves global convergence while recovering the linear rate for large iterations.
- The Newton method on the root-finding form of SUE becomes practical on large networks because the Jacobian structure avoids dense matrices and manifold projections.
- Both algorithms run faster than prior methods on large networks or at high demand levels.
Where Pith is reading between the lines
- The same decomposition might apply to other random-utility choice models if their Jacobians admit an analogous split.
- Numerical verification of the eigenvalue sign on real networks would give a practical way to check the monotonicity assumption before running the algorithms.
- The linear-rate result could guide step-size selection in other fixed-point iterations that arise in traffic equilibrium.
Load-bearing premise
Link costs are monotone non-decreasing and separable.
What would settle it
Finding a monotone separable cost function for which the second Jacobian factor has a positive eigenvalue would disprove the spectral property.
Figures
read the original abstract
We analyze the Jacobian of the logit mapping for stochastic user equilibrium (SUE) and use it to develop two improved algorithms for path-based SUE. We show that the Jacobian decomposes into two matrices: one that annihilates differences of feasible path flow vectors, and another whose eigenvalues are all non-positive reals, provided link costs are monotone non-decreasing and separable. Using these properties, we first show that the method of successive averages (MSA) with a small constant step-size $s$ converges linearly at a rate $1-s$, with the largest admissible step-size depending on the eigenvalues of the Jacobian of the logit mapping. Building on this result, we develop an adaptive constant step-size rule that retains the global convergence of MSA while achieving asymptotic linear convergence. Our second algorithm is a Newton-based method using a reformulation of SUE as a root-finding problem. Unlike gradient-projection approaches that operate on the Hessian of the SUE objective function (a dense matrix), our method exploits the structure of the Jacobian of the logit mapping, making computations tractable and removing the need for manifold optimization. Numerical experiments show superlinear convergence on most tested networks, with our methods outperforming existing approaches on large networks or when demand is high. To our knowledge, this article is the first to report runtimes for logit-based SUE on networks as large as Chicago Regional and Philadelphia, providing a benchmark for future algorithmic development.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that the Jacobian of the logit mapping in path-based stochastic user equilibrium (SUE) decomposes into two matrices—one annihilating differences of feasible path flow vectors and the other with all non-positive real eigenvalues when link costs are monotone non-decreasing and separable. This decomposition is used to prove global convergence with asymptotic linear rate 1-s for an adaptive constant-step-size method of successive averages (MSA), and to derive a tractable Newton method for the root-finding reformulation of SUE that avoids dense Hessians and manifold optimization. Numerical experiments are reported to show superlinear convergence and outperformance versus existing methods on large networks including Chicago Regional and Philadelphia.
Significance. If the decomposition and spectral properties hold under the stated assumptions, the work supplies a theoretical basis for constant-step MSA variants with explicit linear rates and a structure-exploiting Newton scheme that scales to large instances. The reported first runtimes on Chicago Regional and Philadelphia networks constitute a concrete benchmark contribution for logit-based SUE algorithms.
major comments (3)
- [Abstract] Abstract and the section deriving the Jacobian decomposition: the eigenvalue property (all non-positive real eigenvalues for the second factor) is invoked to obtain the contraction rate 1-s for constant-step MSA and local stability of Newton, yet the manuscript supplies no detailed derivation or proof of this spectral claim, leaving the central convergence arguments unverified.
- [Abstract] The convergence analysis for the adaptive MSA (and the Newton local analysis) rests on the separability assumption for the non-positive eigenvalue guarantee. No counter-example, alternative bound, or numerical robustness check is provided for non-separable costs (e.g., turning penalties or multi-class interactions), which are standard and could introduce positive real eigenvalues that invalidate the rate 1-s claim.
- [Numerical experiments] Numerical experiments section: the claims of superlinear convergence on most tested networks and outperformance on large instances or high demand lack accompanying error analysis, tabulated metrics, or data tables, making it impossible to assess the practical magnitude of improvement or reproducibility.
minor comments (2)
- Notation for the step-size parameter s and the eigenvalue bound should be introduced consistently when first used in the MSA convergence statement.
- [Abstract] The abstract states that the Newton method removes the need for manifold optimization; a brief sentence clarifying how the structure exploitation achieves this would improve readability.
Simulated Author's Rebuttal
We thank the referee for the careful review and constructive feedback on our manuscript. We address each major comment below and indicate planned revisions to strengthen the paper.
read point-by-point responses
-
Referee: [Abstract] Abstract and the section deriving the Jacobian decomposition: the eigenvalue property (all non-positive real eigenvalues for the second factor) is invoked to obtain the contraction rate 1-s for constant-step MSA and local stability of Newton, yet the manuscript supplies no detailed derivation or proof of this spectral claim, leaving the central convergence arguments unverified.
Authors: We acknowledge that the derivation of the spectral property in the Jacobian decomposition section is presented concisely. In the revised manuscript we will expand this section with a complete, self-contained proof of the eigenvalue claim under the monotone non-decreasing and separable link-cost assumptions. This will explicitly verify the contraction mapping used for the rate 1-s and the local stability of the Newton iteration. revision: yes
-
Referee: [Abstract] The convergence analysis for the adaptive MSA (and the Newton local analysis) rests on the separability assumption for the non-positive eigenvalue guarantee. No counter-example, alternative bound, or numerical robustness check is provided for non-separable costs (e.g., turning penalties or multi-class interactions), which are standard and could introduce positive real eigenvalues that invalidate the rate 1-s claim.
Authors: The referee correctly notes that the non-positive eigenvalue guarantee requires separability of link costs. This assumption is standard for the logit SUE model analyzed in the paper. In the revision we will add an explicit discussion subsection on the role of separability, clarifying that the rate 1-s is guaranteed only under this condition and that non-separable costs (such as turning penalties) may require different analysis. We will not add counter-examples or robustness checks, as these lie outside the stated scope of the separable case; instead we will reference relevant literature on non-separable SUE. revision: partial
-
Referee: [Numerical experiments] Numerical experiments section: the claims of superlinear convergence on most tested networks and outperformance on large instances or high demand lack accompanying error analysis, tabulated metrics, or data tables, making it impossible to assess the practical magnitude of improvement or reproducibility.
Authors: We agree that the numerical results section would be strengthened by additional quantitative detail. In the revised manuscript we will insert tables reporting iteration counts, CPU times, final gap values, and observed convergence rates for each algorithm and network. We will also include a short error-analysis paragraph discussing the measured superlinear behavior and factors influencing performance on the Chicago Regional and Philadelphia instances. revision: yes
Circularity Check
No significant circularity detected
full rationale
The derivation rests on an algebraic decomposition of the Jacobian of the logit mapping into an annihilator matrix and a second factor whose eigenvalues are shown non-positive under the explicit domain assumptions of monotone non-decreasing separable link costs. Convergence statements for constant-step MSA and the Newton method are obtained directly from this spectral property and the step-size rule; neither the eigenvalue sign nor the linear rate 1-s is obtained by fitting parameters to data or by renaming a self-citation. No load-bearing step reduces by construction to its own inputs, and the paper supplies no self-citation chain that substitutes for an independent proof. The result is therefore self-contained once the separability/monotonicity assumptions are granted.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Link costs are monotone non-decreasing and separable.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We show that the Jacobian decomposes into two matrices: one that annihilates differences of feasible path flow vectors, and another whose eigenvalues are all non-positive reals, provided link costs are monotone non-decreasing and separable.
-
IndisputableMonolith/Foundation/AlexanderDuality.leanalexander_duality_circle_linking unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Theorem 1. The eigenvalues of K(h) have the following properties: 1. All eigenvalues of K(h) are real and non-positive. 2. The maximum eigenvalue is zero.
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Stephen D. Boyles and Nicholas E. Lownes and Avinash Unnikrishnan. Transportation Network Analysis. 2025
work page 2025
-
[2]
Transportation Science , volume=
The convergence of equilibrium algorithms with predetermined step sizes , author=. Transportation Science , volume=. 1982 , publisher=
work page 1982
- [3]
-
[4]
Bagchi, Debojjal , title =
-
[5]
The annals of mathematical statistics , pages=
A stochastic approximation method , author=. The annals of mathematical statistics , pages=. 1951 , publisher=
work page 1951
-
[6]
Transportation network analysis , author=. Vol. I: Static and Dynamic Traffic Assignment , year=
- [7]
-
[8]
Transportmetrica A: Transport Science , volume=
Convergence behavior for traffic assignment characterization metrics , author=. Transportmetrica A: Transport Science , volume=. 2021 , publisher=
work page 2021
-
[9]
Taylor’s Theorem in One and Several Variables , year = "2011", AUTHOR =
work page 2011
-
[10]
Convergence of traffic assignments: how much is enough?
David Boyce and Biljana Ralevic-Dekic and Hillel Bar-Gera. Convergence of traffic assignments: how much is enough?. Journal of Transportation Engineering. 2004
work page 2004
-
[11]
Hillel Bar-Gera and David Boyce. Solving a non-convex combined travel forecasting model by the method of successive averages with constant step sizes. Transportation Research Part B. 2006
work page 2006
-
[12]
https://math.stackexchange.com/q/4896336 , URL =
How far is the spectral norm from the Frobenius norm? , AUTHOR =. https://math.stackexchange.com/q/4896336 , URL =
-
[13]
https://math.stackexchange.com/q/1545118 , URL =
A rank-one matrix is the product of two vectors , AUTHOR =. https://math.stackexchange.com/q/1545118 , URL =
- [14]
- [15]
- [16]
-
[17]
Springer texts in statistics, Springer, New York, NY, doi , volume=
Matrix algebra , author=. Springer texts in statistics, Springer, New York, NY, doi , volume=. 2007 , publisher=
work page 2007
- [18]
- [19]
- [20]
-
[21]
Transportation Research Record , volume=
Modified bureau of public roads link function , author=. Transportation Research Record , volume=. 2023 , publisher=
work page 2023
-
[22]
Traffic assignment manual for application with a large, high speed computer , author=. 1964 , publisher=
work page 1964
-
[23]
Holomorphic function --- Wikipedia , The Free Encyclopedia
Wikipedia contributors. Holomorphic function --- Wikipedia , The Free Encyclopedia. 2025
work page 2025
- [24]
-
[25]
Applied Mathematics: Body and Soul - Calculus in Several Dimensions, Volume III , publisher =
Kenneth Eriksson and Claes Johnson and Donald Estep , title =. Applied Mathematics: Body and Soul - Calculus in Several Dimensions, Volume III , publisher =. 2003 , chapter =. doi:10.1007/978-3-662-05800-8 , url =
- [26]
-
[27]
Transportation Networks for Research , year =
-
[28]
The American Economic Review , volume=
Pricing in urban and suburban transport , author=. The American Economic Review , volume=. 1963 , publisher=
work page 1963
-
[29]
The American economic review , volume=
Congestion theory and transport investment , author=. The American economic review , volume=. 1969 , publisher=
work page 1969
-
[30]
Transportation Research Record , volume=
Queue spillback and demand uncertainty in dynamic network loading , author=. Transportation Research Record , volume=. 2019 , publisher=
work page 2019
- [31]
-
[32]
The Quarterly Journal of Economics , volume=
Some fallacies in the interpretation of social cost , author=. The Quarterly Journal of Economics , volume=. 1924 , publisher=
work page 1924
-
[33]
Higher-order derivatives and taylor’s formula in several variables , author=. Preprint , volume=. 2005 , note =
work page 2005
-
[34]
Transportmetrica B: Transport Dynamics , volume=
Properties of dynamic user equilibrium solution: existence, uniqueness, stability, and robust solution methodology , author=. Transportmetrica B: Transport Dynamics , volume=. 2013 , publisher=
work page 2013
-
[35]
Transportation Science , volume=
On stochastic models of traffic assignment , author=. Transportation Science , volume=. 1977 , publisher=
work page 1977
-
[36]
Transportation Research Part B: Methodological , volume=
Some developments in equilibrium traffic assignment , author=. Transportation Research Part B: Methodological , volume=. 1980 , publisher=
work page 1980
-
[37]
Prashker, Joseph N and Bekhor, Shlomo , journal=. 2004 , publisher=
work page 2004
-
[38]
Equilibrium and advanced transportation modelling , pages=
Stochastic assignment to transportation networks: models and algorithms , author=. Equilibrium and advanced transportation modelling , pages=. 1998 , publisher=
work page 1998
-
[39]
Transportation Research , volume=
A probabilistic multipath traffic assignment model which obviates path enumeration , author=. Transportation Research , volume=. 1971 , publisher=
work page 1971
-
[40]
Transportation planning and technology , volume=
An improved Dial's algorithm for logit-based traffic assignment within a directed acyclic network , author=. Transportation planning and technology , volume=. 2010 , publisher=
work page 2010
-
[41]
Transportation research record , volume=
Accelerating traffic assignment with customizable contraction hierarchies , author=. Transportation research record , volume=. 2020 , publisher=
work page 2020
-
[42]
Highway traffic data for urbanized area project planning and design , author=. NCHRP Report , number=
-
[43]
Journal of Transportation Engineering , volume=
Traffic assignment in practice: overview and guidelines for users , author=. Journal of Transportation Engineering , volume=. 1991 , publisher=
work page 1991
-
[44]
Journal of Advanced Transportation , volume=
Network reliability-based optimal toll design , author=. Journal of Advanced Transportation , volume=. 2008 , publisher=
work page 2008
-
[45]
Transportation Research Part C: Emerging Technologies , volume=
Traffic congestion pricing methodologies and technologies , author=. Transportation Research Part C: Emerging Technologies , volume=. 2011 , publisher=
work page 2011
- [46]
-
[47]
Liu, Henry X and He, Xiaozheng and He, Bingsheng , journal=. 2009 , publisher=
work page 2009
-
[48]
Handbook of transport systems and traffic control , pages=
Traffic congestion and congestion pricing , author=. Handbook of transport systems and traffic control , pages=. 2001 , publisher=
work page 2001
-
[49]
Transportation Research Part B: Methodological , volume=
Profit maximization by a private toll road with cars and trucks , author=. Transportation Research Part B: Methodological , volume=. 2016 , publisher=
work page 2016
-
[50]
Equitable tolling: a case study on Sioux Falls , author=
-
[51]
Models and algorithms for road network design: a review and some new developments , author =. Transport Reviews , volume=. 1998 , publisher=
work page 1998
-
[52]
Estimation of origin-destination matrix from traffic counts: the state of the art , author=. 2011 , publisher=
work page 2011
-
[53]
Journal of Transportation Engineering , volume=
Scheduling of lane closures using genetic algorithms with traffic assignments and distributed simulations , author=. Journal of Transportation Engineering , volume=. 2004 , publisher=
work page 2004
-
[54]
Journal of Applied Probability , volume=
Avoiding the Braess paradox in non-cooperative networks , author=. Journal of Applied Probability , volume=. 1999 , publisher=
work page 1999
-
[55]
Transportation Research Part A: Policy and Practice , volume=
A capacity paradox in network design and how to avoid it , author=. Transportation Research Part A: Policy and Practice , volume=. 1998 , publisher=
work page 1998
-
[56]
Willumsen, L. G. , title =. 1978 , notes =
work page 1978
-
[57]
Transportation Research Part B: Methodological , volume=
Heuristic algorithms for the bilevel origin-destination matrix estimation problem , author=. Transportation Research Part B: Methodological , volume=. 1995 , publisher=
work page 1995
-
[58]
Selfish routing and the price of anarchy , author=. 2005 , publisher=
work page 2005
-
[59]
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages=
The price of anarchy is independent of the network topology , author=. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages=
-
[60]
Proceedings of the IEEE , volume=
The price of anarchy in transportation networks: Data-driven evaluation and reduction strategies , author=. Proceedings of the IEEE , volume=. 2018 , publisher=
work page 2018
-
[61]
2018 Annual American Control Conference (ACC) , pages=
The price of anarchy for transportation networks with mixed autonomy , author=. 2018 Annual American Control Conference (ACC) , pages=. 2018 , organization=
work page 2018
-
[62]
Transportation research procedia , volume=
An optimization approach for deriving upper and lower bounds of transportation network vulnerability under simultaneous disruptions of multiple links , author=. Transportation research procedia , volume=. 2017 , publisher=
work page 2017
-
[63]
Transportation Research Part B: Methodological , volume=
Traffic assignment by paired alternative segments , author=. Transportation Research Part B: Methodological , volume=. 2010 , publisher=
work page 2010
-
[64]
Transportation Research Part B: Methodological , volume=
A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration , author=. Transportation Research Part B: Methodological , volume=. 2006 , publisher=
work page 2006
-
[65]
Transportmetrica A: Transport Science , volume=
Local User Cost Equilibrium: a bush-based algorithm for traffic assignment , author=. Transportmetrica A: Transport Science , volume=. 2014 , publisher=
work page 2014
-
[66]
Transportation Science , volume=
Origin-based algorithm for the traffic assignment problem , author=. Transportation Science , volume=. 2002 , publisher=
work page 2002
-
[67]
Transportation Science , volume=
A note on Bar-Gera's algorithm for the origin-based traffic assignment problem , author=. Transportation Science , volume=. 2012 , publisher=
work page 2012
-
[68]
European Journal of Operational Research , volume=
Bounding the inefficiency of logit-based stochastic user equilibrium , author=. European Journal of Operational Research , volume=. 2010 , publisher=
work page 2010
-
[69]
A self instructing course in mode choice modeling: multinomial and nested logit models , author=. 2006 , publisher=
work page 2006
-
[70]
Computers & Operations Research , volume=
A variational inequality formulation for stochastic user equilibrium with a bounded choice set , author=. Computers & Operations Research , volume=. 2024 , publisher=
work page 2024
-
[71]
Transportation research part B: methodological , volume=
Post-disaster recovery sequencing strategy for road networks , author=. Transportation research part B: methodological , volume=. 2021 , publisher=
work page 2021
- [72]
-
[73]
International journal of disaster risk reduction , volume=
Long-term scheduling for road network disaster recovery , author=. International journal of disaster risk reduction , volume=. 2020 , publisher=
work page 2020
-
[74]
Transportation Science , volume=
On the convergence of the method of successive averages for calculating equilibrium in traffic networks , author=. Transportation Science , volume=. 2015 , publisher=
work page 2015
-
[75]
Transportation Research Part B: Methodological , volume=
An examination of convergence error in equilibrium traffic assignment models , author=. Transportation Research Part B: Methodological , volume=. 1988 , publisher=
work page 1988
-
[76]
Mathematical Programming , volume=
A unified approach to error bounds for structured convex optimization problems , author=. Mathematical Programming , volume=. 2017 , publisher=
work page 2017
-
[77]
Finite-dimensional variational inequalities and complementarity problems , author=. 2003 , publisher=
work page 2003
-
[78]
Linear Convergence of Method of Successive Averages in Logit-based Stochastic User Equilibrium , author =. 2026 , note =
work page 2026
-
[79]
Transportation research record , volume=
Application of cross-nested logit route choice model in stochastic user equilibrium traffic assignment , author=. Transportation research record , volume=. 2007 , publisher=
work page 2007
-
[80]
Transportmetrica A: Transport Science , volume=
A self-adaptive Armijo stepsize strategy with application to traffic assignment models and algorithms , author=. Transportmetrica A: Transport Science , volume=. 2013 , publisher=
work page 2013
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.