Kybernetika 49 no. 1, 188-198, 2013

Augmented Lagrangian method for recourse problem of two-stage stochastic linear programming

Saeed Ketabchi and Malihe Behboodi-Kahoo

Abstract:

In this paper, the augmented Lagrangian method is investigated for solving recourse problems and obtaining their normal solution in solving two-stage stochastic linear programming problems. The objective function of stochastic linear programming problem is piecewise linear and non-differentiable. Therefore, to use a smooth optimization methods, the objective function is approximated by a differentiable and piecewise quadratic function. Using quadratic approximation, it is required to obtain the least 2-norm solution for many linear programming problems in each iteration. To obtain the least 2-norm solution for inner problems based on the augmented Lagrangian method, the generalized Newton method is applied.

Keywords:

two-stage stochastic linear programming, recourse problem, normal solution, augmented Lagrangian method

Classification:

90C15, 90C05, 90C20

paper.pdf

References:

  1. L. Armijoo: Minimazation of functions havinig Lipschitz-continus first partial derivetives. Pacific J. Math. 16 (1966), 1-3.   CrossRef
  2. J. F. Benders: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4 (1962), 238-252.   CrossRef
  3. J. R. Birge, X. Chen and L. Qi: Newton Method for Stochastic Quadratic Programs with Recourse. AMR, School of Mathematics, UNSW, Sydney 1994.   CrossRef
  4. J. R. Birge and F. Louveaux: Introduction to stochastic programming. Springer Series in Operation Research, Springer-Verlag, New York 1997.   CrossRef
  5. M. Branda: Chance constrained problems: penalty reformulation and performance of sample approximation technique. Kybernetika 48 (2012), 105-122.   CrossRef
  6. X. Chen: A parallel BFGS-SQP method for stochastic linear programs. In: Computational Techniques and Applications, World Scientific 1995, pp. 67-74.   CrossRef
  7. X. Chen: Newton-type methods for stochastic programming. Math. Comput. Model. 31 (2000), 89-98.   CrossRef
  8. X. Chen, L. Qi and R. S. Womersley: Newton's method for quadratic stochastic programs with recourse. J. Comp. Appl. Math. 60 (1995), 29-46.   CrossRef
  9. X. Chen and R. S. Womersley: A parallel inexact Newton method for stochastic programs with recourse. Ann. Oper. Res. 64 (1995), 113-141.   CrossRef
  10. X. Chen and R. S. Womersley: Newton's method for quadratic stochastic programs with recourse. J. Comput. Appl. Math. 60 (1995), 29-46.   CrossRef
  11. X. Chen and R. S. Womersley: Random test problems and parallel methods for quadratic programs and quadratic stochastic programs. Optim. Method. Softw. 13 (2000), 275-306.   CrossRef
  12. G. B. Dantzig: Linear programming under uncertainty. Management Sci. 1 (1995), 197-206.   CrossRef
  13. G. B. Dantzig and P. W. Glynn: Parallel processors for planning under uncertainty. Ann. Oper. Res. 22 (1990), 1-21.   CrossRef
  14. G. B. Dantzig and P. Wolfe: Decomposition principle for linear programs. Oper. Res. 8 (1960), 101-111.   CrossRef
  15. Yu. G. Evtushenko, A. I. Golikov and N. Mollaverdi: Augmented lagrangian method for large-scale linear programming problem. Optim. Method. Softw. 20 (2005), 515-524.   CrossRef
  16. J. L. Higle and S. Sen: Stochastic decomposition: an algorithm for two stage linear programs with recourse. Math. Oper. Res. 16 (1991), 650-669.   CrossRef
  17. J.-B. Hiriart-Urruty, J. J. Strodiot and V. H. Nguyen: Generalized Hessian matrics and second-order optimality condisions for problems CL1 data. Appl. Math. Optim. 11 (1984), 43-56.   CrossRef
  18. G. Infanger: Monte carlo(Importance) sampling within a benders decomposition algorithm for stochastic linear programs. Ann. Oper. Res. 39 (1992), 69-95.   CrossRef
  19. S. Joe and I. H. Sloan: Imbedded lattice rules for multidimensional integration. SIAM J. Numer. Anal. 29 (1992), 1119-1135.   CrossRef
  20. P. Kall and S. W. Wallace: Stochastic Programming. John Wiley and Sons, 1994.   CrossRef
  21. C. Kanzow, H. Qi and L. Qi: On the minimum norm solution of linear programs. J. Optim. Theory Appl. 116 (2003), 333-345.   CrossRef
  22. S. Ketabchi and E. Ansari-Piri: On the solution set of convex problems and its numerical application. J. Comput. Appl. Math. 206 (2007), 288-292.   CrossRef
  23. O. L. Mangasarian: Normal solutions of linear programs. Math. Program. Stud. 22 (1984), 206-216.   CrossRef
  24. O. L. Mangasarian: A Newton method for linear programming. J. Optim. Theory Appl. 121 (2004), 1-18.   CrossRef
  25. A. Prekopa: Probabilistic programming. In: Stochastic programming (A. Ruszczynski and A. Shapiro, eds.), Handbook in Operations Research and Management Science 10 (2003), pp. 267-352, Elsevier, Amsterdam.   CrossRef
  26. R. T. Rockafellar: Convex Analysis. Princeton University Press, Princeton 1970.   CrossRef
  27. S. A. Tarim and I. Miguel: A hybrid Bender's decomposition method for solving stochastic constraint programs with linear recourse. Lect. Notes Comput. Sci. 3978 (2006), 133-148.   CrossRef
  28. R. M. Van Slyke and R. Wets: $L-$shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17 (1969), 638-663.   CrossRef