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]

Suxiang He, Pan Zhang, Xiao Hu, Rong Hu. A sample average approximation method based on a D-gap function for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 977-987. doi: 10.3934/jimo.2014.10.977

[2]

Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1

[3]

Mingzheng Wang, M. Montaz Ali, Guihua Lin. Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks. Journal of Industrial & Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317

[4]

Katrin Grunert, Helge Holden, Xavier Raynaud. Lipschitz metric for the Camassa--Holm equation on the line. Discrete & Continuous Dynamical Systems - A, 2013, 33 (7) : 2809-2827. doi: 10.3934/dcds.2013.33.2809

[5]

Anne-Sophie de Suzzoni. Continuity of the flow of the Benjamin-Bona-Mahony equation on probability measures. Discrete & Continuous Dynamical Systems - A, 2015, 35 (7) : 2905-2920. doi: 10.3934/dcds.2015.35.2905

[6]

Michela Eleuteri, Paolo Marcellini, Elvira Mascolo. Local Lipschitz continuity of minimizers with mild assumptions on the $x$-dependence. Discrete & Continuous Dynamical Systems - S, 2019, 12 (2) : 251-265. doi: 10.3934/dcdss.2019018

[7]

Xiangxiang Huang, Xianping Guo, Jianping Peng. A probability criterion for zero-sum stochastic games. Journal of Dynamics & Games, 2017, 4 (4) : 369-383. doi: 10.3934/jdg.2017020

[8]

Wei Mao, Liangjian Hu, Xuerong Mao. Asymptotic boundedness and stability of solutions to hybrid stochastic differential equations with jumps and the Euler-Maruyama approximation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 587-613. doi: 10.3934/dcdsb.2018198

[9]

Andrea Tosin, Paolo Frasca. Existence and approximation of probability measure solutions to models of collective behaviors. Networks & Heterogeneous Media, 2011, 6 (3) : 561-596. doi: 10.3934/nhm.2011.6.561

[10]

Davor Dragičević. Admissibility, a general type of Lipschitz shadowing and structural stability. Communications on Pure & Applied Analysis, 2015, 14 (3) : 861-880. doi: 10.3934/cpaa.2015.14.861

[11]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[12]

Luis D'Alto, Martin Corless. Incremental quadratic stability. Numerical Algebra, Control & Optimization, 2013, 3 (1) : 175-201. doi: 10.3934/naco.2013.3.175

[13]

Maria do Rosário de Pinho, Ilya Shvartsman. Lipschitz continuity of optimal control and Lagrange multipliers in a problem with mixed and pure state constraints. Discrete & Continuous Dynamical Systems - A, 2011, 29 (2) : 505-522. doi: 10.3934/dcds.2011.29.505

[14]

Aram L. Karakhanyan. Lipschitz continuity of free boundary in the continuous casting problem with divergence form elliptic equation. Discrete & Continuous Dynamical Systems - A, 2016, 36 (1) : 261-277. doi: 10.3934/dcds.2016.36.261

[15]

Ugo Bessi. The stochastic value function in metric measure spaces. Discrete & Continuous Dynamical Systems - A, 2017, 37 (4) : 1819-1839. doi: 10.3934/dcds.2017076

[16]

Saul Mendoza-Palacios, Onésimo Hernández-Lerma. Stability of the replicator dynamics for games in metric spaces. Journal of Dynamics & Games, 2017, 4 (4) : 319-333. doi: 10.3934/jdg.2017017

[17]

Shrikrishna G. Dani. Simultaneous diophantine approximation with quadratic and linear forms. Journal of Modern Dynamics, 2008, 2 (1) : 129-138. doi: 10.3934/jmd.2008.2.129

[18]

Beatris Adriana Escobedo-Trujillo, José Daniel López-Barrientos. Nonzero-sum stochastic differential games with additive structure and average payoffs. Journal of Dynamics & Games, 2014, 1 (4) : 555-578. doi: 10.3934/jdg.2014.1.555

[19]

Beatris Adriana Escobedo-Trujillo, Alejandro Alaffita-Hernández, Raquiel López-Martínez. Constrained stochastic differential games with additive structure: Average and discount payoffs. Journal of Dynamics & Games, 2018, 5 (2) : 109-141. doi: 10.3934/jdg.2018008

[20]

Yayun Zheng, Xu Sun. Governing equations for Probability densities of stochastic differential equations with discrete time delays. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3615-3628. doi: 10.3934/dcdsb.2017182

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]