2015, 5(2): 197-209. doi: 10.3934/naco.2015.5.197

Continuity and stability of two-stage stochastic programs with quadratic continuous recourse

1. 

Department of Computing Science, School of Mathematics and Statistics, Xi'an Jiaotong University, 710049 Xi'an, Shanxi, China

2. 

School of Science, Xi'an Polytechnic University,710048 Xi'an, Shanxi, China

Received  September 2014 Revised  May 2015 Published  June 2015

For two-stage stochastic programs with quadratic continuous recourse where all the coefficients in the objective function and the right-hand side vector in the second-stage constraints vary simultaneously, we firstly show the locally Lipschtiz continuity of the optimal value function of the recourse problem, then under suitable probability metric, we derive the joint Lipschitz continuity of the expected optimal value function with respect to the first-stage variables and the probability distribution. Furthermore, we establish the qualitative and quantitative stability results of the optimal value function and the optimal solution set with respect to the Fortet-Mourier probability metric, when the underlying probability distribution is perturbed. Finally, we show the exponential convergence rate of the optimal value sequence when we solve two-stage quadratic stochastic programs by the sample average approximation method.
Citation: Zhiping Chen, Youpan Han. Continuity and stability of two-stage stochastic programs with quadratic continuous recourse. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 197-209. doi: 10.3934/naco.2015.5.197
References:
[1]

B. Bank, J. Guddat, D. Klatte, B. Kummer and K. Tammer, Non-Linear Parametric Optimization,, Akademie Verlag, (1982).   Google Scholar

[2]

J. R. Birge and F. Louveaux, Introduction to Stochastic Programming,, Springer, (1997).   Google Scholar

[3]

X. Chen, L. Qi and R. S. Womersley, Newton's method for quadratic stochastic programs with recourse,, J. Comput. Appl. Math., 60 (1995), 29.  doi: 10.1016/0377-0427(94)00082-C.  Google Scholar

[4]

X. Chen and R. S. Womersley, Random test problems and parallel methods for quadratic programs and quadratic stochastic programs,, Optim. Method Softw., 13 (2000), 275.  doi: 10.1080/10556780008805789.  Google Scholar

[5]

G. M. Cho, Log-barrier method for two-stage quadratic stochastic programming,, Appl. Math. Comput., 164 (2005), 45.  doi: 10.1016/j.amc.2004.04.095.  Google Scholar

[6]

A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications,, Springer-Verlag, (1998).  doi: 10.1007/978-1-4612-5320-4.  Google Scholar

[7]

M. A. Goberna, M. A. López, Linear Semi-Infinite Optimization,, John Wiley and sons, (1998).   Google Scholar

[8]

Y. Han and Z. Chen, Quantitative stability of full random two-stage stochastic programs with recourse,, Optim. Lett., ().   Google Scholar

[9]

P. Kall and S. W. Wallace, Stochastic Programming,, John Wiley and Sons, (1994).   Google Scholar

[10]

W. K. Klein Haneveld and M. H. Van der Vlerk, Stochastic integer programming: general models and algorithms,, Ann. Oper. Res., 85 (1999), 39.  doi: 10.1023/A:1018930113099.  Google Scholar

[11]

O. L. Mangasarian and T. H. Shiau, Lipschitz continuity of solutions of linear inequalities, programs, and complementary problems,, SIAM J. Control Optim., 25 (1987), 583.  doi: 10.1137/0325033.  Google Scholar

[12]

S. Mehrotra and M. G. Özevin, Decomposition-based interior point methods for two-stage stochastic convex quadratic programs with recourse,, Oper. Res., 57 (2009), 964.  doi: 10.1287/opre.1080.0659.  Google Scholar

[13]

E. L. Plambeck, B. R. Fu, S. M. Robinson and R. Suri, Sample-path optimization of convex stochastic performances functions,, Math. Program., 75 (1996), 137.  doi: 10.1016/S0025-5610(96)00010-X.  Google Scholar

[14]

A. Prekopa, Stochastic Programming,, Kluwer Academic Publishers, (1995).  doi: 10.1007/978-94-017-3087-7.  Google Scholar

[15]

L. Qi and R. S. Womersley, An SQP algorithm for extended linear-quadratic problems in stochastic programming,, Ann. Oper. Res., 56 (1995), 251.  doi: 10.1007/BF02031711.  Google Scholar

[16]

S. T. Rachev, W. Römisch, Quantitative stability in stochastic programming: the methods of probability metrics,, Math. Oper. Res., 27 (2002), 792.  doi: 10.1287/moor.27.4.792.304.  Google Scholar

[17]

