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

作     者：Ahipasaoglu, Selin Damla Li, Xiaobo Natarajan, Karthik 

作者机构：Singapore Univ Technol & Design Engn Syst & Design Singapore 487372 Singapore Natl Univ Singapore Dept Ind Syst Engn & Management Singapore 117576 Singapore 

出 版 物：《IEEE TRANSACTIONS ON AUTOMATIC CONTROL》 (IEEE自动控制汇刊)

年 卷 期：2019年第64卷第1期

页      面：190-205页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0811[工学-控制科学与工程] 

基　　金：SUTD-MIT International Design Center [IDG31300105] MOE Tier 2 Grant [MOE2013-T2-2-168] 

主　　题：Choice probability optimization optimization algorithms stochastic systems 

摘      要：A popular discrete choice model that incorporates correlation information is themultinomial 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. Mishra et al. (IEEE Transactions on Automatic Control, 2012) have proposed a semidefinite optimization approach to compute choice probabilities for the 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 with many alternatives is challenging in the CMM model, since one needs to solve large-scale semidefinite programs. We develop a simpler formulation as a representative agent model by maximizing over the choice probabilities in the unit simplex where the objective function is the sum of the expected utilities and a strongly concave perturbation function. By characterizing the perturbation function for the CMM model and its gradient, we develop a simple first-order gradient method with inexact line search to compute choice probabilities. We establish local linear convergence of this algorithm under mild assumptions on the choice probabilities. An implication of our results is that inverting the choice probabilities to compute the mean utilities is straightforward given any positive-definite covariance matrix. Numerical experiments show that this method can compute choice probabilities for a large number of alternatives within a reasonable amount of time while explicitly capturing the correlation information. Comparisons with simulationmethods for MNP and semidefinite programming methods for CMM indicate the efficacy of the method.