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  January 2021 Early access  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 and 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.

[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.

[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.

[4]

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

[5]

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

[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.

[7]

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

[8]

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

[9]

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

[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.

[11]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[28]

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

[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.

[30]

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

[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.

[32]

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

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.

[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.

[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.

[4]

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

[5]

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

[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.

[7]

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

[8]

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

[9]

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

[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.

[11]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[28]

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

[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.

[30]

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

[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.

[32]

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

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]

Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial and Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109
[2]

Bin Li, Jie Sun, Honglei Xu, Min Zhang. A class of two-stage distributionally robust games. Journal of Industrial and Management Optimization, 2019, 15 (1) : 387-400. doi: 10.3934/jimo.2018048
[3]

Zhimin Liu, Shaojian Qu, Hassan Raza, Zhong Wu, Deqiang Qu, Jianhui Du. Two-stage mean-risk stochastic mixed integer optimization model for location-allocation problems under uncertain environment. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2783-2804. doi: 10.3934/jimo.2020094
[4]

Fengming Lin, Xiaolei Fang, Zheming Gao. Distributionally Robust Optimization: A review on theory and applications. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 159-212. doi: 10.3934/naco.2021057
[5]

Bin Zhou, Hailin Sun. Two-stage stochastic variational inequalities for Cournot-Nash equilibrium with risk-averse players under uncertainty. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 521-535. doi: 10.3934/naco.2020049
[6]

Chien Hsun Tseng. Applications of a nonlinear optimization solver and two-stage comprehensive Denoising techniques for optimum underwater wideband sonar echolocation system. Journal of Industrial and Management Optimization, 2013, 9 (1) : 205-225. doi: 10.3934/jimo.2013.9.205
[7]

Yufei Sun, Grace Aw, Kok Lay Teo, Guanglu Zhou. Portfolio optimization using a new probabilistic risk measure. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1275-1283. doi: 10.3934/jimo.2015.11.1275
[8]

Jingzhi Li, Hongyu Liu, Qi Wang. Fast imaging of electromagnetic scatterers by a two-stage multilevel sampling method. Discrete and Continuous Dynamical Systems - S, 2015, 8 (3) : 547-561. doi: 10.3934/dcdss.2015.8.547
[9]

Zhiping Chen, Youpan Han. Continuity and stability of two-stage stochastic programs with quadratic continuous recourse. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 197-209. doi: 10.3934/naco.2015.5.197
[10]

Tugba Sarac, Aydin Sipahioglu, Emine Akyol Ozer. A two-stage solution approach for plastic injection machines scheduling problem. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1289-1314. doi: 10.3934/jimo.2020022
[11]

Xi Chen, Zongrun Wang, Songhai Deng, Yong Fang. Risk measure optimization: Perceived risk and overconfidence of structured product investors. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1473-1492. doi: 10.3934/jimo.2018105
[12]

Jie Jiang, Zhiping Chen, He Hu. Stability of a class of risk-averse multistage stochastic programs and their distributionally robust counterparts. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2415-2440. doi: 10.3934/jimo.2020075
[13]

Yuli Zhang, Lin Han, Xiaotian Zhuang. Distributionally robust front distribution center inventory optimization with uncertain multi-item orders. Discrete and Continuous Dynamical Systems - S, 2022, 15 (7) : 1777-1795. doi: 10.3934/dcdss.2022006
[14]

Gang Li, Minghua Li, Yaohua Hu. Stochastic quasi-subgradient method for stochastic quasi-convex feasibility problems. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 713-725. doi: 10.3934/dcdss.2021127
[15]

Jutamas Kerdkaew, Rabian Wangkeeree. Characterizing robust weak sharp solution sets of convex optimization problems with uncertainty. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2651-2673. doi: 10.3934/jimo.2019074
[16]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283
[17]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171
[18]

Chao Mi, Jun Wang, Weijian Mi, Youfang Huang, Zhiwei Zhang, Yongsheng Yang, Jun Jiang, Postolache Octavian. Research on regional clustering and two-stage SVM method for container truck recognition. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1117-1133. doi: 10.3934/dcdss.2019077
[19]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363
[20]

Rüdiger Schultz. Two-stage stochastic programs: Integer variables, dominance relations and PDE constraints. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 713-738. doi: 10.3934/naco.2012.2.713

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (417)
  • HTML views (868)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy