×

Newton-type methods for stochastic programming. (English) Zbl 1042.90595

Summary: Stochastic programming is concerned with practical procedures for decision making under uncertainty, by modelling uncertainties and risks associated with decision in a form suitable form siutable for optimization. The field is developing rapidly with contributions from many disciplines such as operations research, probability and statistics, and economics. A stochastic linear program with recourse can equivalently be formulated as a convex programming problem. The problem is often large-scale as the objective function involves an expectation, either over a discrete set of scenarios or as a multi-dimensional integral. Moreover, the objective function is possibly nondifferentiable. This paper provides a brief overview of approximation techniques and Newton-type methods for solving two-stage stochastic linear programs with recourse, and parallel implementation of these methods. A simple numerical example is used to signal the potential of smoothing approaches.

MSC:

90C15 Stochastic programming
65C60 Computational problems in statistics (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kail, P.; Wallace, S. W., Stochastic Programming (1994), John Wiley & Sons
[2] Beals, E. M.L, On minimizing a convex function subject to linear inequalities, J. Roy. Stat. Soc., B17, 173-184 (1955) · Zbl 0068.13701
[3] Dantzig, G. B., Linear programming under uncertainty, Management Sci., l, 197-206 (1955) · Zbl 0995.90589
[4] Chen, X., A parallel BFGS-SQP method for stochastic linear programs, (May, R. L.; Easton, A. K., Computational Techniques and Applications (1995), World Scientific), 67-74
[5] Rockafellar, R. T.; Wets, R. J.-B, A Lagrangian finite-generation technique for solving linear-quadratic problems in stochastic programming, Math. Prog. Study, 28, 63-93 (1986) · Zbl 0599.90090
[6] Rockafellar, R. T.; Wets, R. J.-B, Linear-quadratic problems with stochastic penalties: The finite generation algorithm, (Arkin, V. I.; Shiraev, A.; Wets, R. J.-B, Stochastic Optimization, Lecture Notes in Control and Information Sciences, 81 (1987), Springer-Verlag: Springer-Verlag Berlin), 545-560 · Zbl 0661.90065
[7] Chen, X.; Qi, L.; Womersley, R. S., Newton’s method for quadratic stochastic programs with recourse, J. Comp. Appl. Math., 60, 29-46 (1995) · Zbl 0836.65078
[8] Chen, X.; Womersley, R. S., A parallel inexact Newton method for stochastic programs with recourse, Annals Oper. Res., 64, 113-141 (1996) · Zbl 0854.90106
[9] Qi, L.; Womersley, R. S., An SQP algorithm for extended linear quadratic problems in stochastic programming, Annals. Oper. Res., 56, 251-285 (1995) · Zbl 0835.90058
[10] Sun, J.; Wee, K.-E; Zhu, J.-S, An interior point method for solving a class of linear-quadratic stochastic programming problems, (Du, D.-Z; Qi, L.; Womersley, R. S., Recent Advances in Nonsmooth Optimization (1995), World Scientific), 392-404 · Zbl 0939.90011
[11] Zhu, C.; Rockafellar, R. T., Primal-dual projected gradient algorithms for extended linear-quadratic programming, SIAM J. Optim., 3, 751-783 (1993) · Zbl 0788.65069
[12] J.R. Birge, S.M Pollock and L. Qi, A quadratic recourse function for the two-stages stochastic program, In Progress II in Optimization: Contributions from Australasia; J.R. Birge, S.M Pollock and L. Qi, A quadratic recourse function for the two-stages stochastic program, In Progress II in Optimization: Contributions from Australasia · Zbl 0958.90062
[13] Fletcher, R., Practical Methods of Optimization (1987), John Wiley & Sons · Zbl 0905.65002
[14] Chen, X., Convergence of the BFGS method for \(LC^1\) convex constrained optimization, SIAM J. Control Optim., 34, 2051-2063 (1996) · Zbl 0871.90062
[15] Facchinei, F., Minimization of \(SC^1\) functions and the Maratos effect, Oper. Res. Lett., 17, 131-137 (1995) · Zbl 0843.90108
[16] Pang, J. S.; Qi, L., A globally convergent Newton method for convex \(SC^1\) minimization problems, J. Optim. Theory Appl., 85, 633-648 (1995) · Zbl 0831.90095
[17] Qi, L., Superlinear convergent approximate Newton methods for \(LC^1\) optimization problems, Math. Programming, 64, 277-294 (1994) · Zbl 0820.90102
[18] X. Chen and R.S. Womersley, Random test problems and parallel methods for quadratic programs and quadratic stochastic programs, Optim. Methods Software; X. Chen and R.S. Womersley, Random test problems and parallel methods for quadratic programs and quadratic stochastic programs, Optim. Methods Software · Zbl 0980.90060
[19] Jessup, E. R.; Yang, D.; Zenios, S. A., Parallel factorization of structured matrices arising in stochastic programming, SIAM J. Optim., 4, 833-846 (1994) · Zbl 0813.65063
[20] Ruszczyński, A., Parallel decomposition of multistage stochastic programming problems, Math. Programming, 58, 201-228 (1993) · Zbl 0777.90036
[21] Birge, J. R.; Louveaux, F. V., (Introduction to Stochastic Programming, Lecture Note (1995), Department of Industrial and Operations Engineering, The University of Michigan)
[22] Tseng, C.-H, Two-stage stochastic programming with recourse, (Master of Mathematics Thesis (1996), University of New South Wales)
[23] Birge, J. R., Decomposition and partitioning methods for multistage stochastic linear programs, Oper. Res., 33, 989-1007 (1985) · Zbl 0581.90065
[24] Mulvey, J. M., Financial planning via multi-stage stochastic optimization, Statistics and Operations Research Technical Report SOR, Princeton University, 94-09 (1994)
[25] Womersley, R. S.; Lau, K., Portfolio optimization problems, (May, R. L.; Easton, A. K., Computational Techniques and Applications (1995), World Scientific), 795-802 · Zbl 0910.90012
[26] Birge, J. R.; Chen, X.; Qi, L., A stochastic method for stochastic quadratic programs with recourse, (AMR, School of Mathematics, UNSW, Sydney, 94/9 (1994))
[27] Higle, J. L.; Sen, S., Stochastic decomposition: An algorithm for two-stage linear programs with recourse, Math. Oper. Res., 16, 650-669 (1991) · Zbl 0746.90045
[28] Birge, J. R.; Wets, R. J.-B, Designing approximation schemes for stochastic optimization problems, in particular, for stochastic programs with recourse, Math. Prog. Study, 27, 54-102 (1986) · Zbl 0603.90104
[29] Mulvey, J. M.; Vladinirou, H., Stochastic network programming for financial planning problems, Management Sci., 38, 1642-1664 (1992) · Zbl 0825.90062
[30] Nazareth, L.; Wets, R. J.-B, Nonlinear programming techniques applied to stochastic programs with recourse, (Ermoliev, Y.; Wets, R. J.-B, Numerical Techniques in Stochastic Programming (1988), Springer-Verlag: Springer-Verlag Berlin), 95-119 · Zbl 0665.90066
[31] Robinson, S. M.; Wets, R. J.-B, Stability in two-stage stochastic programming, SIAM J. Control. Optim., 25, 1409-1416 (1987) · Zbl 0639.90074
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.