Approximate scenario solutions in the progressive hedging algorithm. A numerical study with an application to fisheries management. (English) Zbl 0739.90047

This paper focuses on a time-discrete controllable process in time stages \(t=0,1,\dots,T\). The state of the process at time \(t\) is denoted by the variable \(x_ t\). The transition from the state at time \(t\) to that at time \(t+1\) is governed by a control variable \(u_ t\) but is also dependent on an auxiliary variable, the scenario \(s^ t\). The scenarios can be illustrated with a tree structure, the scenario tree. Thus we can describe the transition as follows: \(x_{t+1}=G_ t(x_ t,u_ t,s^ t)\). Probabilities are attached to the scenarios.
To solve a stochastic optimal control problem the so-called ‘progressive hedging algorithm’ developed by R. T. Rockafellar and R. J.-B. Wets [Math. Oper. Res. 16, No. 1, 119-147 (1991; Zbl 0729.90067)] is specialized. The paper describes how the scenario aggregation principle can be combined with approximate solutions of the individual scenario problems, resulting in a computationally efficient algorithm where two individual Lagrangian-based procedures are merged into one.
Computational results are given for an example from fisheries management. Numerical experiments indicate that only crude scenario solutions are needed.
Reviewer: L.Paditz (Dresden)


90C15 Stochastic programming
91B76 Environmental economics (natural resource models, harvesting, pollution, etc.)
93E20 Optimal stochastic control
93C95 Application models in control theory
90C90 Applications of mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
93C55 Discrete-time control/observation systems
49L20 Dynamic programming in optimal control and differential games


Zbl 0729.90067
Full Text: DOI


[1] J.R. Birge, Decomposition and partitioning methods for multistage stochastic linear programs, Oper. Res. 33 (1985) 989–1007. · Zbl 0581.90065
[2] H. Gassmann, Multi-period stochastic programming, Ph.D. Thesis, University of British Columbia, Vancouver, Canada (1987).
[3] M.R. Hestenes. Multiplier and gradient methods. J. Opt. Theory Appl. 4 (1969) 303–320. · Zbl 0174.20705
[4] F. Louveaux, A solution method for multi-stage stochastic programs with recourse with applications to an energy investment problem. Oper. Res. 28 (1980) 889–902. · Zbl 0441.90076
[5] F. Louveaux, Multistage stochastic programs with block-separable recourse, Math. Progr. Study 28 (1986) 48–62. · Zbl 0593.90059
[6] J. Mulvey and H. Vladimirou, Solving multistage stochastic networks: An application of scenario analysis. Report SOR-88-1, Dept. of Civil Engineering and Operations Research. Princeton University (1988). · Zbl 0743.90053
[7] P. Olsen, Multistage stochastic program with recourse: The equivalent deterministic problem. SIAM J. Control Optim. 14 (1976) 518–527. · Zbl 0336.90040
[8] D.A. Pierre and M.J. Lowe,Mathematical Programming Via Augmented Lagrangians: An Introduction with Computer Programs. Applied Mathematics and Computation 9 (Addison-Wesley, Reading, 1975). · Zbl 0347.90048
[9] M.J.D. Powell, A method for nonlinear constraints in minimization problems, in:Optimization, ed. R. Fletcher (Academic Press, New York, 1969) pp. 283–298. · Zbl 0194.47701
[10] R.T. Rockafellar and R.J.-B. Wets, The principle of scenario aggregation in optimization under uncertainty, Working paper WP-87-119, IIASA. Austria (1987), to appear in Math. Oper. Res.
[11] M.B. Schaefer, Some aspects of the dynamics of populations important to to the management of the commercial marine fisheries, Inter-Am. Trop. Tuna Comm. Bull. 1 (1954) 27–56.
[12] R. Van Slyke and R.J.-B. Wets, L-shaped linear programs with applications to optimal control and stochastic programming, SIAM J. Appl. Math. 17 (1969) 638–663. · Zbl 0197.45602
[13] S.W. Wallace and T. Helgason, Structural properties of the progressive hedging algorithm, this volume. · Zbl 0743.90085
[14] R.J.-B. Wets, Stochastic programming: Solution techniques and approximation schemes, in:Mathematical Programming. The State of the Art, eds. A. Bachem, M. Grötschel and B. Korte (Springer-Verlag, Berlin, 1983) pp. 566–603.
[15] R.J.-B. Wets, Large scale linear programming techniques, in:Numerical, Techniques in Stochastic Optimization, eds. Y. Ermoliev and R.J.-B. Wets (Springer, Berlin, 1988) pp. 65–94.
[16] R.J.-B. Wets, The aggregation in scenario analysis and stochastic optimization, in:Algorithms and Model Formulations in Mathematical Programming, ed. S.W. Wallace (Springer, Berlin, 1989) pp. 91–113.
[17] R.J.-B. Wets, Stochastic programming, in:Handbooks in Operations Research and Management Science, vol. 1:Optimization, eds. G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (North-Holland, Amsterdam, 1989) pp 573–629.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.