Optimization Online


Polymatroids and Mean-Risk Minimization in Discrete Optimization

Alper Atamturk (atamturk***at***berkeley.edu)
Vishnu Narayanan (vishnu***at***ieor.berkeley.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 trade-off 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 mean-risk tradeoff is well-studied 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 mean-risk minimization for problems with discrete decision variables. In particular, we consider discrete optimization problems with a submodular mean-risk minimization objective. We show the connection between extended polymatroids and the convex lower envelope of this mean-risk objective. For 0-1 problems a complete linear characterization of the convex lower envelope is given. For mixed 0-1 problems we derive an exponential class of conic quadratic inequalities. We report computational experiments on a risk-aware 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 0-1 programming, value-at-risk, 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/


Entry Submitted: 11/29/2007
Entry Accepted: 11/29/2007
Entry Last Modified: 05/21/2009

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 Programming Society