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

Jie Sun; Honglei Xu; Min Zhang

doi:10.3934/jimo.2019022

Article Contents

2020, Volume 16, Issue 4: 1655-1662. Doi: 10.3934/jimo.2019022

This issue Previous Article Model selection based on value-at-risk backtesting approach for GARCH-Type models Next Article Minimizing almost smooth control variation in nonlinear optimal control problems

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

1.
School of Electric Engineering, Computing, and Mathematical Science, Curtin University, Australia
2.
School of Business, National University of Singapore
3.
School of Electric Engineering, Computing, and Mathematical Science, Curtin University, Australia

^* Corresponding author: Min Zhang
^* Corresponding author: Min Zhang

Received: August 2018

Early access: March 2019

Published: May 2020

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[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.