Globally Optimal Estimation of Nested Logit Models
Abstract
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.
Related
- Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification
- Secure RIS-Aided Multicasting: Globally Optimal Beam Management and Discrete-Phase RIS Configuration
- A Stochastic Nested Fixed Point Algorithm for Large-Scale BLP Estimation
- Analytically Optimal Sample Allocations for Nested Multivariate Multifidelity Control Variate Estimators
- Optimal guaranteed sequential estimation for mean-reverting CEV diffusions
BibTeX
@misc{pham2026globally,
title = {{Globally Optimal Estimation of Nested Logit Models}},
author = {Hoang Giang Pham and Tien Mai},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25038},
eprint = {2610.25038},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25038},
}
RIS
TY - UNPB
TI - Globally Optimal Estimation of Nested Logit Models
AU - Hoang Giang Pham
AU - Tien Mai
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2610.25038
UR - https://arxiv.org/abs/2610.25038
AB - 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.
ER -