Discrete Approximation and Convergence Analysis for a Class of Decision-Dependent Two-Stage Stochastic Linear Programs

doi:10.1007/s40305-022-00441-5

Abstract

Abstract: Customary stochastic programming with recourse assumes that the probability distribution of random parameters is independent of decision variables. Recent studies demonstrated that stochastic programming models with endogenous uncertainty can better reflect many real-world activities and applications accompanying with decisiondependent uncertainty. In this paper, we concentrate on a class of decision-dependent two-stage stochastic programs (DTSPs) and investigate their discrete approximation. To develop the discrete approximation methods for DTSPs, we first derive the quantitative stability results for DTSPs. Based on the stability conclusion, we examine two discretization schemes when the support set of random variables is bounded, and give the rates of convergence for the optimal value and optimal solution set of the discrete approximation problem to those of the original problem. Then we extend the proposed approaches to the general situation with an unbounded support set by using the truncating technique. As an illustration of our discretization schemes, we reformulate the discretization problems under specific structures of the decision-dependent distribution. Finally, an application and numerical results are presented to demonstrate our theoretical results.

Key words: Stochastic programming, Decision-dependence, Discrete approximation, Stability, Convergence rate

CLC Number:

90C15
90C31

Jie Jiang, Zhi-Ping Chen. Discrete Approximation and Convergence Analysis for a Class of Decision-Dependent Two-Stage Stochastic Linear Programs[J]. Journal of the Operations Research Society of China, 2024, 12(3): 649-679.

TrendMD

References

[1] Ruszczyński, A., Shapiro, A.: Stochastic programming models. Handbooks Oper. Res. Management Sci. 10, 1-64(2003)
[2] Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming: Modeling and Theory, 2nd ed. SIAM, Philadelphia (2014)
[3] Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (2011)
[4] Kall, P., Wallace, S.W., Kall, P.: Stochastic Programming. John Wiley & Sons, Chichester (1994)
[5] Jonsbråten, T.W., Wets, R.J., Woodruff, D.L.: A class of stochastic programs with decision dependent random elements. Ann. Oper. Res. 82, 83-106(1998)
[6] Mirrlees, J.A.: The theory of moral hazard and unobservable behaviour: Part I. Rev. Econ. Stud. 66(1), 3-21(1999)
[7] Zhan, Y., Zheng, Q.P., Wang, J., Pinson, P.: Generation expansion planning with large amounts of wind power via decision-dependent stochastic programming. IEEE Trans. Power Syst. 32(4), 3015-3026(2016)
[8] Goel, V., Grossmann, I.E.: A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Comput. & Chem. Eng. 28(8), 1409-1429(2004)
[9] Jonsbråten, T.W.: Optimization models for petroleum field exploitation. PhD thesis, Norges Handelshøyskole (1998)
[10] Solak, S., Clarke, J.-P.B., Johnson, E.L., Barnes, E.R.: Optimization of R&D project portfolios under endogenous uncertainty. Eur. J. Oper. Res. 207(1), 420-433(2010)
[11] Jiang, J., Shi, Y., Wang, X., Chen, X.: Regularized two-stage stochastic variational inequalities for Cournot-Nash equilibrium under uncertainty. J. Comput. Math. 37(6), 813-842(2019)
[12] Bertsekas, D.P.: Reinforcement Learning And Optimal Control. Athena Scientific, Nashua (2019)
[13] Hellemo, L., Barton, P.I., Tomasgard, A.: Decision-dependent probabilities in stochastic programs with recourse. CMS 15(3-4), 369-395(2018)
[14] Pflug, G.C.: On-line optimization of simulated markovian processes. Math. Oper. Res. 15(3), 381-395(1990)
[15] Dyer, M., Stougie, L.: Computational complexity of stochastic programming problems. Math. Program. 106(3), 423-432(2006)
[16] Hanasusanto, G.A., Kuhn, D., Wiesemann, W.: A comment on “computational complexity of stochastic programming problems". Math. Program. 159(1-2), 557-569(2016)
[17] Goel, V., Grossmann, I.E.: A class of stochastic programs with decision dependent uncertainty. Math. Program. 108(2-3), 355-394(2006)
[18] Shapiro, A.: Monte carlo sampling methods. Handbooks Oper. Res. Management Sci. 10, 353-425(2003)
[19] Xu, H.: Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming. J. Math. Anal. Appl. 368(2), 692-710(2010)
[20] Shapiro, A., Xu, H.: Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation. Optimization 57(3), 395-418(2008)
[21] Kleywegt, A.J., Shapiro, A., Homem-de-Mello, T.: The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2), 479-502(2002)
[22] Rachev, S.T., Römisch,W.: Quantitative stability in stochastic programming: themethod of probability metrics. Math. Oper. Res. 27(4), 792-818(2002)
[23] Rachev, S.T., Klebanov, L., Stoyanov, S.V., Fabozzi, F.: The Methods of Distances in the Theory of Probability and Statistics. Springer, New York (2013)
[24] Römisch, W.: Stability of stochastic programming problems. Handbooks Oper. Res. Management Sci. 10, 483-554(2003)
[25] Pflug, G.C., Pichler, A.: Multistage Stochastic Optimization. Springer, Cham (2014)
[26] Graf, S., Luschgy, H.: Foundations of Quantization for Probability Distributions, 1st ed. Springer, Berlin/Heideberg (2000)
[27] Liu, Y., Pichler, A., Xu, H.: Discrete approximation and quantification in distributionally robust optimization. Math. Oper. Res. 44(1), 19-37(2018)
[28] Facchinei, F., Pang, J.-S.: Finite-dimensional variational inequalities and complementarity problems. Springer, New York (2007)
[29] Xu, H., Liu, Y., Sun, H.: Distributionally robust optimization with matrix moment constraints: Lagrange duality and cutting plane methods. Math. Program. 169(2), 489-529(2018)
[30] Sun, H., Xu, H.: Convergence analysis for distributionally robust optimization and equilibrium problems. Math. Oper. Res. 41(2), 377-401(2015)
[31] McLachlan, G., Peel, D.: Finite Mixture Models. John Wiley & Sons, USA (2004)
[32] Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (2006)
[33] Chen, X., Sun, H., Xu, H.: Discrete approximation of two-stage stochastic and distributionally robust linear complementarity problems. Math. Program. 177(1-2), 255-289(2019)