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

Previous Article
Primal-dual interior-point algorithms for convex quadratic circular cone optimization
NACO Home
This Issue
Next Article
A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions

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

Abstract
Related Papers

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 and 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, Berlin, 1982.
[2]	J. R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer, New York, 1997.
[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-46. doi: 10.1016/0377-0427(94)00082-C.
[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-306. doi: 10.1080/10556780008805789.
[5]	G. M. Cho, Log-barrier method for two-stage quadratic stochastic programming, Appl. Math. Comput., 164 (2005), 45-69. doi: 10.1016/j.amc.2004.04.095.
[6]	A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Springer-Verlag, New York, 1998. doi: 10.1007/978-1-4612-5320-4.
[7]	M. A. Goberna, M. A. López, Linear Semi-Infinite Optimization, John Wiley and sons, Chichester, 1998.
[8]	Y. Han and Z. Chen, Quantitative stability of full random two-stage stochastic programs with recourse,, Optim. Lett., ().
[9]	P. Kall and S. W. Wallace, Stochastic Programming, John Wiley and Sons, Chichester, 1994.
[10]	W. K. Klein Haneveld and M. H. Van der Vlerk, Stochastic integer programming: general models and algorithms, Ann. Oper. Res., 85 (1999), 39-57. doi: 10.1023/A:1018930113099.
[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-595. doi: 10.1137/0325033.
[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-974. doi: 10.1287/opre.1080.0659.
[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-176. doi: 10.1016/S0025-5610(96)00010-X.
[14]	A. Prekopa, Stochastic Programming, Kluwer Academic Publishers, Dordrecht, Boston. 1995. doi: 10.1007/978-94-017-3087-7.
[15]	L. Qi and R. S. Womersley, An SQP algorithm for extended linear-quadratic problems in stochastic programming, Ann. Oper. Res., 56 (1995), 251-285. doi: 10.1007/BF02031711.
[16]	S. T. Rachev, W. Römisch, Quantitative stability in stochastic programming: the methods of probability metrics, Math. Oper. Res., 27 (2002), 792-818. doi: 10.1287/moor.27.4.792.304.
[17]	S. M. Robinson, Analysis of sample-path optimization, Math. Oper. Res., 21 (1996), 513-528. doi: 10.1287/moor.21.3.513.
[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-93.
[19]	R. T. Rockafeller and R. J-B. Wets, Variational Analysis, Springer, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.
[20]	W. Römisch, Stability of stochastic programming, in Stochastic Programming: Handbooks in Operations Research and Management Science Vol.10 (eds. A. Rusczyński, A. Shapiro), North-Holland Publishing Company, Amsterdam, (2003), 483-554. doi: 10.1016/S0927-0507(03)10008-4.
[21]	W. Römisch and R. Schultz, Distribution sensitivity in stochastic programming, Math. Program., 50 (1991), 197-226. doi: 10.1007/BF01594935.
[22]	W. Römisch and R. Schultz, Lipschitz stability for stochastic programs with complete recourse, SIAM J. Optim., 6 (1996), 531-547. doi: 10.1137/0806028.
[23]	W. Römisch and R. J.-B. Wets, Stability of ε-approximate solutions to convex stochastic programs, SIAM J. Optim., 18 (2007), 961-979. doi: 10.1137/060657716.
[24]	A. Shapiro, Monte Carlo sampling methods, in Stochastic Programming: Handbooks in Operations Research and Management Science Vol.10 (eds. A. Rusczyński, A. Shapiro), North-Holland Publishing Company, Amsterdam, (2003), 353-425. doi: 10.1016/S0927-0507(03)10006-0.
[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-547.
[26]	A. Shapiro, Complexity of two and multi-stage stochastic programming problems,, 2005. Available from: , ().

show all references

References:

[1]	B. Bank, J. Guddat, D. Klatte, B. Kummer and K. Tammer, Non-Linear Parametric Optimization, Akademie Verlag, Berlin, 1982.
[2]	J. R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer, New York, 1997.
[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-46. doi: 10.1016/0377-0427(94)00082-C.
[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-306. doi: 10.1080/10556780008805789.
[5]	G. M. Cho, Log-barrier method for two-stage quadratic stochastic programming, Appl. Math. Comput., 164 (2005), 45-69. doi: 10.1016/j.amc.2004.04.095.
[6]	A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Springer-Verlag, New York, 1998. doi: 10.1007/978-1-4612-5320-4.
[7]	M. A. Goberna, M. A. López, Linear Semi-Infinite Optimization, John Wiley and sons, Chichester, 1998.
[8]	Y. Han and Z. Chen, Quantitative stability of full random two-stage stochastic programs with recourse,, Optim. Lett., ().
[9]	P. Kall and S. W. Wallace, Stochastic Programming, John Wiley and Sons, Chichester, 1994.
[10]	W. K. Klein Haneveld and M. H. Van der Vlerk, Stochastic integer programming: general models and algorithms, Ann. Oper. Res., 85 (1999), 39-57. doi: 10.1023/A:1018930113099.
[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-595. doi: 10.1137/0325033.
[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-974. doi: 10.1287/opre.1080.0659.
[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-176. doi: 10.1016/S0025-5610(96)00010-X.
[14]	A. Prekopa, Stochastic Programming, Kluwer Academic Publishers, Dordrecht, Boston. 1995. doi: 10.1007/978-94-017-3087-7.
[15]	L. Qi and R. S. Womersley, An SQP algorithm for extended linear-quadratic problems in stochastic programming, Ann. Oper. Res., 56 (1995), 251-285. doi: 10.1007/BF02031711.
[16]	S. T. Rachev, W. Römisch, Quantitative stability in stochastic programming: the methods of probability metrics, Math. Oper. Res., 27 (2002), 792-818. doi: 10.1287/moor.27.4.792.304.
[17]	S. M. Robinson, Analysis of sample-path optimization, Math. Oper. Res., 21 (1996), 513-528. doi: 10.1287/moor.21.3.513.
[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-93.
[19]	R. T. Rockafeller and R. J-B. Wets, Variational Analysis, Springer, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.
[20]	W. Römisch, Stability of stochastic programming, in Stochastic Programming: Handbooks in Operations Research and Management Science Vol.10 (eds. A. Rusczyński, A. Shapiro), North-Holland Publishing Company, Amsterdam, (2003), 483-554. doi: 10.1016/S0927-0507(03)10008-4.
[21]	W. Römisch and R. Schultz, Distribution sensitivity in stochastic programming, Math. Program., 50 (1991), 197-226. doi: 10.1007/BF01594935.
[22]	W. Römisch and R. Schultz, Lipschitz stability for stochastic programs with complete recourse, SIAM J. Optim., 6 (1996), 531-547. doi: 10.1137/0806028.
[23]	W. Römisch and R. J.-B. Wets, Stability of ε-approximate solutions to convex stochastic programs, SIAM J. Optim., 18 (2007), 961-979. doi: 10.1137/060657716.
[24]	A. Shapiro, Monte Carlo sampling methods, in Stochastic Programming: Handbooks in Operations Research and Management Science Vol.10 (eds. A. Rusczyński, A. Shapiro), North-Holland Publishing Company, Amsterdam, (2003), 353-425. doi: 10.1016/S0927-0507(03)10006-0.
[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-547.
[26]	A. Shapiro, Complexity of two and multi-stage stochastic programming problems,, 2005. Available from: , ().

[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 and 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 and 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 and Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317
[4]	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
[5]	Shulin Wang, Yangrong Li. Probabilistic continuity of a pullback random attractor in time-sample. Discrete and Continuous Dynamical Systems - B, 2020, 25 (7) : 2699-2722. doi: 10.3934/dcdsb.2020028
[6]	Katrin Grunert, Helge Holden, Xavier Raynaud. Lipschitz metric for the Camassa--Holm equation on the line. Discrete and Continuous Dynamical Systems, 2013, 33 (7) : 2809-2827. doi: 10.3934/dcds.2013.33.2809
[7]	Ling Zhang, Xiaoqi Sun. Stability analysis of time-varying delay neural network for convex quadratic programming with equality constraints and inequality constraints. Discrete and Continuous Dynamical Systems - B, 2022 doi: 10.3934/dcdsb.2022035
[8]	Arnulf Jentzen, Benno Kuckuck, Thomas Müller-Gronbach, Larisa Yaroslavtseva. Counterexamples to local Lipschitz and local Hölder continuity with respect to the initial values for additive noise driven stochastic differential equations with smooth drift coefficient functions with at most polynomially growing derivatives. Discrete and Continuous Dynamical Systems - B, 2022, 27 (7) : 3707-3724. doi: 10.3934/dcdsb.2021203
[9]	Anne-Sophie de Suzzoni. Continuity of the flow of the Benjamin-Bona-Mahony equation on probability measures. Discrete and Continuous Dynamical Systems, 2015, 35 (7) : 2905-2920. doi: 10.3934/dcds.2015.35.2905
[10]	Michela Eleuteri, Paolo Marcellini, Elvira Mascolo. Local Lipschitz continuity of minimizers with mild assumptions on the $x$-dependence. Discrete and Continuous Dynamical Systems - S, 2019, 12 (2) : 251-265. doi: 10.3934/dcdss.2019018
[11]	Hsin-Min Sun, Yu-Juan Sun. Variable fixing method by weighted average for the continuous quadratic knapsack problem. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 15-29. doi: 10.3934/naco.2021048
[12]	Xiangxiang Huang, Xianping Guo, Jianping Peng. A probability criterion for zero-sum stochastic games. Journal of Dynamics and Games, 2017, 4 (4) : 369-383. doi: 10.3934/jdg.2017020
[13]	Andrea Tosin, Paolo Frasca. Existence and approximation of probability measure solutions to models of collective behaviors. Networks and Heterogeneous Media, 2011, 6 (3) : 561-596. doi: 10.3934/nhm.2011.6.561
[14]	Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[15]	Luis D'Alto, Martin Corless. Incremental quadratic stability. Numerical Algebra, Control and Optimization, 2013, 3 (1) : 175-201. doi: 10.3934/naco.2013.3.175
[16]	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 and Continuous Dynamical Systems - B, 2019, 24 (2) : 587-613. doi: 10.3934/dcdsb.2018198
[17]	Davor Dragičević. Admissibility, a general type of Lipschitz shadowing and structural stability. Communications on Pure and Applied Analysis, 2015, 14 (3) : 861-880. doi: 10.3934/cpaa.2015.14.861
[18]	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 and Continuous Dynamical Systems, 2011, 29 (2) : 505-522. doi: 10.3934/dcds.2011.29.505
[19]	Aram L. Karakhanyan. Lipschitz continuity of free boundary in the continuous casting problem with divergence form elliptic equation. Discrete and Continuous Dynamical Systems, 2016, 36 (1) : 261-277. doi: 10.3934/dcds.2016.36.261
[20]	Ugo Bessi. The stochastic value function in metric measure spaces. Discrete and Continuous Dynamical Systems, 2017, 37 (4) : 1819-1839. doi: 10.3934/dcds.2017076

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Zhiping Chen Youpan Han
on Google Scholar
Zhiping Chen Youpan Han

[Back to Top]