[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

On level regularization with normal solutions in decomposition methods for multistage stochastic programming problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

We consider well-known decomposition techniques for multistage stochastic programming and a new scheme based on normal solutions for stabilizing iterates during the solution process. The given algorithms combine ideas from finite perturbation of convex programs and level bundle methods to regularize the so-called forward step of these decomposition methods. Numerical experiments on a hydrothermal scheduling problem indicate that our algorithms are competitive with the state-of-the-art approaches such as multistage regularized decomposition, nested decomposition and stochastic dual dynamic programming.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. Note that \({{\bar{x}}}_3(\xi ^a_{[3]})={{\bar{x}}}_3(\xi ^b_{[3]})=\bar{x}_3(\xi ^c_{[3]})\) and \({{\bar{x}}}_3(\xi ^d_{[3]})=\bar{x}_3(\xi ^e_{[3]})\).

  2. Although the regularization effect still presents if (8) has multiple solutions.

References

  1. Asamov, T., Powell, W.B.: Regularized decomposition of high-dimensional multistage stochastic programs with markov uncertainty. SIAM J. Optim. 28(1), 575–595 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bank, B., Guddat, J., Klatte, D., Kummer, B., Tammer, K.: Non-linear Parametric Optimization. Birkhäuser, Basel (1982)

    Book  MATH  Google Scholar 

  3. Ben-Tal, A., Nemirovski, A.: Non-euclidean restricted memory level method for large-scale convex optimization. Math. Program. 102(3), 407–456 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  4. Birge, J.R.: Decomposition and partitioning methods for multistage stochastic linear programs. Oper. Res. 33(5), 989–1007 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chen, Z.L., Powell, W.B.: Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse. J. Optim. Theory Appl. 102(3), 497–524 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  6. Clark, D.I., Osborne, M.R.: A descent algorithm for minimizing polyhedral convex functions. SIAM J. Sci. Stat. Comput. 4(4), 757–786 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  7. de Matos, V.L., Morton, D.P., Finardi, E.C.: Assessing policy quality in a multistage stochastic program for long-term hydrothermal scheduling. Ann. Oper. Res. 253, 713–731 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  8. de Oliveira, W.: Target radius methods for nonsmooth convex optimization. Oper. Res. Lett. 45(6), 659–664 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  9. de Oliveira, W., Sagastizábal, C.: Level bundle methods for oracles with on demand accuracy. Optim. Methods Softw. 29(6), 1180–1209 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  10. de Oliveira, W., Sagastizábal, C., Jardim Penna, D.D., Maceira, M.E.P., Damázio, J .M.: Optimal scenario tree reduction for stochastic streamflows in power generation planning problems. Optim. Methods Softw. 25(6), 917–936 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. de Oliveira, W., Sagastizábal, C.A., Scheimberg, S.: Inexact bundle methods for two-stage stochastic programming. SIAM J. Optim. 21(2), 517–544 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  12. de Oliveira, W., Solodov, M.: A doubly stabilized bundle method for nonsmooth convex optimization. Math. Program. 156(1), 125–159 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  13. de Oliveira, W., Sagastizábal, C., Lemaréchal, C.: Convex proximal bundle methods in depth: a unified analysis for inexact oracles. Math. Prog. Ser. B 148, 241–277 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  14. de Queiroz, Anderson Rodrigo, Morton, David P: Sharing cuts under aggregated forecasts when decomposing multi-stage stochastic programs. Oper. Res. Lett. 41(3), 311–316 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Donohue, C., Birge, J.R.: The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse. Algorithmic Oper. Res. 1(1), 20–30 (2006)

    MathSciNet  MATH  Google Scholar 

  16. Dupačová, J., Polívka, J.: Asset-liability management for Czech pension funds using stochastic programming. Ann. Oper. Res. 165(1), 5–28 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  17. Dupačová, J.: Portfolio Optimization and Risk Management via Stochastic Programming. Osaka University Press, Osaka (2009)

    Google Scholar 

  18. Fábián, C.I.: Bundle-type methods for inexact data. In: Proceedings of the XXIV Hungarian Operations Researc Conference (Veszprém, 1999). Special issue, T. Csendes and T. Rapcsák (eds.), vol. 8, pp. 35–55, (2000)

  19. Ferris, M.C., Mangasarian, O.L.: Finite perturbation of convex programs. Appl. Math. Optim. 23(1), 263–273 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  20. Fhoula, B., Hajji, A., Rekik, M.: Stochastic dual dynamic programming for transportation planning under demand uncertainty. In: 2013 International Conference on Advanced Logistics and Transport, pp. 550–555, May (2013)

  21. Girardeau, P., Leclere, V., Philpott, A.B.: On the convergence of decomposition methods for multistage stochastic convex programs. Math. Oper. Res. 40(1), 130–145 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  22. 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)

    Article  Google Scholar 

  23. Herer, Y.T., Tzur, M., Yücesan, E.: The multilocation transshipment problem. IIE Trans. 38(3), 185–200 (2006)

    Article  Google Scholar 

  24. Higle, J.L., Sen, S.: Stochastic decomposition: an algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16(3), 650–669 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  25. Hindsberger, M., Philpott, A.B.: Resa: A method for solving multi-stage stochastic linear programs. In: SPIX Stochastic Programming Symposium, Berlin (2001)

  26. Holmes, D.: A (po)rtable (s)tochastic programming (t)est (s)et (posts). http://users.iems.northwestern.edu/~jrbirge/html/dholmes/post.html (1995)

  27. Homem de Mello, T., de Matos, V.L., Finardi, E.C.: Sampling strategies and stopping criteria for stochastic dual dynamic programming: a case study in long-term hydrothermal scheduling. Energy Syst. 2(1), 1–31 (2011)

    Article  Google Scholar 

  28. 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)

    Article  MathSciNet  MATH  Google Scholar 

  29. Kelley, J.E.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703–712 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  30. Kiwiel, K.C.: Finding normal solutions in piecewise linear programming. Appl. Math. Optim. 32(3), 235–254 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  31. Kiwiel, K.C.: Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. Math. Program. 69(1), 89–109 (1995)

    MathSciNet  MATH  Google Scholar 

  32. Lemaréchal, C.: An extension of davidon methods to nondifferentiable problems. Math. Program. Study 3, 95–109 (1975)

    Article  MATH  Google Scholar 

  33. Lemaréchal, C.: Constructing bundle methods for convex optimization. In: Hiriart-Urruty, J. B. (ed.) Fermat Days 85: Mathematics for Optimization. North-Holland Mathematics Studies, vol. 129, pp. 201–240. North-Holland (1986)

  34. Lemaréchal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Math. Program. 69(1), 111–147 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  35. Linowsky, K., Philpott, A.B.: On the convergence of sampling-based decomposition algorithms for multistage stochastic programs. J. Optim. Theory Appl. 125(2), 349–366 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  36. Maceira, M.E.P., Terry, L.A., Costa, F.S., Damázio, J.M., Melo, A.C.G.: Chain of optimization models for setting the energy dispatch and spot price in the Brazilian system. In: Proceedings of the 14th Power Systems Computation Conference—PSCC, pp. 1–7. Servilla, Spain (2002)

  37. Morton, D.P.: Stopping rules for a class of sampling-based stochastic programming algorithms. Oper. Res. 46(5), 710–718 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  38. Nesterov, Y.: Introductory Lectures on Convex Optimization. A Basic Course. Applied Optimization, vol. 87. Springer, Berlin (2004)

    Book  MATH  Google Scholar 

  39. Pereira, M.V., Granville, S., Fampa, M.H.C., Dix, R., Barroso, L.A.: Strategic bidding under uncertainty: a binary expansion approach. IEEE Trans. Power Syst. 11(1), 180–188 (2005)

    Article  Google Scholar 

  40. Pereira, M.V.F., Pinto, L.M.V.G.: Multi-stage stochastic optimization applied to energy planning. Math. Program. 52(2), 359–375 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  41. Ch Pflug, G., Römisch, W.: Modeling. Measuring and Managing Risk. World Scientific, Singapore (2007). https://www.worldscientific.com/worldscibooks/10.1142/6478

  42. Philpott, A.B., de Matos, V.L.: Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion. Eur. J. Oper. Res. 218(2), 470–483 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  43. Philpott, A.B., Guan, Z.: On the convergence of stochastic dual dynamic programming and related methods. Oper. Res. Lett. 36(4), 450–455 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  44. 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)

    Article  MathSciNet  MATH  Google Scholar 

  45. Ruszczyński, A.: On the regularized decomposition method for stochastic programming problems. In: Marti, K., Kall, P. (eds.) Stochastic Programming: Numerical Techniques and Engineering Applications, pp. 93–108. Springer, Berlin (1995)

    Chapter  MATH  Google Scholar 

  46. Sen, S., Zhou, Z.: Multistage stochastic decomposition: a bridge between stochastic programming and approximate dynamic programming. SIAM J. Optim. 24(1), 127–153 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  47. Shapiro, A.: Analysis of stochastic dual dynamic programming method. Eur. J. Oper. Res. 209, 63–72 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  48. Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on stochastic programming. Modeling and Theory. MPS-SIAM Series on Optimization. SIAM and MPS, vol. 9. Philadelphia, (2009)

  49. Shapiro, A., Tekaya, W., da Costa, J.P., Soares, M.P.: Risk neutral and risk averse stochastic dual dynamic programming method. Eur. J. Oper. Res. 224(2), 375–391 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  50. van Ackooij, W., de Oliveira, W., Song, Y.: An adaptive partition-based level decomposition for solving two-stage stochastic programs with fixed recourse. Inf. J. Comput. 30(1), 57–70 (2018)

    Article  MathSciNet  Google Scholar 

  51. van Ackooij, W., Frangioni, A., de Oliveira, W.: Inexact stabilized Benders’ decomposition approaches: with application to chance-constrained problems with finite support. Comput. Optim. Appl. 65(3), 637–669 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  52. van Ackooij, W., Lebbe, N., Malick, J.: Regularized decomposition of large-scale block-structured robust optimization problems. Comput. Manag. Sci. 14(3), 393–421 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  53. Wolf, C., Fábián, C .I., Koberstein, A., Stuhl, L.: Applying oracles of on-demand accuracy in two-stage stochastic programming. A computational study. J. Oper. Res. 239(2), 437–448 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  54. Wolf, C., Koberstein, A.: Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method. Eur. J. Oper. Res. 230(1), 143–156 (2013)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We would like to acknowledge the coordinating editor and two anonymous referees for their constructive suggestions that considerably improved the original version of this article. We also thank C. Wolf and A. Koberstein for providing us with some test problems and E. Finardi and F. Beltrán for the instances of the multistage hydro-thermal power generation planning problem. Finally, the first and the second authors would like to acknowledge the partial financial support of PGMO (Gaspard Monge Program for Optimization and operations research) of the Hadamard Mathematics Foundation, through the project “Models for planning energy investment under uncertainty”. The third author acknowledges partial support by the National Science Foundation (NSF) under grant CMMI 1854960. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF.

