×

A new convergent hybrid learning algorithm for two-stage stochastic programs. (English) Zbl 1431.90105

Summary: This study proposes a new hybrid learning algorithm to approximate the expected recourse function for two-stage stochastic programs. The proposed algorithm, which is called projected stochastic hybrid learning algorithm, is a hybrid of piecewise linear approximation and stochastic subgradient methods. Piecewise linear approximations are updated adaptively by using stochastic subgradient and sample information on the objective function itself. In order to achieve a global optimum, a projection step that implements the stochastic subgradient method is performed to jump out from a local optimum. For general two-stage stochastic programs, we prove the convergence of the algorithm. Furthermore, the algorithm can drop the projection steps for two-stage stochastic programs with network recourse. Therefore, the pure piecewise linear approximation method is convergent when the initial piecewise linear functions are properly constructed. Computational results indicate that the algorithm exhibits rapid convergence.

MSC:

90C15 Stochastic programming
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alem, D.; Clark, A.; Moreno, A., Stochastic network models for logistics planning in disaster relief, European Journal of Operational Research, 255, 1, 187-206 (2016) · Zbl 1346.90069
[2] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 1, 238-252 (1962) · Zbl 0109.38302
[3] Bouzaiene-Ayari, B.; Cheng, C.; Das, S.; Fiorillo, R.; Powell, W. B., From single commodity to multiattribute models for locomotive optimization: A comparison of optimal integer programming and approximate dynamic programming, Transportation Science, 50, 366-389 (2016)
[4] Cheung, R. K.; Chen, C. Y., A two-stage stochastic network model and solution methods for the dynamic empty container allocation problem, Transportation Science, 32, 2, 142-162 (1998) · Zbl 0987.90515
[5] Cheung, R. K.; Powell, W. B., An algorithm for multistage dynamic networks with random arc capacities, with an application to dynamic fleet management, Operations Research, 255, 1, 187-206 (1996)
[6] Cheung, R. K.; Powell, W. B., SHAPE-a stochastic hybrid approximation procedure for two-stage stochastic programs, Operations Research, 48, 1, 73-79 (2000) · Zbl 1106.90361
[7] Cordeau, J.-F.; Soumis, F.; Desrosiers, J., A benders decomposition approach for the locomotive and car assignment problem, Transportation Science, 34, 2, 133-149 (2000) · Zbl 1004.90045
[8] Ermoliev, Y., Stochastic quasigradient methods, Numerical techniques for stochastic optimization (1988), Springer-Verlag: Springer-Verlag New York · Zbl 0666.90072
[9] Girardeau, P.; Leclere, V.; Philpott, A. B., On the convergence of decomposition methods for multistage stochastic convex programs, Mathematics of Operations Research, 40, 1, 130-145 (2015) · Zbl 1308.90115
[10] Godfrey, G. A.; Powell, W. B., An adaptive dynamic programming algorithm for dynamic fleet management i: single period travel times, Transportation Science, 36, 1, 21-39 (2002) · Zbl 1065.90518
[11] Guigues, V., SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning, Computational Optimization and Applications, 57, 167-203 (2014) · Zbl 1312.90047
[12] Guigues, V., Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs, SIAM Journal on Optimization, 26, 2468-2494 (2016) · Zbl 1356.90095
[13] Guigues, V. (2017a). Inexact cuts for deterministic and stochastic dual dynamic programming applied to convex nonlinear optimization problems. arXiv preprint:1707.00812, 2017. (assessed by https://arxiv.org/abs/1707.00812 on 15 Nov, 2019).
[14] Guigues, V., Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures, Mathematical Programming, 163, 169-212 (2017) · Zbl 1380.90200
[15] Guigues, V. (2018). Inexact cuts in deterministic and stochastic dual dynamic programming applied to linear optimization problems. arx preprint: 1801.04243, 2018. (accessed by https://arxiv.org/abs/1801.04243 or http://www.optimization-online.org/DB_FILE/2018/01/6426.pdf on 15 Nov, 2019.).
[16] Guigues, V.; Römisch, W., Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measure, SIAM Journal on Optimization, 22, 286-312 (2012) · Zbl 1259.90082
[17] Higle, J. L.; Sen, S., Stochastic decomposition: an algorithm for two-stage linear programs with recourse, European Journal of Operational Research, 16, 3, 650-669 (1991) · Zbl 0746.90045
[18] Infanger, G.; Morton, D., Cut sharing for multistage stochastic linear programs with interstage dependency, Mathematical Programming, 75, 241-256 (1996) · Zbl 0874.90147
[19] Kim, K.; Mehrotra, S., A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management, Operations Research, 63, 1431-1451 (2015) · Zbl 1334.90092
[20] Kleywegt, A. J.; Shapiro, A.; Homem de Mello, T., The sample average approximation method for stochastic discrete optimization, SIAM Journal on Optimization, 12, 2, 479-502 (2001) · Zbl 0991.90090
[21] Lohmann, T.; Hering, A. S.; Rebennack, S., Spatio-temporal hydro-inflow forecasting of multireservoir inflows for hydro-thermal scheduling, European Journal of Operational Research, 255, 1, 243-258 (2016) · Zbl 1346.90547
[22] Löhndorf, N.; Wozabal, D.; Minner, S., Optimizing trading decisions for hydro storage systems using approximate dual dynamic programming, Operations Research, 61, 4, 1182-1213 (2013) · Zbl 1291.90125
[23] Long, Y.; Lee, L. H.; Chew, E. P., The sample average approximation method for empty container repositioning with uncertainties, European Journal of Operational Research, 222, 1, 65-75 (2012) · Zbl 1253.90051
[24] Moreno, A.; Alem, D.; Ferreira, D.; Clark, A., An effective two-stage stochastic multi-trip location-transportation model with social concerns in relief supply chains, European Journal of Operational Research, 269, 3, 1050-1071 (2018) · Zbl 1388.90022
[25] Nascimento, J.; Powell, W. B., An optimal approximate dynamic programming algorithm for concave, scalar storage problems with vector-valued controls, IEEE Transactions on Automatic Control, 58, 12, 2995-3010 (2013) · Zbl 1369.49035
[26] Nemirovski, A.; Juditsky, A.; Lan, G.; Shapiro, A., Robust stochastic approximation approach to stochastic programming, SIAM Journal on Optimization, 19, 4, 1574-1609 (2009) · Zbl 1189.90109
[27] Neveu, J. (1975). Discrete parameter martingales. North Holland, Amsterdam. · Zbl 0345.60026
[28] Pereira, M. V.F.; Pinto, L. M.V. G., Multi-stage stochastic optimization applied to energy planning, Mathematical Programming, 52, 359-375 (1991) · Zbl 0749.90057
[29] Philpott, A. B.; Guan, Z., On the convergence of stochastic dual dynamic programming and related methods, Operations Research Letters, 36, 450-455 (2008) · Zbl 1155.90437
[30] Philpott, A. B.; de Matos, V. L., Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion, European Journal of Operational Research, 218, 2, 470-483 (2012) · Zbl 1244.90175
[31] Polyak, B. T.; Juditsky, A. B., Acceleration of stochastic approximation by averaging, SIAM Journal on Control and Optimization, 30, 4, 838-855 (1992) · Zbl 0762.62022
[32] Powell, W. B.; Ruszczyński, A.; Togaloglu, H., Learning algorithms for separable approximation of discrete stochastic optimization problems, Mathematics of Operations Research, 29, 4, 814-836 (2004) · Zbl 1082.90079
[33] Rebennack, S., Combining sampling-based and scenario-based nested benders decomposition methods: application to stochastic dual dynamic programming, Mathematical Programming, 156, 1, 343-389 (2016) · Zbl 1342.90116
[34] Restrepo, M. I.; Gendron, B.; Rousseau, L. M., A two-stage stochastic programming approach for multi-activity tour scheduling, European Journal of Operational Research, 262, 2, 620-635 (2017) · Zbl 1375.90142
[35] Robbins, H.; Monro, S., A stochastic approximation method, The Annals of Mathematical Statistics, 22, 3, 400-407 (1951) · Zbl 0054.05901
[36] Rockafellar, R. T.; Wets, J. B., A note about projections in the implementation of stochastic quasigradient methods, Numerical techniques for stochastic optimization. Numerical techniques for stochastic optimization, springer series computational mathematics, vol. 10, 385-392 (1988), Springer: Springer Berlin · Zbl 0664.90067
[37] Ruszczyński, A., A linearization method for nonsmooth stochastic optimization problems, Mathematics of Operations Research, 12, 32-49 (1987) · Zbl 0624.90078
[38] Shapiro, A., Analysis of stochastic dual dynamic programming method, European Journal of Operational Research, 209, 1, 63-72 (2011) · Zbl 1208.90126
[39] Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on stochastic programming: modeling and theory (2014), Society for industrial and applied mathematics · Zbl 1302.90003
[40] Shapiro, A.; Tekaya, W.; da Costa, J.; Soares, M., Risk neutral and risk averse stochastic dual dynamic programming method, European Journal of Operational Research, 224, 1, 375-391 (2013) · Zbl 1292.90219
[41] Song, D. P.; Dong, J. X., Empty container management in cyclic shipping routes, Maritime Economics & Logistics, 10, 4, 335-361 (2008)
[42] Steeger, G.; Lonhmann, T.; Rebennack, S., Strategic bidding for a price-maker hydroelectric producer: stochastic dual dynamic programming and lagrangian relaxation, IISE Transactions, 50, 11, 929-942 (2018)
[43] Taylor, H. M., Martingales and random walks, Volume 2 (1990), Elsevier Science Publishers B.V · Zbl 0708.60038
[44] Van Slyke, R. M.; Wets, R. J.-B., L-shaped linear programs with applications to optimal control and stochastic programming, SIAM Journal on Applied Mathematics, 17, 4, 638-663 (1969) · Zbl 0197.45602
[45] Wallace, S. W.; Ziemba, W. T., Applications of stochastic programming, MPS/SIAM Series on Optimization, vol .5 (2005), Society for Industrial and Applied Mathematics (SIAM); Mathematical Programming Society (MPS): Society for Industrial and Applied Mathematics (SIAM); Mathematical Programming Society (MPS) Philadelphia, PA, ISBN: 0-89871-555-5
[46] Zakeri, G.; Philpott, A. B.; Ryan, D. M., Inexact cuts in benders decomposition, SIAM Journal on Optimization, 10, 4, 643-657 (2000) · Zbl 0955.90088
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.