Globally Optimal Estimation of Nested Logit Models
In the authors' words
Nested logit is widely used in operational demand models, yet jointly estimating its utility coefficients and nest dissimilarity parameters requires nonconvex optimization. Standard estimation routines offer no certificate of global optimality, leaving a gap between globally optimizing decisions under nested-logit demand and reliably estimating that demand model. We develop, to our knowledge, the first globally convergent optimization framework with an explicit global-accuracy guarantee for joint nested-logit estimation. Our central complexity result confines all exponential dependence to the number of free nest dissimilarity parameters: computation is polynomial in the numbers of observations, alternatives, and utility coefficients. Consequently, under the stated compact-domain and relaxation-error conditions, fixing the number of nests yields an additive polynomial-time approximation scheme (PTAS). The framework exploits an exact exponential-cone formulation for fixed dissimilarities and a spatial branch-and-bound algorithm that searches only over the free dissimilarities. Valid likelihood bounds provide an anytime certificate and finite termination at any prescribed additive average-log-likelihood tolerance. Across eight benchmark datasets and 240 estimation instances, the method certifies every reported solution and exposes inferior local estimates despite normal solver termination. These results establish a computational foundation for globally certified nested-logit estimation.
In plain words AI summary
Nested logit models help predict demand, but standard methods cannot guarantee the best possible estimates. Computation time grows polynomially with data size when the number of nests is fixed. The method uses a spatial branch-and-bound algorithm and provides certificates of solution quality. Tests on eight datasets showed the method certifies all solutions and reveals inferior local estimates that other solvers accept.
Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source. 1 sentence was removed for not being supported by the abstract.
Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 45 pages, 8 figures, 3 tables