Author information

Authors and Affiliations

  1. EDF R&D. OSIRIS 7, Boulevard Gaspard Monge, F-91120, Palaiseau Cedex, France

    Wim van Ackooij

  2. MINES ParisTech, PSL - Research University, CMA - Centre de Mathématiques Appliquées, Sophia Antipolis, France

    Welington de Oliveira

  3. Clemson University, Clemson, SC, USA

    Yongjia Song

Authors
  1. Wim van Ackooij
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Welington de Oliveira
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yongjia Song
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Welington de Oliveira.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix A: Proof of Lemma 1

  1. Item (a)

    Let \({{\tilde{x}}}\) be a solution of (11), then \(f({{\tilde{x}}}) \le f(x(\tau ))\) (recall that both \({{\tilde{x}}}\) and \(x(\tau )\) belong to X). Moreover, \(f( x(\tau ))+ \frac{1}{\tau }\varphi (x(\tau )) \le f( {{\tilde{x}}})+ \frac{1}{\tau }\varphi ({{\tilde{x}}})\). These two inequalities show that \(\varphi (x(\tau )) \le \varphi (\tilde{x})=\varphi ^*<\infty \).

  2. Item (b)

    The previous item ensures that \(\varphi (x(\tau _k)) \le \varphi ({{\tilde{x}}})< \infty \) for all k. Since \(\varphi \) is a strong convex function, its level sets are compact. As a result, \(\{x(\tau _k)\}\) is a bounded sequence and, therefore, there exists a constant \(L<\infty \) bounding all subgradients of \(\varphi \) at \(x(\tau _k)\) for all k.

  3. Item (c)

    We first prove that

    $$\begin{aligned} \varphi (x(\tau '))< \varphi (x(\tau '')) \text{ and } f(x(\tau '))<f(x(\tau '')) \hbox { for all } 0<\tau '<\tau ''. \end{aligned}$$
    (29)

