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]

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

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

Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192
[4]

Pengfei Wang, Mengyi Zhang, Huan Su. Input-to-state stability of infinite-dimensional stochastic nonlinear systems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021066
[5]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409
[6]

Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190
[7]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[8]

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

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321
[10]

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

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[12]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[13]

Seung-Yeal Ha, Dongnam Ko, Chanho Min, Xiongtao Zhang. Emergent collective behaviors of stochastic kuramoto oscillators. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1059-1081. doi: 10.3934/dcdsb.2019208
[14]

María J. Garrido-Atienza, Bohdan Maslowski, Jana  Šnupárková. Semilinear stochastic equations with bilinear fractional noise. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3075-3094. doi: 10.3934/dcdsb.2016088
[15]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[16]

Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089
[17]

Guangying Lv, Jinlong Wei, Guang-an Zou. Noise and stability in reaction-diffusion equations. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021005
[18]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[19]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[20]

Shangzhi Li, Shangjiang Guo. Permanence and extinction of a stochastic SIS epidemic model with three independent Brownian motions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2693-2719. doi: 10.3934/dcdsb.2020201

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences