American Institute of Mathematical Sciences

Advanced
January  2021, 17(1): 81-99. doi: 10.3934/jimo.2019100

Robust stochastic optimization with convex risk measures: A discretized subgradient scheme

Haodong Yu 1, and  Jie Sun 2,3,,

1. 

School of Statistics and Mathematics, Shanghai Lixin University of Accounting and Fiance, China
2. 

School of Mathematical Science, Chongqing Normal University, China
3. 

Faculty of Science and Engineering, Curtin University, Perth, Australia

* Corresponding author

Received  March 2018 Revised  July 2018 Published  September 2019

Fund Project: This work is partially supported by Grants 11401384, 11671029, 71631008 and B16002 of National Natural Science Foundation of China and by Grant DP160102819 of Australian Research Council

We study the distributionally robust stochastic optimization problem within a general framework of risk measures, in which the ambiguity set is described by a spectrum of practically used probability distribution constraints such as bounds on mean-deviation and entropic value-at-risk. We show that a subgradient of the objective function can be obtained by solving a finite-dimensional optimization problem, which facilitates subgradient-type algorithms for solving the robust stochastic optimization problem. We develop an algorithm for two-stage robust stochastic programming with conditional value at risk measure. A numerical example is presented to show the effectiveness of the proposed method.

Keywords: Stochastic optimization, distributionally robust, convex risk measure, subgradient method, two-stage optimization problem.
Mathematics Subject Classification: Primary: 90C15; 90C47.
Citation: Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100
References:
[1]

A. Ahmadi-Javid, Entropic value-at-risk: A new coherent risk measure, J. Optim. Theory Appl., 155 (2012), 1105-1123.  doi: 10.1007/s10957-011-9968-2.  Google Scholar

[2]

J. Ang, F. Meng and J. Sun, Two-stage stochastic linear programs with incomplete information on uncertainty, European J. Oper. Res., 233 (2014), 16-22.  doi: 10.1016/j.ejor.2013.07.039.  Google Scholar

[3]

M. Ang, J. Sun and Q. Yao, On the dual representation of coherent risk measures, Ann. Oper. Res., 262 (2018), 29-46.  doi: 10.1007/s10479-017-2441-3.  Google Scholar

[4]

D. P. Bertsekas, Convex optimization algorithms, Athena Scientific, Belmont, MA, 2015.  Google Scholar

[5]

D. P. Bertsekas, A. Nedi and A. E. Ozdaglar, Convex analysis and optimization, Athena Scientific, Belmont, MA, 2003.  Google Scholar

[6]

D. Bertsimas, X. V. Doan and K. Natarajan, Models for minimax stochastic linear optimization problems with risk aversion, Math. Oper. Res., 35 (2010), 580-602.  doi: 10.1287/moor.1100.0445.  Google Scholar

[7]

D. Bertsimas and R. Freund, Data, Models, and Decisions: The Fundamentals of Management Science, South-Western College Publishing, Cincinnati, OH, 2000. Google Scholar

[8]

D. Bertsimas, M. Sim and M. Zhang, Adaptive distributionally robust optimization, Manag. Sci., (2018). doi: 10.1287/mnsc.2017.2952.  Google Scholar

[9]

G. C. Calalore, Ambiguous risk measures and optimal robust portfolios, SIAM J. Optim., 18 (2007), 853-877.  doi: 10.1137/060654803.  Google Scholar

[10]

E. Delage and Y. Y. Ye, Distributionally robust optimization under moment uncertainty with application to data-driven problems, Oper. Res., 58 (2010), 595-612.  doi: 10.1287/opre.1090.0741.  Google Scholar

[11]

H. Föllmer and A. Schied, Stochastic finance, Walter de Gruyter & Co., Berlin, 2002. doi: 10.1515/9783110198065.  Google Scholar

[12]

S. Gao, L. Kong and J. Sun, Robust two-stage stochastic linear programs with moment constraints, Optimization, 63 (2014), 829-837.  doi: 10.1080/02331934.2014.906598.  Google Scholar

[13]

M. Grötschel, L. Lovász and and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), 169-197.  doi: 10.1007/BF02579273.  Google Scholar

[14]

Z. Hu and J. Hong, Kullback-Leibler divergence constrained distributionally robust optimization, Available from: http://www.optimization-online.org/DB_HTML/2012/11/3677.html. Google Scholar

[15]

D. Klabjan, D. Simchi-Levi and M. Song, Robust stochastic lot-sizing by means of histograms, Prod. Oper. Manag., 22 (2013), 691-710.  doi: 10.1111/j.1937-5956.2012.01420.x.  Google Scholar

[16]

B. Li, X. Qian, J. Sun, K. L. Teo and C. Yu, A model of distributionally robust two-stage stochastic convex programming with linear recourse, Appl. Math. Model., 58 (2018), 86-97.  doi: 10.1016/j.apm.2017.11.039.  Google Scholar

[17]

B. Li, Y. Rong, J. Sun and K. L. Teo, A distributionally robust linear receiver design for multi-access space-time block coded MIMO systems, IEEE Trans. Signal Process., 16 (2017), 464-474.  doi: 10.1109/TWC.2016.2625246.  Google Scholar

[18]

B. Li, Y. Rong, J. Sun and K. L. Teo, A distributionally robust minimum variance beamformer design, IEEE Signal Process. Lett., 25 (2018), 105-109.  doi: 10.1109/LSP.2017.2773601.  Google Scholar

[19]

B. Li, J. Sun, H. L. Xu and M. Zhang, A class of two-stage distributionally robust games, J. Ind. Manag. Optim., 15 (2019), 387-400.  doi: 10.3934/jimo.2018048.  Google Scholar

[20]

A. Ling, J. Sun and X. Yang, Robust tracking error portfolio selection with worst-case downside risk measures, J. Econom. Dynam. Control, 39 (2014), 178-207.  doi: 10.1016/j.jedc.2013.11.011.  Google Scholar

[21]

A. Ling, J. Sun, N. H. Xiu and X. Yang, Robust two-stage stochastic linear optimization with risk aversion, European J. Oper. Res., 256 (2017), 215-229.  doi: 10.1016/j.ejor.2016.06.017.  Google Scholar

[22]

H-J. Lüthi and J. Doege, Convex risk measures for portfolio optimization and concepts of flexibility, Math. Program., 104 (2005), 541-559.  doi: 10.1007/s10107-005-0628-x.  Google Scholar

[23]

S. Mehrotra and H. Zhang, Models and algorithms for distributionally robust least squares problems, Math. Program., 146 (2014), 123-141.  doi: 10.1007/s10107-013-0681-9.  Google Scholar

[24]

R. T. Rockafellar, Coherent approaches to risk in optimization under uncertainty, Tutorials in Operations Research, INFORMS, 2007, 38–61. doi: 10.1287/educ.1073.0032.  Google Scholar

[25]

R. T. Rockafellar and S. Uryasev, Optimization of conditional value-at-risk, J. Risk., 2 (2000), 21-42.  doi: 10.21314/JOR.2000.038.  Google Scholar

[26]

R. T. Rockafellar and S. Uryasev, Conditional value-at-risk for general loss distributions, J. Banking & Finance, 26 (2002), 1443-1471.  doi: 10.1016/S0378-4266(02)00271-6.  Google Scholar

[27]

W. W. Rogosinski, Moments of non-negative mass, Proc. Roy. Soc. London Ser. A, 245 (1958), 1-27.  doi: 10.1098/rspa.1958.0062.  Google Scholar

[28]

A. Shapiro and S. Ahmed, On a class of minimax stochastic programs, SIAM J. Optim., 14 (2004), 1237-1249.  doi: 10.1137/S1052623403434012.  Google Scholar

[29]

A. Shapiro, D. Dentcheva and A. Ruszczyski, Lectures on Stochastic Programming: Modeling and Theory, MPS/SIAM Series on Optimization, SIAM, Philadelphia, PA, 2009. doi: 10.1137/1.9780898718751.  Google Scholar

[30]

M. Sion, On general minimax theorems, Pacific J. Math., 8 (1958), 171-176.  doi: 10.2140/pjm.1958.8.171.  Google Scholar

[31]

J. Sun, L. Liao and B. Rodrigues, Quadratic two-stage stochastic optimization with coherent measures of risk, Math. Program., 168 (2018), 599-613.  doi: 10.1007/s10107-017-1131-x.  Google Scholar

[32]

W. Wiesemann, D. Kuhn and M. Sim, Distributionally robust convex optimization, Oper. Res., 62 (2014), 1358-1376.  doi: 10.1287/opre.2014.1314.  Google Scholar

show all references

References:
[1]

A. Ahmadi-Javid, Entropic value-at-risk: A new coherent risk measure, J. Optim. Theory Appl., 155 (2012), 1105-1123.  doi: 10.1007/s10957-011-9968-2.  Google Scholar

[2]

J. Ang, F. Meng and J. Sun, Two-stage stochastic linear programs with incomplete information on uncertainty, European J. Oper. Res., 233 (2014), 16-22.  doi: 10.1016/j.ejor.2013.07.039.  Google Scholar

[3]

M. Ang, J. Sun and Q. Yao, On the dual representation of coherent risk measures, Ann. Oper. Res., 262 (2018), 29-46.  doi: 10.1007/s10479-017-2441-3.  Google Scholar

[4]

