  


A Convex Optimization Approach for Computing Correlated Choice Probabilities with Many Alternatives
Selin Ahipasaoglu (ahipasaoglusutd.edu.sg) Abstract: A popular discrete choice model that incorporates correlation information is the Multinomial Probit (MNP) model where the random utilities of the alternatives are chosen from a multivariate normal distribution. Computing the choice probabilities is challenging in the MNP model when the number of alternatives is large and simulation is used to approximate the choice probabilities. Mishra, Natarajan and Teo (IEEE Transactions on Automatic Control, 2012) have recently proposed a semidefinite optimization approach to compute choice probabilities for the joint distribution of the random utilities that maximizes expected agent utility given only the mean, variance and covariance information. Their model is referred to as the Cross Moment (CMM) model. Computing the choice probabilities is challenging in the CMM model when the number of alternatives is large as one needs to solve large scale semidefinite programs. By bringing together results from economics, matrix analysis and convex optimization, we develop a simple and efficient first order gradient ascent method to compute choice probabilities in the CMM model. Numerical experiments show that this method can compute choice probabilities for up to 5000 alternatives within $2$ hours on a standard laptop while explicitly capturing the correlation information. Comparisons with MNP in terms of computational times and choice probabilities are also provided. Keywords: Choice Models, Optimization, Probability Models Category 1: Robust Optimization Category 2: Applications  OR and Management Sciences Category 3: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 09/09/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  