Optimization Online


A Convex Optimization Approach for Computing Correlated Choice Probabilities with Many Alternatives

Selin Ahipasaoglu (ahipasaoglu***at***sutd.edu.sg)
Xiaobo Li (lixx3195***at***umn.edu)
Karthik Natarajan (natarajan_karthik***at***sutd.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 (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 09/09/2013
Entry Accepted: 09/09/2013
Entry Last Modified: 05/31/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society