S. M. Robinson, Analysis of sample-path optimization,, Math. Oper. Res., 21 (1996), 513.  doi: 10.1287/moor.21.3.513.  Google Scholar

[18]

R. T. Rockafeller and R.J-B. Wets, A lagrangian finite generation technique for solving linear-quadratic problems in stochastic programming,, Math. Program. study, 28 (1986), 63.   Google Scholar

[19]

R. T. Rockafeller and R. J-B. Wets, Variational Analysis,, Springer, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[20]

W. Römisch, Stability of stochastic programming,, in Stochastic Programming: Handbooks in Operations Research and Management Science Vol.10 (eds. A. Rusczyński, (2003), 483.  doi: 10.1016/S0927-0507(03)10008-4.  Google Scholar

[21]

W. Römisch and R. Schultz, Distribution sensitivity in stochastic programming,, Math. Program., 50 (1991), 197.  doi: 10.1007/BF01594935.  Google Scholar

[22]

W. Römisch and R. Schultz, Lipschitz stability for stochastic programs with complete recourse,, SIAM J. Optim., 6 (1996), 531.  doi: 10.1137/0806028.  Google Scholar

[23]

W. Römisch and R. J.-B. Wets, Stability of ε-approximate solutions to convex stochastic programs,, SIAM J. Optim., 18 (2007), 961.  doi: 10.1137/060657716.  Google Scholar

[24]

A. Shapiro, Monte Carlo sampling methods,, in Stochastic Programming: Handbooks in Operations Research and Management Science Vol.10 (eds. A. Rusczyński, (2003), 353.  doi: 10.1016/S0927-0507(03)10006-0.  Google Scholar

[25]

A. Shapiro and T. Homem-de-Mello, On rate of convergence of Monte Carlo approximations of stochastic programs,, SIAM J. Optim., 6 (1996), 531.   Google Scholar

[26]

A. Shapiro, Complexity of two and multi-stage stochastic programming problems,, 2005. Available from: , ().   Google Scholar

show all references

References:
[1]

B. Bank, J. Guddat, D. Klatte, B. Kummer and K. Tammer, Non-Linear Parametric Optimization,, Akademie Verlag, (1982).   Google Scholar

[2]

J. R. Birge and F. Louveaux, Introduction to Stochastic Programming,, Springer, (1997).   Google Scholar

[3]

X. Chen, L. Qi and R. S. Womersley, Newton's method for quadratic stochastic programs with recourse,, J. Comput. Appl. Math., 60 (1995), 29.  doi: 10.1016/0377-0427(94)00082-C.  Google Scholar

[4]

X. Chen and R. S. Womersley, Random test problems and parallel methods for quadratic programs and quadratic stochastic programs,, Optim. Method Softw., 13 (2000), 275.  doi: 10.1080/10556780008805789.  Google Scholar

[5]

G. M. Cho, Log-barrier method for two-stage quadratic stochastic programming,, Appl. Math. Comput., 164 (2005), 45.  doi: 10.1016/j.amc.2004.04.095.  Google Scholar

[6]

A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications,, Springer-Verlag, (1998).  doi: 10.1007/978-1-4612-5320-4.  Google Scholar

[7]

M. A. Goberna, M. A. López, Linear Semi-Infinite Optimization,, John Wiley and sons, (1998).   Google Scholar

[8]

Y. Han and Z. Chen, Quantitative stability of full random two-stage stochastic programs with recourse,, Optim. Lett., ().   Google Scholar

[9]

P. Kall and S. W. Wallace, Stochastic Programming,, John Wiley and Sons, (1994).   Google Scholar

[10]

W. K. Klein Haneveld and M. H. Van der Vlerk, Stochastic integer programming: general models and algorithms,, Ann. Oper. Res., 85 (1999), 39.  doi: 10.1023/A:1018930113099.  Google Scholar

[11]

O. L. Mangasarian and T. H. Shiau, Lipschitz continuity of solutions of linear inequalities, programs, and complementary problems,, SIAM J. Control Optim., 25 (1987), 583.  doi: 10.1137/0325033.  Google Scholar

[12]

S. Mehrotra and M. G. Özevin, Decomposition-based interior point methods for two-stage stochastic convex quadratic programs with recourse,, Oper. Res., 57 (2009), 964.  doi: 10.1287/opre.1080.0659.  Google Scholar

[13]

E. L. Plambeck, B. R. Fu, S. M. Robinson and R. Suri, Sample-path optimization of convex stochastic performances functions,, Math. Program., 75 (1996), 137.  doi: 10.1016/S0025-5610(96)00010-X.  Google Scholar

[14]

A. Prekopa, Stochastic Programming,, Kluwer Academic Publishers, (1995).  doi: 10.1007/978-94-017-3087-7.  Google Scholar

[15]

L. Qi and R. S. Womersley, An SQP algorithm for extended linear-quadratic problems in stochastic programming,, Ann. Oper. Res., 56 (1995), 251.  doi: 10.1007/BF02031711.  Google Scholar

[16]

S. T. Rachev, W. Römisch, Quantitative stability in stochastic programming: the methods of probability metrics,, Math. Oper. Res., 27 (2002), 792.  doi: 10.1287/moor.27.4.792.304.  Google Scholar

[17]

S. M. Robinson, Analysis of sample-path optimization,, Math. Oper. Res., 21 (1996), 513.  doi: 10.1287/moor.21.3.513.  Google Scholar

[18]

R. T. Rockafeller and R.J-B. Wets, A lagrangian finite generation technique for solving linear-quadratic problems in stochastic programming,, Math. Program. study, 28 (1986), 63.   Google Scholar

[19]

R. T. Rockafeller and R. J-B. Wets, Variational Analysis,, Springer, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[20]

W. Römisch, Stability of stochastic programming,, in Stochastic Programming: Handbooks in Operations Research and Management Science Vol.10 (eds. A. Rusczyński, (2003), 483.  doi: 10.1016/S0927-0507(03)10008-4.  Google Scholar

[21]

W. Römisch and R. Schultz, Distribution sensitivity in stochastic programming,, Math. Program., 50 (1991), 197.  doi: 10.1007/BF01594935.  Google Scholar

[22]

W. Römisch and R. Schultz, Lipschitz stability for stochastic programs with complete recourse,, SIAM J. Optim., 6 (1996), 531.  doi: 10.1137/0806028.  Google Scholar

[23]

W. Römisch and R. J.-B. Wets, Stability of ε-approximate solutions to convex stochastic programs,, SIAM J. Optim., 18 (2007), 961.  doi: 10.1137/060657716.  Google Scholar

[24]

A. Shapiro, Monte Carlo sampling methods,, in Stochastic Programming: Handbooks in Operations Research and Management Science Vol.10 (eds. A. Rusczyński, (2003), 353.  doi: 10.1016/S0927-0507(03)10006-0.  Google Scholar

[25]

A. Shapiro and T. Homem-de-Mello, On rate of convergence of Monte Carlo approximations of stochastic programs,, SIAM J. Optim., 6 (1996), 531.   Google Scholar

[26]

A. Shapiro, Complexity of two and multi-stage stochastic programming problems,, 2005. Available from: , ().   Google Scholar

[1]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017

[2]

Patrick Martinez, Judith Vancostenoble. Lipschitz stability for the growth rate coefficients in a nonlinear Fisher-KPP equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 695-721. doi: 10.3934/dcdss.2020362

[3]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[4]

Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Existence results and stability analysis for a nonlinear fractional boundary value problem on a circular ring with an attached edge : A study of fractional calculus on metric graph. Networks & Heterogeneous Media, 2021  doi: 10.3934/nhm.2021003

[5]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026

[6]

Reza Chaharpashlou, Abdon Atangana, Reza Saadati. On the fuzzy stability results for fractional stochastic Volterra integral equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020432

[7]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012

[8]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384

[9]

Lingwei Ma, Zhenqiu Zhang. Monotonicity for fractional Laplacian systems in unbounded Lipschitz domains. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 537-552. doi: 10.3934/dcds.2020268

[10]

Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325

[11]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374

[12]

Xiaoming Wang. Upper semi-continuity of stationary statistical properties of dissipative systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 521-540. doi: 10.3934/dcds.2009.23.521

[13]

Yu Yuan, Zhibin Liang, Xia Han. Optimal investment and reinsurance to minimize the probability of drawdown with borrowing costs. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021003

[14]

Yanan Li, Zhijian Yang, Na Feng. Uniform attractors and their continuity for the non-autonomous Kirchhoff wave models. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021018

[15]

Bing Liu, Ming Zhou. Robust portfolio selection for individuals: Minimizing the probability of lifetime ruin. Journal of Industrial & Management Optimization, 2021, 17 (2) : 937-952. doi: 10.3934/jimo.2020005

[16]

Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389

[17]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[18]

Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020364

[19]

Giulia Luise, Giuseppe Savaré. Contraction and regularizing properties of heat flows in metric measure spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 273-297. doi: 10.3934/dcdss.2020327

[20]

Soonki Hong, Seonhee Lim. Martin boundary of brownian motion on Gromov hyperbolic metric graphs. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021014

 Impact Factor: 

Metrics

  • PDF downloads (62)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]