July  2020, 16(4): 1655-1662. doi: 10.3934/jimo.2019022

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

Received  August 2018 Published  March 2019

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.

Citation: Jie Sun, Honglei Xu, Min Zhang. A new interpretation of the progressive hedging algorithm for multistage stochastic minimization problems. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1655-1662. doi: 10.3934/jimo.2019022
References:
[1]

M. AngJ. 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.  Google Scholar

[2]

M. FazelT. K. PongD. 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.  Google Scholar

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

[4]

J. J. Moreau, Proximité et dualité dans un espace Hilbertien, Bull. Soc. Math. de France, 93 (1975), 273-299.   Google Scholar

[5]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.  Google Scholar

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

[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). Google Scholar

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

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

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

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

[12]

J. Sun, X. M. Yang, Q. Yao and M. Zhang, Risk minimization, regret minimization and progressive hedging algorithms, work in process. Google Scholar

show all references

References:
[1]

M. AngJ. 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.  Google Scholar

[2]

M. FazelT. K. PongD. 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.  Google Scholar

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

[4]

J. J. Moreau, Proximité et dualité dans un espace Hilbertien, Bull. Soc. Math. de France, 93 (1975), 273-299.   Google Scholar

[5]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.  Google Scholar

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

[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). Google Scholar

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

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

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

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

[12]

J. Sun, X. M. Yang, Q. Yao and M. Zhang, Risk minimization, regret minimization and progressive hedging algorithms, work in process. Google Scholar

[1]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170

[2]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048

[3]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[4]

Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020323

[5]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264

[6]

Anna Canale, Francesco Pappalardo, Ciro Tarantino. Weighted multipolar Hardy inequalities and evolution problems with Kolmogorov operators perturbed by singular potentials. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020274

[7]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

[8]

Xuhui Peng, Rangrang Zhang. Approximations of stochastic 3D tamed Navier-Stokes equations. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5337-5365. doi: 10.3934/cpaa.2020241

[9]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[10]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[11]

Reza Chaharpashlou, Abdon Atangana, Reza Saadati. On the fuzzy stability results for fractional stochastic Volterra integral equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020432

[12]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

[13]

Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080

[14]

Pengyu Chen. Non-autonomous stochastic evolution equations with nonlinear noise and nonlocal conditions governed by noncompact evolution families. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020383

[15]

Lin Shi, Xuemin Wang, Dingshi Li. Limiting behavior of non-autonomous stochastic reaction-diffusion equations with colored noise on unbounded thin domains. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5367-5386. doi: 10.3934/cpaa.2020242

[16]

Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468

[17]

Andrew D. Lewis. Erratum for "nonholonomic and constrained variational mechanics". Journal of Geometric Mechanics, 2020, 12 (4) : 671-675. doi: 10.3934/jgm.2020033

[18]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[19]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020271

[20]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (340)
  • HTML views (1028)
  • Cited by (1)

Other articles
by authors

[Back to Top]