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.