×

Regularized stochastic dual dynamic programming for convex nonlinear optimization problems. (English) Zbl 1452.90227

Summary: We define a regularized variant of the dual dynamic programming algorithm called DDP-REG to solve nonlinear dynamic programming equations. We extend the algorithm to solve nonlinear stochastic dynamic programming equations. The corresponding algorithm, called SDDP-REG, can be seen as an extension of a regularization of the stochastic dual dynamic programming (SDDP) algorithm recently introduced which was studied for linear problems only and with less general prox-centers. We show the convergence of DDP-REG and SDDP-REG. We assess the performance of DDP-REG and SDDP-REG on portfolio models with direct transaction and market impact costs. In particular, we propose a risk-neutral portfolio selection model which can be cast as a multistage stochastic second-order cone program. The formulation is motivated by the impact of market impact costs on large portfolio rebalancing operations. Numerical simulations show that DDP-REG is much quicker than DDP on all problem instances considered (up to 184 times quicker than DDP) and that SDDP-REG is quicker on the instances of portfolio selection problems with market impact costs tested and much faster on the instance of risk-neutral multistage stochastic linear program implemented (8.2 times faster).

MSC:

90C15 Stochastic programming
90C90 Applications of mathematical programming

Software:

Mosek
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Almgren, R., Optimal execution with nonlinear impact functions and trading-enhanced risk, Appl Math Finance, 10, 1-18 (2003) · Zbl 1064.91058 · doi:10.1080/135048602100056
[2] Almgren, R.; Thum, C.; Li, H., Equity market impact, Risk, 18, 57-62 (2005)
[3] Andersen ED, Dahl J, Friberg HA (2009) Markowitz portfolio optimization using MOSEK. MOSEK Technical report: TR-2009-2. Revised on March 4th, 2012. Avaialble at: https://docs.mosek.com/whitepapers/portfolio.pdf
[4] Asamov, T.; Powell, W., Regularized decomposition of high-dimensional multistage stochastic programs with Markov uncertainty, SIAM J Optim, 28, 575-595 (2015) · Zbl 1395.90190 · doi:10.1137/16M1072231
[5] Bandarra M, Guigues V (2019) Single cut and multicut SDDP with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments. arXiv:1902.06757
[6] Bouchaud, J.; Gefen, Y.; Potters, M.; Wyart, M., Fluctuations and response in financial markets: the subtle nature ofrandom price changes, Quant Finance, 4, 176-190 (2004) · Zbl 1405.91730 · doi:10.1080/14697680400000022
[7] Cadenillas, A., Consumption-investment problems with transaction costs: survey and open problems, Math Methods Oper Res, 51, 43-68 (2000) · Zbl 0947.91042 · doi:10.1007/s001860050002
[8] de Matos, V.; Philpott, A.; Finardi, E., Improving the performance of stochastic dual dynamic programming, J Comput Appl Math, 290, 196-208 (2015) · Zbl 1329.90098 · doi:10.1016/j.cam.2015.04.048
[9] Filomena, T.; Lejeune, M., Stochastic portfolio optimization with proportional transaction costs: convex reformulations and computational experiments, Oper Res Lett, 40, 212-217 (2012) · Zbl 1245.90074 · doi:10.1016/j.orl.2012.01.003
[10] Frino, A.; Bjursell, J.; Wang, G.; Lepone, A., Large trades and intraday futures price behavior, J Fut Mark, 28, 1117-1181 (2008) · doi:10.1002/fut.20380
[11] Gabaix, X.; Gopikrishnan, P.; Plerou, V.; Stanley, H., A theory of power-law distributions in financial market fluctuations, Nature, 423, 267-270 (2003) · doi:10.1038/nature01624
[12] Gatheral, J., No-dynamic-arbitrage and market impact, Quant Finance, 10, 749-759 (2010) · Zbl 1194.91208 · doi:10.1080/14697680903373692
[13] Girardeau, P.; Leclere, V.; Philpott, A., On the convergence of decomposition methods for multistage stochastic convex programs, Math Oper Res, 40, 130-145 (2015) · Zbl 1308.90115 · doi:10.1287/moor.2014.0664
[14] Grinold, R., A dynamic model of portfolio management, J Invest Manag, 4, 5-22 (2006)
[15] Grinold, R.; Kahn, R., Active Portfolio Management (2000), New York: McGraw-Hill, New York
[16] Guigues, V., SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning, Comput Optim Appl, 57, 167-203 (2014) · Zbl 1312.90047 · doi:10.1007/s10589-013-9584-1
[17] Guigues, V., Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs, SIAM J Optim, 26, 2468-2494 (2016) · Zbl 1356.90095 · doi:10.1137/140983136
[18] Guigues, V., Dual dynamic programing with cut selection: convergence proof and numerical experiments, Eur J Oper Res, 258, 47-57 (2017) · Zbl 1380.90277 · doi:10.1016/j.ejor.2016.10.047
[19] Guigues, V., Inexact cuts in stochastic dual dynamic programming, SIAM J Optim, 30, 407-438 (2020) · Zbl 1430.90444 · doi:10.1137/18M1211799
[20] Guigues, V.; Römisch, W., Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures, SIAM J Optim, 22, 286-312 (2012) · Zbl 1259.90082 · doi:10.1137/100811696
[21] Guigues, V.; Römisch, W., SDDP for multistage stochastic linear programs based on spectral risk measures, Oper Res Lett, 40, 313-318 (2012) · Zbl 1251.90296 · doi:10.1016/j.orl.2012.04.006
[22] Infanger, G.; Morton, D., Cut sharing for multistage stochastic linear programs with interstage dependency, Math Program, 75, 241-256 (1996) · Zbl 0874.90147
[23] Kozmik, V.; Morton, D., Evaluating policies in risk-averse multi-stage stochastic programming, Math Program, 152, 275-300 (2015) · Zbl 1327.90155 · doi:10.1007/s10107-014-0787-8
[24] Lemarechal C (1974) An algorithm for minimizing convex functions. In: Proceedings of the IFIP’74, Stockholm · Zbl 0297.65041
[25] Lillo, F.; Farmer, J.; Mantegna, R., Econophysics: master curve for price-impact function, Nature, 421, 129-130 (2003) · doi:10.1038/421129a
[26] Loeb, T., Trading costs: the critical link between investment information and results, Financ Anal J, 39, 39-44 (1983) · doi:10.2469/faj.v39.n3.39
[27] Mitchell, J.; Braun, S., Rebalancing an investment portfolio in the presence of convex transaction costs, including market impact costs, Optim Methods Softw, 28, 523-542 (2013) · Zbl 1266.91121 · doi:10.1080/10556788.2012.717940
[28] Mo, B.; Gjelsvik, A.; Grundt, A., Integrated risk management of hydro power scheduling and contract management, IEEE Trans Power Syst, 16, 216-221 (2001) · doi:10.1109/59.918289
[29] Moazeni, S.; Coleman, T.; Li, Y., Optimal portfolio execution strategies and sensitivity to price impact parameters, SIAM J Optim, 20, 1620-1654 (2010) · Zbl 1198.91193 · doi:10.1137/080715901
[30] Moro, E.; Vicente, J.; Moyano, L.; Gerig, A.; Farmer, J.; Vaglica, G.; Lillo, F.; Mantegna, R., Market impact and trading profile of hidden orders in stock markets, Phys Rev E, 80, 1-8 (2009) · doi:10.1103/PhysRevE.80.066102
[31] MOSEK (2017) MOSEK optimization suite. release 8.0.0.52
[32] Pereira, M.; Pinto, L., Multi-stage stochastic optimization applied to energy planning, Math Program, 52, 359-375 (1991) · Zbl 0749.90057 · doi:10.1007/BF01582895
[33] Pfeiffer L, Apparigliato R, Auchapt S (2012) Two methods of pruning benders’ cuts and their application to the management of a gas portfolio. Research report RR-8133, hal-00753578
[34] Philpott, AB; de Matos, V., Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion, Eur J Oper Res, 218, 470-483 (2012) · Zbl 1244.90175 · doi:10.1016/j.ejor.2011.10.056
[35] Philpott, AB; Guan, Z., On the convergence of stochastic dual dynamic programming and related methods, Oper Res Lett, 36, 450-455 (2008) · Zbl 1155.90437 · doi:10.1016/j.orl.2008.01.013
[36] Powell, W., Approximate Dynamic Programming (2011), London: Wiley, London · Zbl 1242.90002
[37] Rockafellar, R.; Uryasev, S., Conditional value-at-risk for general loss distributions, J Bank Finance, 26, 1443-1471 (2002) · doi:10.1016/S0378-4266(02)00271-6
[38] Sen, S.; Zhou, Z., Multistage stochastic decomposition: a bridge between stochastic programming and approximate dynamic programming, SIAM J Optim, 24, 127-153 (2014) · Zbl 1291.90153 · doi:10.1137/120864854
[39] Service WDR (2016) WRDS. http://wrds-web.wharton.upenn.edu
[40] Shapiro, A., Analysis of stochastic dual dynamic programming method, Eur J Oper Res, 209, 63-72 (2011) · Zbl 1208.90126 · doi:10.1016/j.ejor.2010.08.007
[41] Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on stochastic programming: modeling and theory (2009), Philadelphia: SIAM, Philadelphia · Zbl 1183.90005
[42] Shapiro, A.; Tekaya, W.; da Costa, J.; Soares, M., Risk neutral and risk averse stochastic dual dynamic programming method, Eur J Oper Res, 224, 375-391 (2013) · Zbl 1292.90219 · doi:10.1016/j.ejor.2012.08.022
[43] Tikhonov, A., On the stability of inverse problems, Dokl Akad Nauk SSSR, 39, 195-198 (1943)
[44] Torre, N., Market impact model handbook (1997), Berkeley: BARRA Inc., Berkeley
[45] Zagst, R.; Kalin, D., Portfolio optimization under liquidity costs, Int J Pure Appl Math, 39, 217-233 (2007) · Zbl 1221.91045
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.