×

On conditional cuts for stochastic dual dynamic programming. (English) Zbl 1441.90111

Summary: Multistage stochastic programs arise in many applications from engineering whenever a set of inventories or stocks has to be valued. Such is the case in seasonal storage valuation of a set of cascaded reservoir chains in hydro management. A popular method is stochastic dual dynamic programming (SDDP), especially when the dimensionality of the problem is large and dynamic programming is no longer an option. The usual assumption of SDDP is that uncertainty is stage-wise independent, which is highly restrictive from a practical viewpoint. When possible, the usual remedy is to increase the state-space to account for some degree of dependency. In applications, this may not be possible or it may increase the state-space by too much. In this paper, we present an alternative based on keeping a functional dependency in the SDDP – cuts related to the conditional expectations in the dynamic programming equations. Our method is based on popular methodology in mathematical finance, where it has progressively replaced scenario trees due to superior numerical performance. We demonstrate the interest of combining this way of handling dependency in uncertainty and SDDP on a set of numerical examples. Our method is readily available in the open-source software package StOpt.

MSC:

90C15 Stochastic programming
65C35 Stochastic particle methods

Software:

astsa; StOpt
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Barrera-Esteve, C.; Bergeret, F.; Dossal, C.; Gobet, E.; Meziou, A.; Munos, R.; Reboul-Salze, D., Numerical methods for the pricing of swing options: a stochastic control approach, Methodol Comput Appl Probab, 8, 4, 517-540 (2006) · Zbl 1142.91502
[2] Birge, JR, Decomposition and partitioning methods for multistage stochastic linear programs, Oper Res, 33, 5, 989-1007 (1985) · Zbl 0581.90065
[3] Bouchard, B.; Touzi, N., Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations, Stoch Process Appl, 111, 2, 175-206 (2004) · Zbl 1071.60059
[4] Bouchard, B.; Warin, X.; Carmona, RA; del Moral, P.; Hu, P.; Oudjane, N., Monte-Carlo valuation of American options: facts and new algorithms to improve existing methods, Numerical methods in finance, 215-255 (2012), Berlin: Springer, Berlin · Zbl 1247.91196
[5] Bruhns A, Deurveilher G, Roy JS (2005) A non-linear regression model for mid-term load forecasting and improvements in seasonality. In: PSCC 2005 Luik
[6] Carmona, R.; Ludkovski, M., Valuation of energy storage: an optimal switching approach, Quant Finance, 10, 4, 359-374 (2010) · Zbl 1203.91286
[7] Chen, ZL; Powell, WB, Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse, J Optim Theory Appl, 102, 3, 497-524 (1999) · Zbl 0955.90096
[8] de Matos, VL; Morton, DP; Finardi, EC, Assessing policy quality in a multistage stochastic program for long-term hydrothermal scheduling, Ann Oper Res, 253, 2, 713-731 (2017) · Zbl 1380.90209
[9] de Oliveira, W.; Sagastizábal, C.; Jardim Penna, DD; Maceira, MEP; Damázio, JM, Optimal scenario tree reduction for stochastic streamflows in power generation planning problems, Optim Methods Softw, 25, 6, 917-936 (2010) · Zbl 1200.78012
[10] de Queiroz, AR; Morton, DP, Sharing cuts under aggregated forecasts when decomposing multi-stage stochastic programs, Oper Res Lett, 41, 311-316 (2013) · Zbl 1286.90104
[11] Donohue, C.; Birge, JR, The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse, Algorithmic Oper Res, 1, 1, 20-30 (2006) · Zbl 1148.90336
[12] Dupačová, J., Portfolio optimization and risk management via stochastic programming (2009), Suita: Osaka University Press, Suita
[13] Dupačová, J.; Kozmík, V., Structure of risk-averse multistage stochastic programs, OR Spectr, 37, 3, 559-582 (2015) · Zbl 1317.90217
[14] Dupačová, J.; Polívka, J., Asset-liability management for Czech pension funds using stochastic programming, Ann Oper Res, 165, 1, 5-28 (2009) · Zbl 1163.90681
[15] Dupačová, J.; Gröwe-Kuska, N.; Römisch, W., Scenario reduction in stochastic programming: an approach using probability metrics, Math Program, 95, 3, 493-511 (2003) · Zbl 1023.90043
[16] Eichhorn, A.; Römisch, W., Polyhedral risk measures in stochastic programming, SIAM J Optim, 16, 1, 69-95 (2005) · Zbl 1114.90077
[17] Fahim, A.; Touzi, N.; Warin, X., A probabilistic numerical method for fully nonlinear parabolic pdes, Ann Appl Probab, 21, 4, 1322-1364 (2011) · Zbl 1230.65009
[18] Fhoula B, Hajji A, Rekik M (2013) Stochastic dual dynamic programming for transportation planning under demand uncertainty. In: 2013 international conference on advanced logistics and transport, May, pp 550-555
[19] Fournié, E.; Lasry, J-M; Lebuchoux, J.; Lions, P-L; Touzi, N., Applications of Malliavin calculus to Monte Carlo methods in finance, Finance Stoch, 3, 4, 391-412 (1999) · Zbl 0947.60066
[20] Fournié, E.; Lasry, J-M; Lebuchoux, J.; Lions, P-L, Applications of Malliavin calculus to Monte-Carlo methods in finance. II, Finance Stoch, 5, 2, 201-236 (2001) · Zbl 0973.60061
[21] Friedman, J.; Hastie, T.; Tibshirani, R., The elements of statistical learning (2001), New York: Springer, New York · Zbl 0973.62007
[22] Gevret H, Lelong J, Warin X (2016) Stochastic optimization library in C++
[23] Girardeau, P.; Leclere, V.; Philpott, AB, On the convergence of decomposition methods for multistage stochastic convex programs, Math Oper Res, 40, 1, 130-145 (2015) · Zbl 1308.90115
[24] Gobet, E.; Turkedjiev, P., Approximation of backward stochastic differential equations using Malliavin weights and least-squares regression, Bernoulli, 22, 1, 530-562 (2016) · Zbl 1339.60094
[25] Gobet, E.; Lemor, J-P; Warin, X., A regression-based Monte Carlo method to solve backward stochastic differential equations, Ann Appl Probab, 15, 3, 2172-2202 (2005) · Zbl 1083.60047
[26] Goel, V.; Grossmann, IE, A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves, Comput Chem Eng, 28, 8, 1409-1429 (2004)
[27] Guigues, V., SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning, Comput Optim Appl, 57, 1, 167-203 (2014) · Zbl 1312.90047
[28] Guigues, V., Convergence analysis of sampling-based decomposition for risk-averse multistage stochastic convex programs, SIAM J Optim, 26, 4, 2468-2494 (2016) · Zbl 1356.90095
[29] Guigues, V.; Römisch, W., Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures, SIAM J Optim, 22, 2, 286-312 (2012) · Zbl 1259.90082
[30] Guigues, V.; Sagastizábal, C., The value of rolling horizon policies for risk-averse hydro-thermal planning, Eur J Oper Res, 217, 219-240 (2012) · Zbl 1244.90264
[31] Heitsch, H.; Römisch, W.; Bertocchi, M.; Consigli, G.; Dempster, MAH, Scenario tree generation for multi-stage stochastic programs, Stochastic optimization methods in finance and energy: new financial products and energy market strategies, 313-341 (2011), Berlin: Springer, Berlin · Zbl 1405.90089
[32] Henaff P, Laachir I, Russo F (2013) Gas storage valuation and hedging. A quantification of the model risk. Arxiv
[33] Herer, YT; Tzur, M.; Yücesan, E., The multilocation transshipment problem, IIE Trans, 38, 3, 185-200 (2006)
[34] Hindsberger M, Philpott AB (2001) Resa: a method for solving multi-stage stochastic linear programs. In: SPIX stochastic programming symposium, Berlin
[35] Homem de Mello, T.; Pagnoncelli, B., Risk aversion in multistage stochastic programming: a modeling and algorithmic perspective, Eur J Oper Res, 249, 188-199 (2016) · Zbl 1346.90639
[36] Hull, J.; White, A., Pricing interest-rate-derivative securities, Rev Financ Stud, 3, 4, 573-592 (1990) · Zbl 1386.91152
[37] Infanger, G.; Morton, D., Cut sharing for multistage stochastic linear programs with interstage dependency, Math Program, 75, 1, 241-256 (1996) · Zbl 0874.90147
[38] Kelley, JE, The cutting-plane method for solving convex programs, J Soc Ind Appl Math, 8, 4, 703-712 (1960) · Zbl 0098.12104
[39] Kovacevic, RM; Pichler, A., Tree approximation for discrete time stochastic processes: a process distance approach, Ann Oper Res, 235, 1, 395-421 (2015) · Zbl 1332.90182
[40] Lemor, J-P; Gobet, E.; Warin, X., Rate of convergence of an empirical regression method for solving generalized backward stochastic differential equations, Bernoulli, 12, 5, 889-916 (2006) · Zbl 1136.60351
[41] Linowsky, K.; Philpott, AB, On the convergence of sampling-based decomposition algorithms for multistage stochastic programs, J Optim Theory Appl, 125, 2, 349-366 (2005) · Zbl 1071.90029
[42] Longstaff, FA; Schwartz, ES, Valuing American options by simulation: a simple least-squares approach, Rev Financ Stud, 14, 1, 113-147 (2001)
[43] Mo, B.; Gjelsvik, A.; Grundt, A., Integrated risk management of hydro power scheduling and contract management, IEEE Trans Power Syst, 16, 2, 216-221 (2001)
[44] Pagès, G.; Printems, J., Optimal quadratic quantization for numerics: the Gaussian case, Monte Carlo Methods Appl, 9, 2, 135-166 (2003) · Zbl 1029.65012
[45] Pagès, G.; Printems, J., Functional quantization for numerics with an application to option pricing, Monte Carlo Methods Appl, 11, 4, 407-446 (2005) · Zbl 1161.91402
[46] Pagès, G.; Printems, J.; Bensoussan, A.; Zhang, Q., Optimal quantization for finance: from random vectors to stochastic processes, Handbook of numerical analysis, 595-648 (2009), Amsterdam: North Holland, Amsterdam · Zbl 1180.91309
[47] Pagès, G.; Pham, H.; Printems, J.; Rachev, ST, Optimal quantization methods and applications to numerical problems in finance, Handbook of computational and numerical methods in finance, 253-297 (2004), Berlin: Springer, Berlin · Zbl 1138.91467
[48] Pereira, MVF; Pinto, LMVG, Multi-stage stochastic optimization applied to energy planning, Math Program, 52, 2, 359-375 (1991) · Zbl 0749.90057
[49] Pereira, MV; Granville, S.; Fampa, MHC; Dix, R.; Barroso, LA, Strategic bidding under uncertainty: a binary expansion approach, IEEE Trans Power Syst, 11, 1, 180-188 (2005)
[50] Pflug, GCh, Version-independence and nested distributions in multistage stochastic optimization, SIAM J Optim, 20, 3, 1406-1420 (2010) · Zbl 1198.90307
[51] Pflug, GCh; Pichler, A., A distance for multistage stochastic optimization models, SIAM J Optim, 22, 1, 1-23 (2012) · Zbl 1262.90118
[52] Pflug, G. Ch; Römisch, W., Modeling, measuring and managing risk (2007), Singapore: World Scientific Publishing Company, Singapore · Zbl 1153.91023
[53] Philpott, AB; Guan, Z., On the convergence of stochastic dual dynamic programming and related methods, Oper Res Lett, 36, 4, 450-455 (2008) · Zbl 1155.90437
[54] Philpott, AB; de Matos, VL, Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion, Eur J Oper Res, 218, 2, 470-483 (2012) · Zbl 1244.90175
[55] Rebennack, S., Combining sampling-based and scenario-based nested benders decomposition methods: application to stochastic dual dynamic programming, Math Program, 156, 1, 343-389 (2016) · Zbl 1342.90116
[56] Rodríguez FB, de Oliveria W, Finardi E (2017) Application of scenario tree reduction via quadratic process to medium-term hydrothermal scheduling problem. IEEE Trans Power Syst (to appear)
[57] Ruszczyński, A.; Shapiro, A., Conditional risk mappings, Math Oper Res, 31, 3, 544-561 (2006) · Zbl 1278.90284
[58] Ruszczyński, A.; Swietanowski, A., Accelerating the regularized decomposition method for two stage stochastic linear problems, Eur J Oper Res, 101, 2, 328-342 (1997) · Zbl 0929.90067
[59] Shapiro, A., Analysis of stochastic dual dynamic programming method, Eur J Oper Res, 209, 63-72 (2011) · Zbl 1208.90126
[60] Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on stochastic programming. Modeling and theory (2009), Philadelphia: SIAM, Philadelphia · Zbl 1183.90005
[61] Shapiro, A.; Tekaya, W.; da Costa, JP; Soares, MP, Risk neutral and risk averse stochastic dual dynamic programming method, Eur J Oper Res, 224, 2, 375-391 (2013) · Zbl 1292.90219
[62] Shumway, RH; Stoffer, DS, Time series analysis and its applications (2005), Berlin: Springer, Berlin
[63] Song, Y.; Luedtke, J., An adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse, SIAM J Optim, 25, 3, 1344-1367 (2015) · Zbl 1317.90222
[64] Tsilikis, J.; Van Roy, B., Optimal stopping of Markov processes: Hilbert space theory, approximation algorithms, and application to pricing high dimensional financial derivatives, IEEE Trans Autom Control, 44, 1840-1851 (1999) · Zbl 0958.60042
[65] Valladão, D.; Silva, T.; Poggi, M., Time-consistent risk-constrained dynamic portfolio optimization with transactional costs and time-dependent returns, Ann Oper Res, 282, 1-2, 379-405 (2019) · Zbl 1430.91092
[66] van Ackooij, W.; Malick, J., Decomposition algorithm for large-scale two-stage unit-commitment, Ann Oper Res, 238, 1, 587-613 (2016) · Zbl 1342.49046
[67] van Ackooij, W.; Henrion, R.; Möller, A.; Zorgati, R., Joint chance constrained programming for hydro reservoir management, Optim Eng, 15, 509-531 (2014) · Zbl 1364.90232
[68] van Ackooij, W.; de Oliveira, W.; Song, Y., An adaptive partition-based level decomposition for solving two-stage stochastic programs with fixed recourse, Informs J Comput, 30, 1, 57-70 (2018) · Zbl 1474.90307
[69] van Ackooij, W.; de Oliveira, W.; Song, Y., On regularization with normal solutions in decomposition methods for multistage stochastic programs, Comput Optim Appl, 74, 1, 1-42 (2019) · Zbl 1427.90207
[70] Warin, X.; Carmona, RA; del Moral, P.; Hu, P.; Oudjane, N., Gas storage hedging, Numerical methods in finance, 421-445 (2012), Berlin: Springer, Berlin · Zbl 1247.91203
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.