We consider the problem of making choice prediction by optimizing the expectation of maximum utility in discrete choice situations, and propose a discrete choice model which generates choice probabilities through a semidefinite program. The choice model, termed as the cross moment model (CMM) is parsimonious in that it uses only the mean and covariance information of the utilities. It is encouraging that CMM generates reasonable choice estimates when utilities are correlated even though no distributional assumptions on random utilities are made. We present a few examples in route choice setting and random walk to test the quality of choice prediction using CMM. By capturing correlations among utilities, CMM avoids some of the common behavioral limitations, such as the Independence of Irrelevant Alternatives and the Invariate Proportion of Substitution, present in several discrete choice models. Being a convex optimization problem, it obviates the use of exhaustive simulation in computing choice probabilities for which the multinomial probit (MNP) model is often criticized. CMM can be easily used in design problems such as product-line selection and assortment planning. We exploit CMM to solve a flexible packaging design problem faced by online retailers and warehouses. We use the data provided by a local service part supplier for this design problem and compare the results with Multinomial Logit and MNP models. We find that CMM not only captures utility correlations in this problem and provides good designs but also has computational advantages over MNP which uses simulation.