Abstract
Stochastic decomposition is a stochastic analog of Benders' decomposition in which randomly generated observations of random variables are used to construct statistical estimates of supports of the objective function. In contrast to deterministic Benders' decomposition for two stage stochastic programs, the stochastic version requires infinitely many inequalities to ensure convergence. We show that asymptotic optimality can be achieved with a finite master program provided that a quadratic regularizing term is included. Our computational results suggest that the elimination of the cutting planes impacts neither the number of iterations required nor the statistical properties of the terminal solution.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J.R. Birge, “Decomposition and partitioning methods for multi-stage stochastic linear programs,”Operations Research 33 (1985) 989–1007.
J.L. Higle and S. Sen, “Stochastic decomposition: an algorithm for two stage linear programs with recourse,”Mathematics of Operations Research 16 (1991a) 650–669.
J.L. Higle and S. Sen, “Statistical verification of optimality conditions,”Annals of Operations Research 30 (1991b) 215–240.
J.L. Higle and S. Sen, “On the convergence of algorithms, with implications for stochastic and nondifferentiable optimization,”Mathematics of Operations Research 17 (1992) 112–131.
J.K. Ho and E. Loute, “A set of staircase linear programming test problems,”Mathematical Programming 20 (1981) 245–250.
K.C. Kiwiel,Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics No. 1133 (Springer-Verlag, Berlin, 1985).
B. Lemaire, “The Proximal Algorithm,”International Series of Numerical Mathematics 87 (1989) 73–87.
F.V. Louveaux and Y. Smeers, “Optimal investment for electricity generation: A stochastic model and a test problem,” in: Y. Ermoliev and R.J-B. Wets (eds.),Numerical Techniques for Stochastic Optimization (Springer-Verlag, Berlin, 1988) pp. 445–453.
R.T. Rockafellar, “Monotone operators and the proximal point algorithm,”SIAM Journal of Control and Optimization 14 (1976) 877–898.
A. Ruszczyński, “A regularized decomposition method for minimizing a sum of polyhedral functions,”Mathematical Programming 35 (1986) 309–333.
A. Ruszczyński, “A linearization method for nonsmooth stochastic programming problems,”Mathematics of Operations Research 12 (1987) 32–49.
S. Sen, J. Mai and J.L. Higle, “Solution of large scale stochastic programs with stochastic decomposition algorithms,” in: W. Hager, D. Hearn and P. Pardalos (eds.),Large Scale Optimization: The State of the Art (Kluwer Academic Publishers, Dordrecht, 1994), to appear.
R. Van Slyke and R. J-B. Wets, “L-Shaped linear programs with applications to optimal control and stochastic programming,”SIAM Journal on Applied Mathematics 17 (1969) 638–663.
R. J-B. Wets, “Stochastic programs with fixed recourse; the equivalent deterministic problem,”SIAM Review 16 (1974) 309–339.
D.S. Yakowitz, “A regularized stochastic decomposition algorithm for two stage stochastic linear programs,”Computational Optimization and Application 3 (1994) 59–81.
Author information
Authors and Affiliations
Additional information
This work was supported in part by Grant No. AFOSR-88-0076 from the Air Force Office of Scientific Research and Grant Nos. DDM-89-10046, DDM-9114352 from the National Science Foundation.
Corresponding author.
Rights and permissions
About this article
Cite this article
Higle, J.L., Sen, S. Finite master programs in regularized stochastic decomposition. Mathematical Programming 67, 143–168 (1994). https://doi.org/10.1007/BF01582219
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582219