In this paper, we propose a gradient descent method to estimate the parameters in a Markov chain choice model. Particularly, we derive closed-form formula for the gradient of the log-likelihood function and show the convergence of the algorithm. Numerical experiments verify the efficiency of our approach by comparing with the expectation-maximization algorithm. We show that the similar result can be extended to a more general case that one does not have observation of the no-purchase data.
Lei Fu, Dong-Dong Ge
. A Gradient Descent Method for Estimating the Markov Chain Choice Model[J]. Journal of the Operations Research Society of China, 2023
, 11(2)
: 371
-381
.
DOI: 10.1007/s40305-021-00365-6
[1] Blanchet, J., Gallego, G., Goyal, V.:A Markov chain approximation to choice modeling. Oper. Res. 64(4), 886-905(2016)
[2] Feldman, J. B., & Topaloglu, H.:Revenue management under the Markov chain choice model. Oper. Res. 65(5), 1322-1342(2017)
[3] Désir, A., Goyal, V., Segev, D., Ye, C.:Capacity constrained assortment optimization under the Markov chain based choice model (2016). https://doi.org/10.2139/ssrn.2626484
[4] Désir, A., Goyal, V., Topalogu, H., Zhang, J.:Robust assortment optimization under the Markov chain model (2019). http://www.columbia.edu/~vg2277/Robust_MC.pdf
[5] Davis, J.M., Gallego, G., Topaloglu, H.:Assortment optimization under variants of the nested logit model. Oper. Res. 62(2), 250-273(2014)
[6] Rusmevichientong, P., Max Shen, Z.-J., Shmoys, D.B.:Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Oper. Res. 58(6), 1666-1680(2010)
[7] Simsek, S., Topaloglu, H.:Technical note:An expectation-maximization algorithm to estimate the parameters of the Markov chain choice model. Oper. Res. J. Oper. Res. Soc. Am. 66(3),748-760(2018)
[8] Gupta, A., Hsu, D.:Parameter identification in Markov chain choice models. Theoretical Computer Science, 808, 99-107(2020)
[9] Goldstein, A.A.:Convex programming in Hilbert space. Bull. Am. Math. Soc. 70(5), 709-710(1964)
[10] Michelot, C.:A finite algorithm for finding the projection of a point onto the canonical simples of Rn. J. Optim. Theory Appl. 50(1), 195-200(1986)
[11] Bertsekas, D.:On the Goldstein-Levitin-Polyak gradient projection method. IEEE Trans. Autom. Control 21(2), 174-183(1976)
[12] Dunn, J.C.:Global and asymptotic convergence rate estimates for a class of projected gradient processes. SIAM J. Control. Optim. 19(3), 368-400(1981)
[13] Gafni, E.M., Bertsekas, D.P.:Convergence of a gradient projection method. Massachusetts Institute of Technology, Laboratory for Information and Decision Systems Report LIDS-P-1201(1982)
[14] Calamai, P.H., Moré, J.J.:Projected gradient methods for linearly constrained problems. Math. Program. 39(1), 93-116(1987)
[15] Vulcano, G., van Ryzin, G., Ratliff, R.:Estimating primary demand for substitutable products from sales transaction data. Oper. Res. 60(2), 313-334(2012)
[16] van Ryzin, G., Vulcano, G.:An expectation-maximization method to estimate a rank-based choice model of demand. Oper. Res. 65(2), 396-407(2017)
