Geodesic
Augmented Lagrangian method for recourse problem of two-stage stochastic linear programming
Kybernetika, Tome 49 (2013) no. 1, pp. 188-198 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 90C05, 90C15, 90C20
Keywords: two-stage stochastic linear programming; recourse problem; normal solution; augmented Lagrangian method 
@article{KYB_2013_49_1_a13,
     author = {Ketabchi, Saeed and Behboodi-Kahoo, Malihe},
     title = {Augmented {Lagrangian} method for recourse problem of two-stage stochastic linear programming},
     journal = {Kybernetika},
     pages = {188--198},
     year = {2013},
     volume = {49},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2013_49_1_a13/}
}
TY  - JOUR
AU  - Ketabchi, Saeed
AU  - Behboodi-Kahoo, Malihe
TI  - Augmented Lagrangian method for recourse problem of two-stage stochastic linear programming
JO  - Kybernetika
PY  - 2013
SP  - 188
EP  - 198
VL  - 49
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/KYB_2013_49_1_a13/
LA  - en
ID  - KYB_2013_49_1_a13
ER  - 
%0 Journal Article
%A Ketabchi, Saeed
%A Behboodi-Kahoo, Malihe
%T Augmented Lagrangian method for recourse problem of two-stage stochastic linear programming
%J Kybernetika
%D 2013
%P 188-198
%V 49
%N 1
%U http://geodesic.mathdoc.fr/item/KYB_2013_49_1_a13/
%G en
%F KYB_2013_49_1_a13
Ketabchi, Saeed; Behboodi-Kahoo, Malihe. Augmented Lagrangian method for recourse problem of two-stage stochastic linear programming. Kybernetika, Tome 49 (2013) no. 1, pp. 188-198. http://geodesic.mathdoc.fr/item/KYB_2013_49_1_a13/

[1] Armijoo, L.: Minimazation of functions havinig Lipschitz-continus first partial derivetives. Pacific J. Math. 16 (1966), 1-3. | DOI | MR

[2] Benders, J. F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4 (1962), 238-252. | DOI | MR | Zbl

[3] Birge, J. R., Chen, X., Qi, L.: Newton Method for Stochastic Quadratic Programs with Recourse. AMR, School of Mathematics, UNSW, Sydney 1994.

[4] Birge, J. R., Louveaux, F.: Introduction to stochastic programming. Springer Series in Operation Research, Springer-Verlag, New York 1997. | MR | Zbl

[5] Branda, M.: Chance constrained problems: penalty reformulation and performance of sample approximation technique. Kybernetika 48 (2012), 105-122. | MR | Zbl

[6] Chen, X.: A parallel BFGS-SQP method for stochastic linear programs. In: Computational Techniques and Applications, World Scientific 1995, pp. 67-74. | MR | Zbl

[7] Chen, X.: Newton-type methods for stochastic programming. Math. Comput. Model. 31 (2000), 89-98. | DOI | MR | Zbl

[8] Chen, X., Qi, L., Womersley, R. S.: Newton's method for quadratic stochastic programs with recourse. J. Comp. Appl. Math. 60 (1995), 29-46. | DOI | MR | Zbl

[9] Chen, X., Womersley, R. S.: A parallel inexact Newton method for stochastic programs with recourse. Ann. Oper. Res. 64 (1995), 113-141. | DOI | MR | Zbl

[10] Chen, X., Womersley, R. S.: Newton's method for quadratic stochastic programs with recourse. J. Comput. Appl. Math. 60 (1995), 29-46. | DOI | MR | Zbl

[11] Chen, X., Womersley, R. S.: Random test problems and parallel methods for quadratic programs and quadratic stochastic programs. Optim. Method. Softw. 13 (2000), 275-306. | DOI | MR | Zbl

[12] Dantzig, G. B.: Linear programming under uncertainty. Management Sci. 1 (1995), 197-206. | DOI | MR | Zbl

[13] Dantzig, G. B., Glynn, P. W.: Parallel processors for planning under uncertainty. Ann. Oper. Res. 22 (1990), 1-21. | DOI | MR | Zbl

[14] Dantzig, G. B., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8 (1960), 101-111. | DOI | Zbl

[15] Evtushenko, Yu. G., Golikov, A. I., Mollaverdi, N.: Augmented lagrangian method for large-scale linear programming problem. Optim. Method. Softw. 20 (2005), 515-524. | DOI | MR

[16] Higle, J. L., Sen, S.: Stochastic decomposition: an algorithm for two stage linear programs with recourse. Math. Oper. Res. 16 (1991), 650-669. | DOI | MR | Zbl

[17] Hiriart-Urruty, J.-B., Strodiot, J. J., Nguyen, V. H.: Generalized Hessian matrics and second-order optimality condisions for problems CL1 data. Appl. Math. Optim. 11 (1984), 43-56. | DOI | MR

[18] Infanger, G.: Monte carlo(Importance) sampling within a benders decomposition algorithm for stochastic linear programs. Ann. Oper. Res. 39 (1992), 69-95. | DOI | MR | Zbl

[19] Joe, S., Sloan, I. H.: Imbedded lattice rules for multidimensional integration. SIAM J. Numer. Anal. 29 (1992), 1119-1135. | DOI | MR | Zbl

[20] Kall, P., Wallace, S. W.: Stochastic Programming. John Wiley and Sons, 1994. | MR | Zbl

[21] Kanzow, C., Qi, H., Qi, L.: On the minimum norm solution of linear programs. J. Optim. Theory Appl. 116 (2003), 333-345. | DOI | MR | Zbl

[22] Ketabchi, S., Ansari-Piri, E.: On the solution set of convex problems and its numerical application. J. Comput. Appl. Math. 206 (2007), 288-292. | DOI | MR | Zbl

[23] Mangasarian, O. L.: Normal solutions of linear programs. Math. Program. Stud. 22 (1984), 206-216. | DOI | MR | Zbl

[24] Mangasarian, O. L.: A Newton method for linear programming. J. Optim. Theory Appl. 121 (2004), 1-18. | DOI | MR | Zbl

[25] Prekopa, A.: 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. | MR | Zbl

[26] Rockafellar, R. T.: Convex Analysis. Princeton University Press, Princeton 1970. | MR | Zbl

[27] Tarim, S. A., Miguel, I.: A hybrid Bender's decomposition method for solving stochastic constraint programs with linear recourse. Lect. Notes Comput. Sci. 3978 (2006), 133-148. | DOI

[28] Slyke, R. M. Van, Wets, R.: $L-$shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17 (1969), 638-663. | DOI | MR