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

Saeed Ketabchi; Malihe Behboodi-Kahoo

Kybernetika (2013)

  • Volume: 49, Issue: 1, page 188-198
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Ketabchi, Saeed, and Behboodi-Kahoo, Malihe. "Augmented Lagrangian method for recourse problem of two-stage stochastic linear programming." Kybernetika 49.1 (2013): 188-198. <http://eudml.org/doc/252463>.

@article{Ketabchi2013,
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.},
author = {Ketabchi, Saeed, Behboodi-Kahoo, Malihe},
journal = {Kybernetika},
keywords = {two-stage stochastic linear programming; recourse problem; normal solution; augmented Lagrangian method; two-stage stochastic linear programming; recourse problem; normal solution; augmented Lagrangian method},
language = {eng},
number = {1},
pages = {188-198},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Augmented Lagrangian method for recourse problem of two-stage stochastic linear programming},
url = {http://eudml.org/doc/252463},
volume = {49},
year = {2013},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 49
IS - 1
SP - 188
EP - 198
AB - 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.
LA - eng
KW - two-stage stochastic linear programming; recourse problem; normal solution; augmented Lagrangian method; two-stage stochastic linear programming; recourse problem; normal solution; augmented Lagrangian method
UR - http://eudml.org/doc/252463
ER -

References

top
  1. Armijoo, L., 10.2140/pjm.1966.16.1, Pacific J. Math. 16 (1966), 1-3. MR0191071DOI10.2140/pjm.1966.16.1
  2. Benders, J. F., 10.1007/BF01386316, Numer. Math. 4 (1962), 238-252. Zbl1115.90361MR0147303DOI10.1007/BF01386316
  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. Zbl1223.90001MR1460264
  5. Branda, M., Chance constrained problems: penalty reformulation and performance of sample approximation technique., Kybernetika 48 (2012), 105-122. Zbl1243.93117MR2932930
  6. Chen, X., A parallel BFGS-SQP method for stochastic linear programs., In: Computational Techniques and Applications, World Scientific 1995, pp. 67-74. Zbl0909.65034MR1664847
  7. Chen, X., 10.1016/S0895-7177(00)00075-3, Math. Comput. Model. 31 (2000), 89-98. Zbl1042.90595MR1768781DOI10.1016/S0895-7177(00)00075-3
  8. Chen, X., Qi, L., Womersley, R. S., 10.1016/0377-0427(94)00082-C, J. Comp. Appl. Math. 60 (1995), 29-46. Zbl0836.65078MR1354646DOI10.1016/0377-0427(94)00082-C
  9. Chen, X., Womersley, R. S., 10.1007/BF02187643, Ann. Oper. Res. 64 (1995), 113-141. Zbl0854.90106MR1405632DOI10.1007/BF02187643
  10. Chen, X., Womersley, R. S., 10.1016/0377-0427(94)00082-C, J. Comput. Appl. Math. 60 (1995), 29-46. Zbl0836.65078MR1354646DOI10.1016/0377-0427(94)00082-C
  11. Chen, X., Womersley, R. S., 10.1080/10556780008805789, Optim. Method. Softw. 13 (2000), 275-306. Zbl0980.90060MR1787947DOI10.1080/10556780008805789
  12. Dantzig, G. B., 10.1287/mnsc.1.3-4.197, Management Sci. 1 (1995), 197-206. Zbl1215.90042MR0075511DOI10.1287/mnsc.1.3-4.197
  13. Dantzig, G. B., Glynn, P. W., 10.1007/BF02023045, Ann. Oper. Res. 22 (1990), 1-21. Zbl0714.90074MR1042810DOI10.1007/BF02023045
  14. Dantzig, G. B., Wolfe, P., 10.1287/opre.8.1.101, Oper. Res. 8 (1960), 101-111. Zbl0093.32806DOI10.1287/opre.8.1.101
  15. Evtushenko, Yu. G., Golikov, A. I., Mollaverdi, N., 10.1080/10556780500139690, Optim. Method. Softw. 20 (2005), 515-524. MR2179569DOI10.1080/10556780500139690
  16. Higle, J. L., Sen, S., 10.1287/moor.16.3.650, Math. Oper. Res. 16 (1991), 650-669. Zbl0746.90045MR1120475DOI10.1287/moor.16.3.650
  17. Hiriart-Urruty, J.-B., Strodiot, J. J., Nguyen, V. H., 10.1007/BF01442169, Appl. Math. Optim. 11 (1984), 43-56. MR0726975DOI10.1007/BF01442169
  18. Infanger, G., 10.1007/BF02060936, Ann. Oper. Res. 39 (1992), 69-95. Zbl0773.90054MR1204972DOI10.1007/BF02060936
  19. Joe, S., Sloan, I. H., 10.1137/0729068, SIAM J. Numer. Anal. 29 (1992), 1119-1135. Zbl0756.65027MR1173189DOI10.1137/0729068
  20. Kall, P., Wallace, S. W., Stochastic Programming., John Wiley and Sons, 1994. Zbl0812.90122MR1315300
  21. Kanzow, C., Qi, H., Qi, L., 10.1023/A:1022457904979, J. Optim. Theory Appl. 116 (2003), 333-345. Zbl1043.90046MR1967673DOI10.1023/A:1022457904979
  22. Ketabchi, S., Ansari-Piri, E., 10.1016/j.cam.2006.07.004, J. Comput. Appl. Math. 206 (2007), 288-292. Zbl1131.90042MR2337444DOI10.1016/j.cam.2006.07.004
  23. Mangasarian, O. L., 10.1007/BFb0121017, Math. Program. Stud. 22 (1984), 206-216. Zbl0588.90058MR0774243DOI10.1007/BFb0121017
  24. Mangasarian, O. L., 10.1023/B:JOTA.0000026128.34294.77, J. Optim. Theory Appl. 121 (2004), 1-18. Zbl1140.90467MR2062967DOI10.1023/B:JOTA.0000026128.34294.77
  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. Zbl1042.90597MR2052757
  26. Rockafellar, R. T., Convex Analysis., Princeton University Press, Princeton 1970. Zbl1011.49013MR0274683
  27. Tarim, S. A., Miguel, I., 10.1007/11754602_10, Lect. Notes Comput. Sci. 3978 (2006), 133-148. DOI10.1007/11754602_10
  28. Slyke, R. M. Van, Wets, R., 10.1137/0117061, SIAM J. Appl. Math. 17 (1969), 638-663. MR0253741DOI10.1137/0117061

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.