Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
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
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.
References:
[1] Armijoo, L.: Minimazation of functions havinig Lipschitz-continus first partial derivetives. Pacific J. Math. 16 (1966), 1-3. DOI 10.2140/pjm.1966.16.1 | MR 0191071
[2] Benders, J. F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4 (1962), 238-252. DOI 10.1007/BF01386316 | MR 0147303 | Zbl 1115.90361
[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 1460264 | Zbl 1223.90001
[5] Branda, M.: Chance constrained problems: penalty reformulation and performance of sample approximation technique. Kybernetika 48 (2012), 105-122. MR 2932930 | Zbl 1243.93117
[6] Chen, X.: A parallel BFGS-SQP method for stochastic linear programs. In: Computational Techniques and Applications, World Scientific 1995, pp. 67-74. MR 1664847 | Zbl 0909.65034
[7] Chen, X.: Newton-type methods for stochastic programming. Math. Comput. Model. 31 (2000), 89-98. DOI 10.1016/S0895-7177(00)00075-3 | MR 1768781 | Zbl 1042.90595
[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 10.1016/0377-0427(94)00082-C | MR 1354646 | Zbl 0836.65078
[9] Chen, X., Womersley, R. S.: A parallel inexact Newton method for stochastic programs with recourse. Ann. Oper. Res. 64 (1995), 113-141. DOI 10.1007/BF02187643 | MR 1405632 | Zbl 0854.90106
[10] Chen, X., Womersley, R. S.: Newton's method for quadratic stochastic programs with recourse. J. Comput. Appl. Math. 60 (1995), 29-46. DOI 10.1016/0377-0427(94)00082-C | MR 1354646 | Zbl 0836.65078
[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 10.1080/10556780008805789 | MR 1787947 | Zbl 0980.90060
[12] Dantzig, G. B.: Linear programming under uncertainty. Management Sci. 1 (1995), 197-206. DOI 10.1287/mnsc.1.3-4.197 | MR 0075511 | Zbl 1215.90042
[13] Dantzig, G. B., Glynn, P. W.: Parallel processors for planning under uncertainty. Ann. Oper. Res. 22 (1990), 1-21. DOI 10.1007/BF02023045 | MR 1042810 | Zbl 0714.90074
[14] Dantzig, G. B., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8 (1960), 101-111. DOI 10.1287/opre.8.1.101 | Zbl 0093.32806
[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 10.1080/10556780500139690 | MR 2179569
[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 10.1287/moor.16.3.650 | MR 1120475 | Zbl 0746.90045
[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 10.1007/BF01442169 | MR 0726975
[18] Infanger, G.: Monte carlo(Importance) sampling within a benders decomposition algorithm for stochastic linear programs. Ann. Oper. Res. 39 (1992), 69-95. DOI 10.1007/BF02060936 | MR 1204972 | Zbl 0773.90054
[19] Joe, S., Sloan, I. H.: Imbedded lattice rules for multidimensional integration. SIAM J. Numer. Anal. 29 (1992), 1119-1135. DOI 10.1137/0729068 | MR 1173189 | Zbl 0756.65027
[20] Kall, P., Wallace, S. W.: Stochastic Programming. John Wiley and Sons, 1994. MR 1315300 | Zbl 0812.90122
[21] Kanzow, C., Qi, H., Qi, L.: On the minimum norm solution of linear programs. J. Optim. Theory Appl. 116 (2003), 333-345. DOI 10.1023/A:1022457904979 | MR 1967673 | Zbl 1043.90046
[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 10.1016/j.cam.2006.07.004 | MR 2337444 | Zbl 1131.90042
[23] Mangasarian, O. L.: Normal solutions of linear programs. Math. Program. Stud. 22 (1984), 206-216. DOI 10.1007/BFb0121017 | MR 0774243 | Zbl 0588.90058
[24] Mangasarian, O. L.: A Newton method for linear programming. J. Optim. Theory Appl. 121 (2004), 1-18. DOI 10.1023/B:JOTA.0000026128.34294.77 | MR 2062967 | Zbl 1140.90467
[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 2052757 | Zbl 1042.90597
[26] Rockafellar, R. T.: Convex Analysis. Princeton University Press, Princeton 1970. MR 0274683 | Zbl 1011.49013
[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 10.1007/11754602_10
[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 10.1137/0117061 | MR 0253741
Search
Partner of
