Convergence Analysis of a Stochastic Progressive Hedging Algorithm for Stochastic Programming

  • Zhenguo Mu College of Science, Nanjing University of Posts and Telecommunications
  • Junfeng Yang Nanjing University, China
Keywords: Progressive hedging algorithm, stochastic programming, nonanticipativity, alternating direction method of multipliers

Abstract

Stochastic programming is an approach for solving optimization problems with uncertainty data whose probability distribution is assumed to be known, and progressive hedging algorithm (PHA) is a well-known decomposition method for solving the underlying model. However, the per iteration computation of PHA could be very costly since it solves a large number of subproblems corresponding to all the scenarios. In this paper,  a stochastic variant of PHA is studied. At each iteration, only a small fraction of the scenarios are selected uniformly at random and the corresponding variable components are updated accordingly, while the variable components corresponding to those not selected scenarios are kept untouch. Therefore, the per iteration cost can be controlled freely to achieve very fast iterations. We show that, though the per iteration cost is reduced significantly, the proposed stochastic PHA converges in an ergodic sense at the same sublinear rate as the original PHA.

References

J. BIRGE AND F. LOUVEAUX, Introduction to stochastic programming, Springer Science & Business Media, (2011).

D. GABAY AND B. MERCIER, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers and Mathematics with Applications, 2 (1976), pp. 17–40.

X. GAO, Y. Y. XU, AND S. Z. ZHANG, Randomized primal-dual proximal block coordinate updates, Journal of the Operations Research Society of China, 7(2019), pp. 205--250.

R. GLOWINSKI AND A. MARROCCO, Sur l’approximation, par ´el´ements finis d’ordre un, et la r´esolution, par p´enalisation-dualit´e, d’une classe de probl`emes de Dirichlet non lin´eaires, R.A.I.R.O., R2, 9 (1975), pp. 41–76.

B. HE AND X. YUAN, On the O(1=n) convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Anal., 50 (2012), pp. 700–709.

M. R. HESTENES, Multiplier and gradient methods, J. Optimization Theory Appl., 4 (1969), pp. 303–320.

B. MARTINET, R´egularisation d’in´equations variationnelles par approximations successives, Rev. Franc¸aise Informat. Recherche Op´erationnelle, 4 (1970), pp. 154–158.

M. J. D. POWELL, A method for nonlinear constraints in minimization problems, in Optimization (Sympos., Univ. Keele, Keele, 1968), Academic Press, London, 1969, pp. 283–298.

R. T. ROCKAFELLAR, Monotone operators and the proximal point algorithm, SIAM J. Control Optimization, 14 (1976), pp. 877–898.

R. T. ROCKAFELLAR, Progressive decoupling of linkages in monotone variational inequalities and convex optimization, in Proceedings of the 10th International Conference on Nonlinear Analysis and Convex Analysis (Chitose, Japanm 2017, Yokohama Publishers, Japan).

R. T. ROCKAFELLAR, Progressive decoupling of linkages in optimization and variational inequalities with elicitable convexity or monotonicity, Set-valued and Variational Analysis, 27(2019), pp.863--893.

R. T. ROCKAFELLAR, Solving stochastic programming problems with risk measures by progressive hedging, Set-Valued and Variational Analysis, 26 (2018), pp. 759–768.

R. T. ROCKAFELLAR AND J. SUN, Solving monotone stochastic variational inequalities and complementarity problems by progressive headging, Mathematical Programming, Series B,174(2019), pp. 453--471.

R. T. ROCKAFELLAR AND S. URYASEV, Minimizing buffered probability of exceedance by progressive hedging, Mathematical Programming, series B, 181(2020) pp.453--472.

R. T. ROCKAFELLAR AND R. J.-B. WETS, Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res., 16 (1991), pp. 119–147.

R. T. ROCKAFELLAR AND R. J.-B. WETS, Stochastic variaitional inequalities: single-stage to multistage, Math. Program., 165 (2017), pp. 331–360.

A. SHAPIRO, D. DENTCHEVA, AND A. RUSZCZY´N SKI, Lectures on stochastic programming, vol. 9 of MOS-SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, second ed., 2014. Modeling and theory.

A. SHAPIRO AND A. PHILPOTT, A tutorial on stochastic programming, Introductory Lecture Notes, (2007).

Published
2020-08-06
How to Cite
Mu, Z., & Yang, J. (2020). Convergence Analysis of a Stochastic Progressive Hedging Algorithm for Stochastic Programming. Statistics, Optimization & Information Computing, 8(3), 656-667. https://doi.org/10.19139/soic-2310-5070-964
Section
Research Articles