D. P. Bertsekas, Convex optimization algorithms, Athena Scientific, Belmont, MA, 2015.  Google Scholar

[5]

D. P. Bertsekas, A. Nedi and A. E. Ozdaglar, Convex analysis and optimization, Athena Scientific, Belmont, MA, 2003.  Google Scholar

[6]

D. Bertsimas, X. V. Doan and K. Natarajan, Models for minimax stochastic linear optimization problems with risk aversion, Math. Oper. Res., 35 (2010), 580-602.  doi: 10.1287/moor.1100.0445.  Google Scholar

[7]

D. Bertsimas and R. Freund, Data, Models, and Decisions: The Fundamentals of Management Science, South-Western College Publishing, Cincinnati, OH, 2000. Google Scholar

[8]

D. Bertsimas, M. Sim and M. Zhang, Adaptive distributionally robust optimization, Manag. Sci., (2018). doi: 10.1287/mnsc.2017.2952.  Google Scholar

[9]

G. C. Calalore, Ambiguous risk measures and optimal robust portfolios, SIAM J. Optim., 18 (2007), 853-877.  doi: 10.1137/060654803.  Google Scholar

[10]

E. Delage and Y. Y. Ye, Distributionally robust optimization under moment uncertainty with application to data-driven problems, Oper. Res., 58 (2010), 595-612.  doi: 10.1287/opre.1090.0741.  Google Scholar

[11]

H. Föllmer and A. Schied, Stochastic finance, Walter de Gruyter & Co., Berlin, 2002. doi: 10.1515/9783110198065.  Google Scholar

[12]

S. Gao, L. Kong and J. Sun, Robust two-stage stochastic linear programs with moment constraints, Optimization, 63 (2014), 829-837.  doi: 10.1080/02331934.2014.906598.  Google Scholar

[13]

M. Grötschel, L. Lovász and and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), 169-197.  doi: 10.1007/BF02579273.  Google Scholar

[14]

Z. Hu and J. Hong, Kullback-Leibler divergence constrained distributionally robust optimization, Available from: http://www.optimization-online.org/DB_HTML/2012/11/3677.html. Google Scholar

[15]

D. Klabjan, D. Simchi-Levi and M. Song, Robust stochastic lot-sizing by means of histograms, Prod. Oper. Manag., 22 (2013), 691-710.  doi: 10.1111/j.1937-5956.2012.01420.x.  Google Scholar

[16]

B. Li, X. Qian, J. Sun, K. L. Teo and C. Yu, A model of distributionally robust two-stage stochastic convex programming with linear recourse, Appl. Math. Model., 58 (2018), 86-97.  doi: 10.1016/j.apm.2017.11.039.  Google Scholar

[17]

B. Li, Y. Rong, J. Sun and K. L. Teo, A distributionally robust linear receiver design for multi-access space-time block coded MIMO systems, IEEE Trans. Signal Process., 16 (2017), 464-474.  doi: 10.1109/TWC.2016.2625246.  Google Scholar

[18]

B. Li, Y. Rong, J. Sun and K. L. Teo, A distributionally robust minimum variance beamformer design, IEEE Signal Process. Lett., 25 (2018), 105-109.  doi: 10.1109/LSP.2017.2773601.  Google Scholar

[19]

B. Li, J. Sun, H. L. Xu and M. Zhang, A class of two-stage distributionally robust games, J. Ind. Manag. Optim., 15 (2019), 387-400.  doi: 10.3934/jimo.2018048.  Google Scholar

[20]

A. Ling, J. Sun and X. Yang, Robust tracking error portfolio selection with worst-case downside risk measures, J. Econom. Dynam. Control, 39 (2014), 178-207.  doi: 10.1016/j.jedc.2013.11.011.  Google Scholar

[21]

A. Ling, J. Sun, N. H. Xiu and X. Yang, Robust two-stage stochastic linear optimization with risk aversion, European J. Oper. Res., 256 (2017), 215-229.  doi: 10.1016/j.ejor.2016.06.017.  Google Scholar

[22]

H-J. Lüthi and J. Doege, Convex risk measures for portfolio optimization and concepts of flexibility, Math. Program., 104 (2005), 541-559.  doi: 10.1007/s10107-005-0628-x.  Google Scholar

[23]

S. Mehrotra and H. Zhang, Models and algorithms for distributionally robust least squares problems, Math. Program., 146 (2014), 123-141.  doi: 10.1007/s10107-013-0681-9.  Google Scholar

[24]

R. T. Rockafellar, Coherent approaches to risk in optimization under uncertainty, Tutorials in Operations Research, INFORMS, 2007, 38–61. doi: 10.1287/educ.1073.0032.  Google Scholar

[25]

