  


Polymatroids and MeanRisk Minimization in Discrete Optimization
Alper Atamturk (atamturkberkeley.edu) Abstract: In financial markets high levels of risk are associated with large returns as well as large losses, whereas with lower levels of risk, the potential for either return or loss is small. Therefore, risk management is fundamentally concerned with finding an optimal tradeoff between risk and return matching an investor's risk tolerance. Managing risk is studied mostly in a financial context; nevertheless, it is certainly relevant in any area with a significant source of uncertainty. The meanrisk tradeoff is wellstudied for problems with a convex feasible set. However, this is not the case in the discrete setting, even though, in practice, portfolios are often restricted to discrete choices. In this paper we study meanrisk minimization for problems with discrete decision variables. In particular, we consider discrete optimization problems with a submodular meanrisk minimization objective. We show the connection between extended polymatroids and the convex lower envelope of this meanrisk objective. For 01 problems a complete linear characterization of the convex lower envelope is given. For mixed 01 problems we derive an exponential class of conic quadratic inequalities. We report computational experiments on a riskaware capital budgeting problem with uncertain returns on investments with discrete choices. The results show significant improvements in the solvability of the problem with the introduced convexification method. Keywords: Conic mixed 01 programming, valueatrisk, ellipsoidal uncertainty sets, submodular functions Category 1: Integer Programming Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 3: Combinatorial Optimization (Graphs and Matroids ) Citation: Appeared in Operations Research Letters. Check http://www.ieor.berkeley.edu/~atamturk/ Download: Entry Submitted: 11/29/2007 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  