TY - JOUR

T1 - A scenario decomposition algorithm for stochastic programming problems with a class of downside risk measures

AU - Rysz, Maciej

AU - Vinel, Alexander

AU - Krokhmal, Pavlo

AU - Pasiliao, Eduardo L.

N1 - Funding Information:
This work was supported, in part, by the Air Force Office of Scientific Research [Grant FA9550-12-1-0142] and the U.S. Department of Air Force [Grant FA8651-12-2-0010]. In addition, support by the Air Force Research Lab Mathematical Modeling and Optimization Institute is gratefully acknowledged.
Publisher Copyright:
© 2015 INFORMS.

PY - 2015/3/1

Y1 - 2015/3/1

N2 - We present an efficient scenario decomposition algorithm for solving large-scale convex stochastic programming problems that involve a particular class of downside risk measures. The considered risk functionals encompass coherent and convex measures of risk that can be represented as an infimal convolution of a convex certainty equivalent, and include well-known measures, such as conditional value-at-risk, as special cases. The resulting structure of the feasible set is then exploited via iterative solving of relaxed problems, and it is shown that the number of iterations is bounded by a parameter that depends on the problem size. The computational performance of the developed scenario decomposition method is illustrated on portfolio optimization problems involving two families of nonlinear measures of risk, the higher-moment coherent risk measures, and log-exponential convex risk measures. It is demonstrated that for large-scale nonlinear problems the proposed approach can provide up to an order-of-magnitude improvement in computational time in comparison to state-of-the-art solvers, such as CPLEX, Gurobi, and MOSEK.

AB - We present an efficient scenario decomposition algorithm for solving large-scale convex stochastic programming problems that involve a particular class of downside risk measures. The considered risk functionals encompass coherent and convex measures of risk that can be represented as an infimal convolution of a convex certainty equivalent, and include well-known measures, such as conditional value-at-risk, as special cases. The resulting structure of the feasible set is then exploited via iterative solving of relaxed problems, and it is shown that the number of iterations is bounded by a parameter that depends on the problem size. The computational performance of the developed scenario decomposition method is illustrated on portfolio optimization problems involving two families of nonlinear measures of risk, the higher-moment coherent risk measures, and log-exponential convex risk measures. It is demonstrated that for large-scale nonlinear problems the proposed approach can provide up to an order-of-magnitude improvement in computational time in comparison to state-of-the-art solvers, such as CPLEX, Gurobi, and MOSEK.

KW - Certainty equivalent

KW - Higher-moment coherent risk measures

KW - Log-exponential convex risk measures

KW - Risk measures

KW - Scenario decomposition

KW - Stochastic optimization

KW - Utility theory

UR - http://www.scopus.com/inward/record.url?scp=84982291252&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84982291252&partnerID=8YFLogxK

U2 - 10.1287/ijoc.2014.0635

DO - 10.1287/ijoc.2014.0635

M3 - Article

AN - SCOPUS:84982291252

SN - 1091-9856

VL - 27

SP - 416

EP - 430

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

IS - 2

ER -