American Institute of Mathematical Sciences

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

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

Zhiping Chen 1, and  Youpan Han 2,

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.
Keywords: Stochastic quadratic programming, stability, sample average approximation., probability metric, Lipschitz continuity.
Mathematics Subject Classification: Primary: 90C15, 90C20,90C3.
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  doi: 10.3934/fods.2020017
[2]

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

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
[4]

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
[5]

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

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

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[8]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[9]

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
[10]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[11]

Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020450
[12]

Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020323
[13]

Xin-Guang Yang, Lu Li, Xingjie Yan, Ling Ding. The structure and stability of pullback attractors for 3D Brinkman-Forchheimer equation with delay. Electronic Research Archive, 2020, 28 (4) : 1395-1418. doi: 10.3934/era.2020074
[14]

Chao Xing, Jiaojiao Pan, Hong Luo. Stability and dynamic transition of a toxin-producing phytoplankton-zooplankton model with additional food. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020275
[15]

A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441
[16]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264
[17]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317
[18]

Xuhui Peng, Rangrang Zhang. Approximations of stochastic 3D tamed Navier-Stokes equations. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5337-5365. doi: 10.3934/cpaa.2020241
[19]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047
[20]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences