| Title:
|
Augmented Lagrangian method for recourse problem of two-stage stochastic linear programming (English) |
| Author:
|
Ketabchi, Saeed |
| Author:
|
Behboodi-Kahoo, Malihe |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
49 |
| Issue:
|
1 |
| Year:
|
2013 |
| Pages:
|
188-198 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
two-stage stochastic linear programming |
| Keyword:
|
recourse problem |
| Keyword:
|
normal solution |
| Keyword:
|
augmented Lagrangian method |
| MSC:
|
90C05 |
| MSC:
|
90C15 |
| MSC:
|
90C20 |
| . |
| Date available:
|
2013-03-05T15:18:52Z |
| Last updated:
|
2013-07-31 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143249 |
| . |
| Reference:
|
[1] Armijoo, L.: Minimazation of functions havinig Lipschitz-continus first partial derivetives..Pacific J. Math. 16 (1966), 1-3. MR 0191071, 10.2140/pjm.1966.16.1 |
| Reference:
|
[2] Benders, J. F.: Partitioning procedures for solving mixed-variables programming problems..Numer. Math. 4 (1962), 238-252. Zbl 1115.90361, MR 0147303, 10.1007/BF01386316 |
| Reference:
|
[3] Birge, J. R., Chen, X., Qi, L.: Newton Method for Stochastic Quadratic Programs with Recourse..AMR, School of Mathematics, UNSW, Sydney 1994. |
| Reference:
|
[4] Birge, J. R., Louveaux, F.: Introduction to stochastic programming..Springer Series in Operation Research, Springer-Verlag, New York 1997. Zbl 1223.90001, MR 1460264 |
| Reference:
|
[5] Branda, M.: Chance constrained problems: penalty reformulation and performance of sample approximation technique..Kybernetika 48 (2012), 105-122. Zbl 1243.93117, MR 2932930 |
| Reference:
|
[6] Chen, X.: A parallel BFGS-SQP method for stochastic linear programs..In: Computational Techniques and Applications, World Scientific 1995, pp. 67-74. Zbl 0909.65034, MR 1664847 |
| Reference:
|
[7] Chen, X.: Newton-type methods for stochastic programming..Math. Comput. Model. 31 (2000), 89-98. Zbl 1042.90595, MR 1768781, 10.1016/S0895-7177(00)00075-3 |
| Reference:
|
[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. Zbl 0836.65078, MR 1354646, 10.1016/0377-0427(94)00082-C |
| Reference:
|
[9] Chen, X., Womersley, R. S.: A parallel inexact Newton method for stochastic programs with recourse..Ann. Oper. Res. 64 (1995), 113-141. Zbl 0854.90106, MR 1405632, 10.1007/BF02187643 |
| Reference:
|
[10] Chen, X., Womersley, R. S.: Newton's method for quadratic stochastic programs with recourse..J. Comput. Appl. Math. 60 (1995), 29-46. Zbl 0836.65078, MR 1354646, 10.1016/0377-0427(94)00082-C |
| Reference:
|
[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. Zbl 0980.90060, MR 1787947, 10.1080/10556780008805789 |
| Reference:
|
[12] Dantzig, G. B.: Linear programming under uncertainty..Management Sci. 1 (1995), 197-206. Zbl 1215.90042, MR 0075511, 10.1287/mnsc.1.3-4.197 |
| Reference:
|
[13] Dantzig, G. B., Glynn, P. W.: Parallel processors for planning under uncertainty..Ann. Oper. Res. 22 (1990), 1-21. Zbl 0714.90074, MR 1042810, 10.1007/BF02023045 |
| Reference:
|
[14] Dantzig, G. B., Wolfe, P.: Decomposition principle for linear programs..Oper. Res. 8 (1960), 101-111. Zbl 0093.32806, 10.1287/opre.8.1.101 |
| Reference:
|
[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. MR 2179569, 10.1080/10556780500139690 |
| Reference:
|
[16] Higle, J. L., Sen, S.: Stochastic decomposition: an algorithm for two stage linear programs with recourse..Math. Oper. Res. 16 (1991), 650-669. Zbl 0746.90045, MR 1120475, 10.1287/moor.16.3.650 |
| Reference:
|
[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. MR 0726975, 10.1007/BF01442169 |
| Reference:
|
[18] Infanger, G.: Monte carlo(Importance) sampling within a benders decomposition algorithm for stochastic linear programs..Ann. Oper. Res. 39 (1992), 69-95. Zbl 0773.90054, MR 1204972, 10.1007/BF02060936 |
| Reference:
|
[19] Joe, S., Sloan, I. H.: Imbedded lattice rules for multidimensional integration..SIAM J. Numer. Anal. 29 (1992), 1119-1135. Zbl 0756.65027, MR 1173189, 10.1137/0729068 |
| Reference:
|
[20] Kall, P., Wallace, S. W.: Stochastic Programming..John Wiley and Sons, 1994. Zbl 0812.90122, MR 1315300 |
| Reference:
|
[21] Kanzow, C., Qi, H., Qi, L.: On the minimum norm solution of linear programs..J. Optim. Theory Appl. 116 (2003), 333-345. Zbl 1043.90046, MR 1967673, 10.1023/A:1022457904979 |
| Reference:
|
[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. Zbl 1131.90042, MR 2337444, 10.1016/j.cam.2006.07.004 |
| Reference:
|
[23] Mangasarian, O. L.: Normal solutions of linear programs..Math. Program. Stud. 22 (1984), 206-216. Zbl 0588.90058, MR 0774243, 10.1007/BFb0121017 |
| Reference:
|
[24] Mangasarian, O. L.: A Newton method for linear programming..J. Optim. Theory Appl. 121 (2004), 1-18. Zbl 1140.90467, MR 2062967, 10.1023/B:JOTA.0000026128.34294.77 |
| Reference:
|
[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. Zbl 1042.90597, MR 2052757 |
| Reference:
|
[26] Rockafellar, R. T.: Convex Analysis..Princeton University Press, Princeton 1970. Zbl 1011.49013, MR 0274683 |
| Reference:
|
[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. 10.1007/11754602_10 |
| Reference:
|
[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. MR 0253741, 10.1137/0117061 |
| . |
