Article Contents
Article Contents

# A new interpretation of the progressive hedging algorithm for multistage stochastic minimization problems

• * Corresponding author: Min Zhang
• The progressive hedging algorithm of Rockafellar and Wets for multistage stochastic programming problems could be viewed as a two-block alternating direction method of multipliers. This correspondence brings in some useful results. In particular, it provides a new proof for the convergence of the progressive hedging algorithm with a flexibility in the selection of primal and dual step lengths and it helps to develop a new progressive hedging algorithm for solving risk averse stochastic optimization problems with cross constraints.

Mathematics Subject Classification: 65K10, 65K15, 90C15.

 Citation:

•  [1] M. Ang, J. Sun and Q. Yao, On the dual representation of coherent risk measures, Ann. Oper. Res., 262 (2018), 29-46.  doi: 10.1007/s10479-017-2441-3. [2] M. Fazel, T. K. Pong, D. Sun and P. Tseng, Hankel matrix rank minimization with applications to system identification and realization, SIAM J. Matrix Anal. Appl., 34 (2013), 946-977.  doi: 10.1137/110853996. [3] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1. [4] J. J. Moreau, Proximité et dualité dans un espace Hilbertien, Bull. Soc. Math. de France, 93 (1975), 273-299. [5] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056. [6] R. T. Rockafellar, Solving stochastic programming problems with risk measures by progressive hedging, Set-Valued Var. Anal., 26 (2018), 759-768.  doi: 10.1007/s11228-017-0437-4. [7] R. T. Rockafellar, Progressive decoupling of linkages in monotone variational inequalities and convex optimization, in Proceedings of the Conference on Nonlinear Analysis and Convex Analysis, Chitose, Japan, (2017). [8] R. T. Rockafellar and J. Sun, Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging, Math. Program., (2018). doi: 10.1007/s10107-018-1251-y. [9] R. T. Rockafellar and R. J. B. Wets, Scenario and policy aggregation in optimization under uncertainty, Math. Oper. Res., 16 (1991), 119-147.  doi: 10.1287/moor.16.1.119. [10] R. T. Rockafellar and R. J. B. Wets, Stochastic variational inequalities: Single-stage to multistage, Math. Program., 135 (2016), 331-360.  doi: 10.1007/s10107-016-0995-5. [11] J. E. Spingarn, Applications of the method of partial inverses to convex programming: decomposition, Math. Program., 32 (1985), 199-223.  doi: 10.1007/BF01586091. [12] J. Sun, X. M. Yang, Q. Yao and M. Zhang, Risk minimization, regret minimization and progressive hedging algorithms, work in process.