Convergence Analysis of a Stochastic Progressive Hedging Algorithm for Stochastic Programming
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).
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
