Skip to main content
SpringerLink
Log in

Convergent Bounds for Stochastic Programs with Expected Value Constraints

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

This article describes a bounding approximation scheme for convex multistage stochastic programs (MSP) that constrain the conditional expectation of some decision-dependent random variables. Expected value constraints of this type are useful for modelling a decision maker’s risk preferences, but they may also arise as artifacts of stage-aggregation. We develop two finite-dimensional approximate problems that provide bounds on the (infinite-dimensional) original problem, and we show that the gap between the bounds can be made smaller than any prescribed tolerance. Moreover, the solutions of the approximate MSPs give rise to a feasible policy for the original MSP, and this policy’s optimality gap is shown to be smaller than the difference of the bounds. The considered problem class comprises models with integrated chance constraints and conditional value-at-risk constraints. No relatively complete recourse is assumed.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (1997)

    MATH  Google Scholar 

  2. Kall, P., Wallace, S.W.: Stochastic Programming. Wiley, Chichester (1994)

    MATH  Google Scholar 

  3. Prékopa, A.: Stochastic Programming. Kluwer Academic, Dordrecht (1995)

    Google Scholar 

  4. Wallace, S.W., Ziemba, W.T. (eds.): Applications of Stochastic Programming. MPS/SIAM Series on Optimization, vol. 5. SIAM, Philadelphia (2005)

    MATH  Google Scholar 

  5. Kaut, M., Wallace, S.W.: Evaluation of scenario-generation methods for stochastic programming. Pac. J. Optim. 3(2), 257–271 (2007)

    MATH  MathSciNet  Google Scholar 

  6. Høyland, K., Wallace, S.W.: Generating scenario trees for multistage decision problems. Manag. Sci. 47(2), 295–307 (2001)

    Article  Google Scholar 

  7. Shapiro, A.: On complexity of multistage stochastic programs. Oper. Res. Lett. 34, 1–8 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  8. Shapiro, A.: Inference of statistical bounds for multistage stochastic programming problems. Math. Methods Oper. Res. 58(1), 57–68 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  9. Koivu, M.: Variance reduction in sample approximations of stochastic programs. Math. Program. Ser. A 103, 463–485 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  10. Pennanen, T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Math. Program. Ser. B 116(1), 461–479 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  11. Pflug, G.Ch.: Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Program. Ser. B 89, 251–271 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  12. Hochreiter, R., Pflug, G.Ch.: Financial scenario generation for stochastic multi-stage decision processes as facility location problems. Ann. Oper. Res. 156(1), 257–272 (2007)

    Article  MathSciNet  Google Scholar 

  13. Dupačová, J., Gröwe-Kuska, N., Römisch, W.: Scenario reduction in stochastic programming: an approach using probability metrics. Math. Program. Ser. A 95, 493–511 (2003)

    Article  MATH  Google Scholar 

  14. Heitsch, H., Römisch, W.: Scenario reduction algorithms in stochastic programming. Comput. Optim. Appl. 24, 187–206 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  15. Rachev, S.T., Römisch, W.: Quantitative stability in stochastic programming: the method of probability metrics. Math. Oper. Res. 27, 792–818 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  16. Dantzig, G.B., Infanger, G.: Large-scale stochastic linear programs–importance sampling and Benders decomposition. Comput. Appl. Math. I, 111–120 (1992)

    MathSciNet  Google Scholar 

  17. Dempster, M.A.H., Thompson, R.T.: EVPI-based importance sampling solution procedures for multistage stochastic linear programmes on parallel MIMD architectures. Ann. Oper. Res. 90, 161–184 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  18. Ermoliev, Y.M., Gaivoronski, A.A.: Stochastic quasigradient methods for optimization of discrete event systems. Ann. Oper. Res. 39, 1–39 (1992)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  20. Infanger, G.: Planning under Uncertainty: Solving Large-Scale Stochastic Linear Programs. Boyd and Fraser, Danvers (1994)

    MATH  Google Scholar 

  21. Birge, J.R., Wets, R.J.-B.: Computing bounds for stochastic programming problems by means of a generalized moment problem. Math. Oper. Res. 12, 149–162 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  22. Dupačová, J.: On minimax solutions of stochastic linear programming problems. Časopis Pěstování Mat. 91, 423–429 (1966). (As Žáčková)

    Google Scholar 

  23. Frauendorfer, K.: Solving SLP recourse problems with arbitrary multivariate distributions—the dependent case. Math. Oper. Res. 13, 377–394 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  24. Gassmann, G., Ziemba, W.T.: A tight upper bound for the expectation of a convex function of a multivariate random variable. Math. Program. Study 27, 39–53 (1986)

    MATH  MathSciNet  Google Scholar 

  25. Kall, P.: An upper bound for SLP using first and total second moments. Ann. Oper. Res. 30, 267–276 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  26. Madansky, A.: Inequalities for stochastic linear programming problems. Manag. Sci. 6, 197–204 (1960)

    Article  MATH  MathSciNet  Google Scholar 

  27. Edirisinghe, N.C.P., Ziemba, W.T.: Bounding the expectation of a saddle function with application to stochastic programming. Math. Oper. Res. 19, 314–340 (1994)

    Article  MathSciNet  Google Scholar 

  28. Edirisinghe, N.C.P., Ziemba, W.T.: Bounds for two-stage stochastic programs with fixed recourse. Math. Oper. Res. 19, 292–313 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  29. Frauendorfer, K.: Stochastic Two-Stage Programming. Lecture Notes in Economics and Mathematical Systems, vol. 392. Springer, Berlin (1992)

    MATH  Google Scholar 

  30. Frauendorfer, K.: Multistage stochastic programming: error analysis for the convex case. Z. Oper. Res. 39(1), 93–122 (1994)

    MATH  MathSciNet  Google Scholar 

  31. Frauendorfer, K.: Barycentric scenario trees in convex multistage stochastic programming. Math. Program. 75(2), 277–294 (1996)

    Article  MathSciNet  Google Scholar 

  32. Kuhn, D.: Generalized Bounds for Convex Multistage Stochastic Programs. Lecture Notes in Economics and Mathematical Systems, vol. 548. Springer, Berlin (2004)

    Google Scholar 

  33. Wright, S.E.: Primal-dual aggregation and disaggregation for stochastic linear programs. Math. Oper. Res. 19(4), 893–908 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  34. Kuhn, D.: Aggregation and discretization in multistage stochastic programming. Math. Program. Ser. A 113(1), 61–94 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  35. Prékopa, A.: Contributions to the theory of stochastic programming. Math. Program. 4, 202–221 (1973)

    Article  MATH  Google Scholar 

  36. Charnes, A., Cooper, W.W.: Chance-constrained programming. Manag. Sci. 6, 73–79 (1959/1960)

    Article  MathSciNet  Google Scholar 

  37. Klein Haneveld, W.K.: Duality in Stochastic Linear and Dynamic Programming. Lecture Notes in Economics and Mathematical Systems, vol. 274. Springer, Berlin (1985)

    Google Scholar 

  38. Klein Haneveld, W.K., van der Vlerk, M.H.: Integrated chance constraints: reduced forms and an algorithm. Comput. Manag. Sci. 3(4), 245–269 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  39. Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-at-risk. J. Risk 2(3), 21–41 (2000)

    Google Scholar 

  40. Rockafellar, R.T., Uryasev, S.: Conditional value-at-risk for general loss distributions. J. Bank. Finance 26, 1443–1471 (2002)

    Article  Google Scholar 

  41. Rockafellar, R.T., Wets, R.J.-B.: The optimal recourse problem in discrete time: L 1-multipliers for inequality constraints. SIAM J. Control Optim. 16, 16–36 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  42. Rockafellar, R.T.: Conjugate Duality and Optimization. SIAM, Philadelphia (1974)

    MATH  Google Scholar 

  43. Rockafellar, R.T., Wets, R.J.-B.: Nonanticipativity and L 1-martingales in stochastic optimization problems. Math. Program. Study 6, 170–187 (1976)

    MathSciNet  Google Scholar 

  44. Rockafellar, R.T., Wets, R.J.-B.: Stochastic convex programming: basic duality. Pac. J. Math. 62, 173–195 (1976)

    MATH  MathSciNet  Google Scholar 

  45. Rockafellar, R.T., Wets, R.J.-B.: Stochastic convex programming: relatively complete recourse and induced feasibility. SIAM J. Control Optim. 14, 574–589 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  46. Rockafellar, R.T., Wets, R.J.-B.: Stochastic convex programming: singular multipliers and extended duality. Pac. J. Math. 62, 507–522 (1976)

    MATH  MathSciNet  Google Scholar 

  47. Dunford, N., Schwartz, J.T.: Linear Operators: Part I. Wiley, New York/Chichester/Brisbane/Toronto/Singapore (1988)

    MATH  Google Scholar 

  48. Pennanen, T.: Epi-convergent discretizations of multistage stochastic programs. Math. Oper. Res. 30(1), 245–256 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  49. Heitsch, H., Römisch, W., Strugarek, C.: Stability of multistage stochastic programs. SIAM J. Optim. 17, 511–525 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  50. Casey, M.S., Sen, S.: The scenario generation algorithm for multistage stochastic linear programming. Math. Oper. Res. 30(3), 615–631 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  51. Kuhn, D., Parpas, P., Rustem, B.: Threshold accepting approach to improve bound-based approximations for portfolio optimization. In: Kontoghiorghes, E., Rustem, B., Winker, P. (eds.) Computational Methods in Financial Engineering, pp. 3–26. Springer, Berlin (2008)

    Chapter  Google Scholar 

  52. Kuhn, D., Parpas, P., Rustem, B.: Bound-based decision rules in multistage stochastic programming. Kybernetika 44(2), 134–150 (2008)

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computing, Imperial College of Science, Technology, and Medicine, 180 Queen’s Gate, London, SW7 2AZ, UK

    D. Kuhn

Authors
  1. D. Kuhn
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to D. Kuhn.

Additional information

Communicated by D.G. Luenberger.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kuhn, D. Convergent Bounds for Stochastic Programs with Expected Value Constraints. J Optim Theory Appl 141, 597–618 (2009). https://doi.org/10.1007/s10957-008-9476-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-008-9476-1

Keywords

Search

Navigation