It follows from optimality of \(x(\tau ')\) and \(x(\tau '')\) and strongly convexity of \(\varphi \) that

$$\begin{aligned} f(x(\tau '))+ \varphi (x(\tau '))/\tau '< & {} f(x(\tau ''))+\varphi (x(\tau ''))/\tau ' \nonumber \\ f(x(\tau ''))+\varphi (x(\tau ''))/\tau ''< & {} f(x(\tau '))+\varphi (x(\tau '))/\tau '' \,. \end{aligned}$$
(30)

By summing these inequalities we obtain \(\varphi (x(\tau '))\left( \frac{1}{\tau '} - \frac{1}{\tau ''}\right) < \varphi (x(\tau ''))\left( \frac{1}{\tau '} - \frac{1}{\tau ''}\right) \), showing that \(\varphi (x(\tau ')) < \varphi (x(\tau ''))\). Inequality (30) implies \( f(x(\tau '')) - f(x(\tau '))< \frac{1}{\tau ''}[\varphi (x(\tau ')) - \varphi (x(\tau ''))] < 0\), yielding \(f(x(\tau '')) < f(x(\tau '))\).

Next we show that

$$\begin{aligned} x(\tau )= & {} \mathop {\mathrm{argmin}}\{ f(x)\; \text{ s.t. } x \in X,\; \varphi (x) \le \varphi (x(\tau ))\} \nonumber \\= & {} \mathop {\mathrm{argmin}}\{ \varphi (x)\; \text{ s.t. } x \in X,\; f(x) \le f(x(\tau ))\}, \quad \forall \; \tau >0. \end{aligned}$$
(31)

To this end, let \(x \in X\) such that \(x\ne x(\tau )\). Then \(\frac{1}{\tau }[\varphi (x(\tau )) - \varphi (x)] < f(x) -f(x(\tau ))\) from the definition of \(x(\tau )\). If \(\varphi (x) \le \varphi (x(\tau ))\) then \(f(x(\tau ))< f(x)\), showing that \(x(\tau )\) is the unique solution of \(\min \{ f(x)\; \text{ s.t. } x \in X,\; \varphi (x) \le \varphi (x(\tau ))\}\). Furthermore, if \(f(x)\le f(x(\tau ))\), then \(\varphi (x(\tau )) < \varphi (x)\), showing that \(x(\tau )\) is the unique solution of \(\min \{ \varphi (x)\; \text{ s.t. } x \in X,\; f(x) \le f(x(\tau ))\}\).

We are now in position to proof item (c). Recall that \(\varphi (x(\tau )) \le \varphi ({{\tilde{x}}})\) from item (a). The equivalences follow from (31) \( \varphi ({{\tilde{x}}})= \varphi (x(\tau )) \Leftrightarrow f({{\tilde{x}}})= f(x(\tau )) \Leftrightarrow x(\tau ) \in X^* \), and the identity \(x(\tau ')=\tilde{x}\) for all \(\tau ' \ge \tau \) follows from (29). \(\square \)

Appendix B: Detailed descriptions of the test instances

We describe the test instances used in our numerical experiments in more detail. The interconnected network structure of the hydrothermal power plants in Brazil is depicted in Fig. 6, and the detailed data on hydro and thermo plants are given in Table 4 and Table 5, respectively. In addition, we set the demand to be a constant 14,500 in each stage, and we set the unit penalty cost of not satisfying the demand to be 4500. The scenario data file is too big to be displayed here, but will be available upon request.

Table 4 Hydro plant data: the maximum allowed amount of turbined flow, the minimum/maximum level of water allowed, the initial water level, and the amount of power generated by releasing one unit of water flow in each hydro plant \(h = 1,2,\ldots , 30\)
Full size table
Fig. 6
figure 6

The interconnected network structure of the hydrothermal power plants in Brazil

Full size image
Table 5 Thermo plant data: maximum allowed amount of power generated and the unit cost of thermal power generated from each thermo plant f
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

van Ackooij, W., de Oliveira, W. & Song, Y. On level regularization with normal solutions in decomposition methods for multistage stochastic programming problems. Comput Optim Appl 74, 1–42 (2019). https://doi.org/10.1007/s10589-019-00104-x

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-019-00104-x

Keywords