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, 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]

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems & Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917

[2]

Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2019029

[3]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067

[4]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247

[5]

Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078

[6]

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial & Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037

[7]

Xiaojun Chen, Guihua Lin. CVaR-based formulation and approximation method for stochastic variational inequalities. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 35-48. doi: 10.3934/naco.2011.1.35

[8]

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

[9]

Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645

[10]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317

[11]

Takeshi Fukao, Nobuyuki Kenmochi. Abstract theory of variational inequalities and Lagrange multipliers. Conference Publications, 2013, 2013 (special) : 237-246. doi: 10.3934/proc.2013.2013.237

[12]

Suxiang He, Pan Zhang, Xiao Hu, Rong Hu. A sample average approximation method based on a D-gap function for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 977-987. doi: 10.3934/jimo.2014.10.977

[13]

Rong Hu, Ya-Ping Fang, Nan-Jing Huang. Levitin-Polyak well-posedness for variational inequalities and for optimization problems with variational inequality constraints. Journal of Industrial & Management Optimization, 2010, 6 (3) : 465-481. doi: 10.3934/jimo.2010.6.465

[14]

Roxin Zhang, Bao Truong, Qinghong Zhang. Multistage hierarchical optimization problems with multi-criterion objectives. Journal of Industrial & Management Optimization, 2011, 7 (1) : 103-115. doi: 10.3934/jimo.2011.7.103

[15]

Hongxia Yin. An iterative method for general variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 201-209. doi: 10.3934/jimo.2005.1.201

[16]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020103

[17]

Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215

[18]

Qingzhi Yang. The revisit of a projection algorithm with variable steps for variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 211-217. doi: 10.3934/jimo.2005.1.211

[19]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[20]

Gang Qian, Deren Han, Lingling Xu, Hai Yang. Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities. Journal of Industrial & Management Optimization, 2013, 9 (1) : 255-274. doi: 10.3934/jimo.2013.9.255

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (73)
  • HTML views (517)
  • Cited by (0)

Other articles
by authors

[Back to Top]