Robust Discrete Optimization and Downside Risk Measures, Working Paper

We propose methods for robust discrete optimization in which the objective function has cost components that are subject to independent and bounded perturbations. Motivated by risk management practice, we approximate the problem of optimization of VaR, a widely used downside risk measure by introducing four approximating models that origininate in robust optimization. We show that all four models allow the fexibility of adjusting the level of conservativism such that the probability of the actual cost being less than a specified level, in the worst case distribution, is at least 1- α. Under a robust model with ellipsoidal uncertainty set, we propose a Frank-Wolfe type algorithm that we show converges to a locally optimal solution, and in computational experiments is remarkably effective. We propose a robust model that is at most 1 + ε more conservative than the ellipsoidal uncertainty set model and show that we can reduce the robust model to solving a polynomial number of nominal problems. We generalize our earlier proposed framework and show that it results in decreased conservatism, while maintaining the complexity of the nominal problem. Among the proposed robust models, we show both theoretically and computationally that the robust model under ellipsoidal uncertainty set is the least conservative