SpringerLink
Log in

A Lagrangian Dual Method with Self-Concordant Barriers for Multi-Stage Stochastic Convex Programming

  • Published:
Mathematical Programming Submit manuscript

Abstract.

This paper presents an algorithm for solving multi-stage stochastic convex nonlinear programs. The algorithm is based on the Lagrangian dual method which relaxes the nonanticipativity constraints, and the barrier function method which enhances the smoothness of the dual objective function so that the Newton search directions can be used. The algorithm is shown to be of global convergence and of polynomial-time complexity.

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
EUR 32.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 includes VAT (Canada)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms, 2nd Edition, John Wiley & Sons, 1993

  2. Birge, J.R.: Current trends in stochastic programming computation and applications. Technical Report 95–15, Dept of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109-2117, USA, 1995

  3. Birge, J.R., Dempster, M.A.H., Gassmann, H.I., Gunn, E.A., King, A.J., Wallace, S.W.: A standard input format for multistage stochastic linear programs. COAL Newsletter 17, 1–19 (1987)

    Google Scholar 

  4. Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming, Springer-Verlag, 1997

  5. Birge, J.R., Rosa, C.H.: Modelling investment uncertainty in the costs of global CO2 emission policy. European Journal of Operations Research 83, 466–488 (1995)

    Article  MATH  Google Scholar 

  6. Cariño, D.R., Kent, T., Meyers, D.H., Stacy, C., Sylvanus, M., Turner, A.L., Watanabe, K., Ziemba, W.T.: The Russel- Yasuda Kasai Model: An asset/liability model for a Japanese insurance company using multistage stochastic programming. Interfaces 24, 29–49 (1994)

    Google Scholar 

  7. Chen, B.J., Robinson, S.M.: Scenario analysis vis bundle decomposition. Ann. Oper. Res. 56, 39–63 (1995)

    MathSciNet  Google Scholar 

  8. Eppen, G.D., Martin, R.K., Schrage, L.: A scenario approach to capacity planning. Operations Research 37, 517–527 (1989)

    Google Scholar 

  9. Ferguson, A., Dantzig, G.B.: The allocation of aircraft to routes: an example of linear programming under uncertain demands. Management Science 3, 45–73 (1956)

    Article  MATH  MathSciNet  Google Scholar 

  10. Frantzeskakis, L., Powell, W.B.: A successive linear approximation procedure for stochastic, dynamic vehicle allocation problems. Transportation Science 24, 40–57 (1990)

    MATH  MathSciNet  Google Scholar 

  11. Gassmann, H.I.: MSLiP: A computer code for the multistage stochastic linear programming problem. Mathematical Programming 47, 407–423 (1990)

    MATH  MathSciNet  Google Scholar 

  12. Helgason, T., Wallace, S.W.: Approximate scenarios solutions in the progressive hedging algorithm. Ann. Oper. Res. 31, 425–444 (1991)

    MATH  MathSciNet  Google Scholar 

  13. Hertog, Den, D., Jarre, F., Roos, C., Terlaky, T.: A sufficient condition for self-concordance, with application to some classes of structured convex programming problems. Mathematical Programming 69, 75–88 (1995)

    Article  MathSciNet  Google Scholar 

  14. Higle, J.L., Sen, S.: Stochastic Decomposition: A statistical method for large scale stochastic linear programming. Kluwer Academic Publishers, Dordrecht, Netherlands, 1996

  15. Jarre, F.: Interior-point methods for convex programming. Appl. Math. Optim. 26, 287–311 (1992)

    MATH  MathSciNet  Google Scholar 

  16. Kall, P., Wallace, S.W.: Stochastic Programming. John Wiley & Sons, New York, 1994

  17. King, A.J.: Stochastic programming problems: examples from the literature. Numerical Techniques for Stochastic Optimization. Y. Ermoliev and R. J-B Wets (eds.), Springer-Verlag, 543–-567, (1988)

  18. Kojima, M., Megiddo, N., Mizuno, S., Shindoh, S.: Horizontal and vertical decomposition in interior point methods for linear programs. Working paper, Dept of Mathematical and Computing Sciences, Tokyo Institute of Technology, Japan, 1993

  19. Liu, X., Toh, K-C., Zhao, G.: On implementation of a Lagrangian dual method for solving multi-stage stochastic programming problems. Research Report, Department of Mathematics, National University of Singapore, Singapore, 2000

  20. Mulvey, J.M., Ruszczyński, A.: A new scenario decomposition method for large scale stochastic optimization. Operations Research 43, 477–490 (1995)

    MATH  MathSciNet  Google Scholar 

  21. Mulvey, J.M., Vladimirou, H.: Applying the progressive hedging algorithm to stochastic generalized networks. Annals of Operations Research 31, 399–424 (1991)

    MATH  MathSciNet  Google Scholar 

  22. Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming. SIAM, Philadelphia, PE, 1994

  23. Pereira, M.V.F., Pinto, L.M.V.G.: Multi-stage stochastic optimization applied to energy planning. Mathematical Programming 52, 359–375 (1991)

    MATH  MathSciNet  Google Scholar 

  24. Peters, R.J., Boskma, K., Kuper, H.A.E.: Stochastic programming in production planning: a case with non-simple recourse. Statistica Neerlanica 31, 113–126 (1977)

    Article  MATH  Google Scholar 

  25. Rockafellar, R.T., Wets, R.J-B.: Scenarios and policy aggregation in optimization under uncertainty. Mathematics of Operations Research 16, 119–147 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  26. Ruszczyński, A.: On convergence of an augmented Lagrangian decomposition method for sparse convex optimization. Math. Oper. Res. 20, 634–656 (1995)

    MATH  MathSciNet  Google Scholar 

  27. Van Slyke, R., Wets, R.J.-B: L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Applied Math. 17, 638–663 (1969)

    MATH  Google Scholar 

  28. Zhao, G.: Interior-point methods with decomposition for solving large-scale linear programs. JOTA 102, 169–192 (1999)

    Article  MATH  Google Scholar 

  29. Zhao, G.: A log-barrier method with Benders decomposition for solving two-stage stochastic programs. Math. Programming. 90, 507–536 (2001)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore, 117543

    Gongyun Zhao

Authors
  1. Gongyun Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gongyun Zhao.

Additional information

Mathematics Subject Classification (2000): 90C15, 90C51, 90C06, 90C25, 90C60

Research is partially supported by NUS Academic Research Grant R-146-000-006-112

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zhao, G. A Lagrangian Dual Method with Self-Concordant Barriers for Multi-Stage Stochastic Convex Programming. Math. Program. 102, 1–24 (2005). https://doi.org/10.1007/s10107-003-0471-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-003-0471-x

Keywords

Search

Navigation