R. T. Rockafellar and S. Uryasev, Optimization of conditional value-at-risk, J. Risk., 2 (2000), 21-42.  doi: 10.21314/JOR.2000.038.  Google Scholar

[26]

R. T. Rockafellar and S. Uryasev, Conditional value-at-risk for general loss distributions, J. Banking & Finance, 26 (2002), 1443-1471.  doi: 10.1016/S0378-4266(02)00271-6.  Google Scholar

[27]

W. W. Rogosinski, Moments of non-negative mass, Proc. Roy. Soc. London Ser. A, 245 (1958), 1-27.  doi: 10.1098/rspa.1958.0062.  Google Scholar

[28]

A. Shapiro and S. Ahmed, On a class of minimax stochastic programs, SIAM J. Optim., 14 (2004), 1237-1249.  doi: 10.1137/S1052623403434012.  Google Scholar

[29]

A. Shapiro, D. Dentcheva and A. Ruszczyski, Lectures on Stochastic Programming: Modeling and Theory, MPS/SIAM Series on Optimization, SIAM, Philadelphia, PA, 2009. doi: 10.1137/1.9780898718751.  Google Scholar

[30]

M. Sion, On general minimax theorems, Pacific J. Math., 8 (1958), 171-176.  doi: 10.2140/pjm.1958.8.171.  Google Scholar

[31]

J. Sun, L. Liao and B. Rodrigues, Quadratic two-stage stochastic optimization with coherent measures of risk, Math. Program., 168 (2018), 599-613.  doi: 10.1007/s10107-017-1131-x.  Google Scholar

[32]

W. Wiesemann, D. Kuhn and M. Sim, Distributionally robust convex optimization, Oper. Res., 62 (2014), 1358-1376.  doi: 10.1287/opre.2014.1314.  Google Scholar

Table 1.  parameters of the test problem
$ w $(Wrench) $ p $(Plier)
$ x $: Steel A(lbs.) 1.5 1
$ y $: Steel B(lbs.) 1 2
Molding Machine (hours) 1 1
Assembly Machine (hours) .3 .5
Contribution to Earnings (＄/1000 units) 130 100
Table Options

Download as excel

$ w $(Wrench) $ p $(Plier)
$ x $: Steel A(lbs.) 1.5 1
$ y $: Steel B(lbs.) 1 2
Molding Machine (hours) 1 1
Assembly Machine (hours) .3 .5
Contribution to Earnings (＄/1000 units) 130 100
Table 2.  combined distribution of $ h $
$ h_2 $ $ h_1 $
21000 25000
8000 0.25 0.25
10000 0.25 0.25
Table Options

Download as excel

$ h_2 $ $ h_1 $
21000 25000
8000 0.25 0.25
10000 0.25 0.25
Table 3.  possible values of h
$ i $ 1 2 3 4
$ h_{1i} $ 21000 21000 25000 25000
$ h_{2i} $ 8000 10000 8000 10000
Table Options

Download as excel

$ i $ 1 2 3 4
$ h_{1i} $ 21000 21000 25000 25000
$ h_{2i} $ 8000 10000 8000 10000
Table 4.  production plans under various scenarios
$ i $ 1 2 3 4
$ w_i $ 7988 9969 8000 9969
$ p_i $ 77 10 27 10
Table Options

Download as excel

$ i $ 1 2 3 4
$ w_i $ 7988 9969 8000 9969
$ p_i $ 77 10 27 10
Table 5.  worst-case distribution of $ h $
Pro 0.5 0.0134 0.0539 0.0006 0.4321
$ h_1 $ 22355 22216 21008 22239 24021
$ h_2 $ 8000 10000 10000 10000 10000
Table Options

Download as excel

Pro 0.5 0.0134 0.0539 0.0006 0.4321
$ h_1 $ 22355 22216 21008 22239 24021
$ h_2 $ 8000 10000 10000 10000 10000
[1]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023
[2]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[3]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[4]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[5]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[6]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[7]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008
[8]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[9]

Min Li, Jiahua Zhang, Yifan Xu, Wei Wang. Effects of disruption risk on a supply chain with a risk-averse retailer. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021024
[10]

Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281
[11]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931
[12]

Joel Fotso Tachago, Giuliano Gargiulo, Hubert Nnang, Elvira Zappale. Multiscale homogenization of integral convex functionals in Orlicz Sobolev setting. Evolution Equations & Control Theory, 2021, 10 (2) : 297-320. doi: 10.3934/eect.2020067
[13]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[14]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[15]

M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072
[16]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881
[17]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009
[18]

Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933
[19]

Zhigang Pan, Chanh Kieu, Quan Wang. Hopf bifurcations and transitions of two-dimensional Quasi-Geostrophic flows. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021025
[20]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (191)
  • HTML views (598)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences