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]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[2]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[3]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065

[4]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[5]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[6]

Seung-Yeal Ha, Dongnam Ko, Chanho Min, Xiongtao Zhang. Emergent collective behaviors of stochastic kuramoto oscillators. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1059-1081. doi: 10.3934/dcdsb.2019208

[7]

María J. Garrido-Atienza, Bohdan Maslowski, Jana  Šnupárková. Semilinear stochastic equations with bilinear fractional noise. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3075-3094. doi: 10.3934/dcdsb.2016088

[8]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[9]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002

[10]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263

[11]

Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175

[12]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004

[13]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[14]

Shihu Li, Wei Liu, Yingchao Xie. Large deviations for stochastic 3D Leray-$ \alpha $ model with fractional dissipation. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2491-2509. doi: 10.3934/cpaa.2019113

[15]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521

[16]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[17]

Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827

[18]

Jean Dolbeault, Maria J. Esteban, Michał Kowalczyk, Michael Loss. Improved interpolation inequalities on the sphere. Discrete & Continuous Dynamical Systems - S, 2014, 7 (4) : 695-724. doi: 10.3934/dcdss.2014.7.695

[19]

Xingchun Wang, Yongjin Wang. Variance-optimal hedging for target volatility options. Journal of Industrial & Management Optimization, 2014, 10 (1) : 207-218. doi: 10.3934/jimo.2014.10.207

[20]

V. V. Zhikov, S. E. Pastukhova. Korn inequalities on thin periodic structures. Networks & Heterogeneous Media, 2009, 4 (1) : 153-175. doi: 10.3934/nhm.2009.4.153

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (422)
  • HTML views (1031)
  • Cited by (1)

Other articles
by authors

[Back to Top]