×

Smoothing techniques and augmented Lagrangian method for recourse problem of two-stage stochastic linear programming. (English) Zbl 1271.90047

Summary: The augmented Lagrangian method can be used for solving recourse problems and obtaining their normal solution in solving two-stage stochastic linear programming problems. The augmented Lagrangian objective function of a stochastic linear problem is not twice differentiable which precludes the use of a Newton method. In this paper, we apply the smoothing techniques and a fast Newton-Armijo algorithm for solving an unconstrained smooth reformulation of this problem. Computational results and comparisons are given to show the effectiveness and speed of the algorithm.

MSC:

90C05 Linear programming
90C15 Stochastic programming

Software:

SSVM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer Series in Operations Research, Springer, New York, NY, USA, 1997. · Zbl 0920.62042
[2] G. B. Dantzig, “Linear programming under uncertainty,” Management Science. Journal of the Institute of Management Science. Application and Theory Series, vol. 1, pp. 197-206, 1955. · Zbl 0995.90589 · doi:10.1287/mnsc.1.3-4.197
[3] J. L. Higle and S. Sen, “Stochastic decomposition: an algorithm for two-stage linear programs with recourse,” Mathematics of Operations Research, vol. 16, no. 3, pp. 650-669, 1991. · Zbl 0746.90045 · doi:10.1287/moor.16.3.650
[4] P. Kall and S. W. Wallace, Stochastic Programming, John Wiley & Sons, Chichester, UK, 1994. · Zbl 0812.90122
[5] S. A. Tarim and I. A. Miguel, “A hybrid benders’ decomposition method for solving stochastic constraint programs with linear recourse,” in Recent Advances in Constraints, vol. 3978 of Lecture Notes in Computer Science, pp. 133-148, Springer, Berlin, Germany, 2006. · Zbl 1180.68252 · doi:10.1007/11754602
[6] J. R. Birge, X. Chen, L. Qi, and Z. Wei, “A stochastic Newton method for stochastic quadratic programs with recourse,” Tech. Rep., Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Mich, USA, 1994.
[7] X. Chen, “A parallel BFGS-SQP method for stochastic linear programs,” in World Scientific, pp. 67-74, World Scientific, River Edge, NJ, USA, 1995. · Zbl 0909.65034
[8] X. Chen, “Newton-type methods for stochastic programming,” Mathematical and Computer Modelling, vol. 31, no. 10-12, pp. 89-98, 2000. · Zbl 1042.90595 · doi:10.1016/S0895-7177(00)00075-3
[9] X. J. Chen, L. Q. Qi, and R. S. Womersley, “Newton’s method for quadratic stochastic programs with recourse,” Journal of Computational and Applied Mathematics, vol. 60, no. 1-2, pp. 29-46, 1995. · Zbl 0836.65078 · doi:10.1016/0377-0427(94)00082-C
[10] X. Chen and R. S. Womersley, “A parallel inexact Newton method for stochastic programs with recourse,” Annals of Operations Research, vol. 64, pp. 113-141, 1996. · Zbl 0854.90106 · doi:10.1007/BF02187643
[11] X. Chen and R. S. Womersley, “Random test problems and parallel methods for quadratic programs and quadratic stochastic programs,” Optimization Methods and Software, vol. 13, no. 4, pp. 275-306, 2000. · Zbl 0980.90060 · doi:10.1080/10556780008805789
[12] X. Chen and Y. Ye, “On homotopy-smoothing methods for box-constrained variational inequalities,” SIAM Journal on Control and Optimization, vol. 37, no. 2, pp. 589-616, 1999. · Zbl 0973.65051 · doi:10.1137/S0363012997315907
[13] Y.-J. Lee and O. L. Mangasarian, “SSVM: a smooth support vector machine for classification,” Computational Optimization and Applications. An International Journal, vol. 20, no. 1, pp. 5-22, 2001. · Zbl 1017.90105 · doi:10.1023/A:1011215321374
[14] C. Kanzow, H. Qi, and L. Qi, “On the minimum norm solution of linear programs,” Journal of Optimization Theory and Applications, vol. 116, no. 2, pp. 333-345, 2003. · Zbl 1043.90046 · doi:10.1023/A:1022457904979
[15] O. L. Mangasarian, “A Newton method for linear programming,” Journal of Optimization Theory and Applications, vol. 121, no. 1, pp. 1-18, 2004. · Zbl 1140.90467 · doi:10.1023/B:JOTA.0000026128.34294.77
[16] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, USA, 1970. · Zbl 0193.18401
[17] Yu. G. Evtushenko, A. I. Golikov, and N. Mollaverdy, “Augmented Lagrangian method for large-scale linear programming problems,” Optimization Methods & Software, vol. 20, no. 4-5, pp. 515-524, 2005. · Zbl 1134.90023 · doi:10.1080/10556780500139690
[18] C. H. Chen and O. L. Mangasarian, “Smoothing methods for convex inequalities and linear complementarity problems,” Mathematical Programming, vol. 71, no. 1, pp. 51-69, 1995. · Zbl 0855.90124 · doi:10.1007/BF01592244
[19] C. Chen and O. L. Mangasarian, “A class of smoothing functions for nonlinear and mixed complementarity problems,” Computational Optimization and Applications. An International Journal, vol. 5, no. 2, pp. 97-138, 1996. · Zbl 0859.90112 · doi:10.1007/BF00249052
[20] X. Chen, L. Qi, and D. Sun, “Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities,” Mathematics of Computation, vol. 67, no. 222, pp. 519-540, 1998. · Zbl 0894.90143 · doi:10.1090/S0025-5718-98-00932-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.