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

Zhiping  Chen; Youpan  Han

doi:10.3934/naco.2015.5.197

Article Contents

2015, Volume 5, Issue 2: 197-209. Doi: 10.3934/naco.2015.5.197

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

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
2.
School of Science, Xi'an Polytechnic University,710048 Xi'an, Shanxi

Received: August 31, 2014

Revised: April 30, 2015

Published: May 2015

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C15, 90C20,90C31.

Citation:

Related Papers

Cited by

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., to appear.
[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: //www2.isye.gatech.edu/~ashapiro/publications.html.