Abstract

For convex multistage programming problems, we propose a variant for the Progressive Hedging algorithm inspired from bundle methods. Like in the original algorithm, iterates are generated by first solving separate problems for each scenario, and then performing a projective step to ensure non-anticipativity. An additional test checks the quality of the approximation, splitting iterates into two subsequences, akin to the dichotomy between bundle serious and null steps. The method is shown to converge in both cases, and the convergence rate is linear for the serious subsequence. Our bundle-like approach endows the Progressive Hedging algorithm with an implementable stopping test. Moreover, it is possible to vary the augmentation parameter along iterations without impairing convergence. Such enhancements with respect to the original Progressive Hedging algorithm are obtained at the expense of the solution of additional subproblems at each iteration, one per scenario.

Author information

Contact details are reproduced from the original publication and may be historical.

Keywords

  • Bundle methods
  • progressive Hedging algorithm
  • projective descent schemes
  • Douglas-Rachford splitting

Mathematics Subject Classification

90C30, 90C33, 90C55, 65K05

References

  1. W. van Ackooij, V. Berge, W. de Oliveira, C. Sagastizábal: Probabilistic optimization via approximate p-efficient points and bundle methods, Comp. Oper. Res. 77 (2017) 177–193.https://doi.org/10.1016/j.cor.2016.08.002Google Scholar
  2. W. van Ackooij, C. Sagastizábal: Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems, SIAM J. Optimization 24/2 (2014) 733–765.https://doi.org/10.1137/120903099Google Scholar
  3. P. Apkarian, D. Noll, A. Rondepierre: Mixed H2/H∞ control via nonsmooth optimization, SIAM J. Optimization Control 47/3 (2008) 1516–1546.https://doi.org/10.1137/070685026Google Scholar
  4. F. Atenas, C. Sagastizábal, P. J. S. Silva, M. Solodov: A unified analysis of descent sequences in weakly convex optimization, including convergence rates for bundle methods, SIAM J. Optimization 33/1 (2023) 89–115.https://doi.org/10.1137/21M1465445Google Scholar
  5. H. Attouch, J. Bolte, B. F. Svaiter: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Programming 137/1-2 (2013) 91–129.https://doi.org/10.1007/s10107-011-0484-9Google Scholar
  6. J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal: Numerical Optimization: Theoretical and Practical Aspects, 2nd ed., Springer, Berlin (2006).Google Scholar
  7. P. L. Combettes, J. Eckstein: Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions, Math. Programming 126/1-2 (2018) 645–672.https://doi.org/10.1007/s10107-016-1044-0Google Scholar
  8. D. Drusvyatskiy, A. D. Ioffe, A. S. Lewis: Nonsmooth optimization using Taylor-like models: Error bounds, convergence, and termination criteria, Math. Programming 185/1 (2021) 357–383.https://doi.org/10.1007/s10107-019-01432-wGoogle Scholar
  9. J. Eckstein: Splitting Methods for Monotone Operators, with Applications To Parallel Optimization, PhD Thesis, MIT, Cambridge (1989).Google Scholar
  10. J. Eckstein: A simplified form of block-iterative operator splitting and an asynchronous algorithm resembling the multi-block alternating direction method of multipliers, J. Optimization Theory Appl. 173/1 (2017) 155–182.https://doi.org/10.1007/s10957-017-1074-7Google Scholar
  11. J. Eckstein, B. F. Svaiter: A family of projective splitting methods for the sum of two maximal monotone operators, Math. Programming 111/1-2 (2008) 173–199.https://doi.org/10.1007/s10107-006-0070-8Google Scholar
  12. J. Eckstein, B. F. Svaiter: General projective splitting methods for sums of maximal monotone operators, SIAM J. Control Optimization 48/2 (2009) 787–811.https://doi.org/10.1137/070698816Google Scholar
  13. J. Eckstein, J.-P. Watson, D. L. Woodruff: Projective hedging for stochastic programming, Optimization Online, published 2022-05-06 (2022), 39p.Google Scholar
  14. B. Gilles, Y. Laguel, D. Grishchenko, F. Iutzeler, J. Malick: Randomized progressive hedging methods for multi-stage stochastic programming, Ann. Oper. Res. 295/2 (2020) 535–560.https://doi.org/10.1007/s10479-020-03811-5Google Scholar
  15. R. E. C. Gonçalves, E. C. Finardi, E. L. da Silva: Applying different decomposition schemes using the progressive hedging algorithm to the operation planning problem of a hydrothermal system, Electric Power Syst. Res. 83/1 (2012) 19–27.https://doi.org/10.1016/j.epsr.2011.09.006Google Scholar
  16. W. Hare, C. Sagastizábal: Computing proximal points of nonconvex functions, Math. Programming 116/1-2 (2009) 221–258.https://doi.org/10.1007/s10107-007-0124-6Google Scholar
  17. W. Hare, C. Sagastizábal: A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optimization 20/5 (2010) 2442–2473.https://doi.org/10.1137/090754595Google Scholar
  18. J. B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms I, II, Grundlehren der mathematischen Wissenschaften Band 305 und 306, Springer, Berlin (1996).Google Scholar
  19. A. Izmailov, M.Solodov: Optimization: Computational Methods (Portuguese), 3rd ed., IMPA, Rio de Janeiro (2018).Google Scholar
  20. E. Karas, A. Ribeiro, C. Sagastizábal, M. V. Solodov: A bundle-filter method for nonsmooth convex constrained optimization, Math. Programming B 116/1-2 (2009) 297–320.https://doi.org/10.1007/s10107-007-0123-7Google Scholar
  21. B. Knueven, D. T. Mildebrath, C. Muir, J. D. Siirola, J.-P. Watson, D. L. Woodruff: A parallel hub-and-spoke system for large-scale scenario-based optimization under uncertainty, Optimization Online, published 2022-09-09 (2022), 30 p.Google Scholar
  22. G. Li, T. K. Pong: Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods, Found. Comp. Math. 18/5 (2018) 1199–1232.https://doi.org/10.1007/s10208-017-9366-8Google Scholar
  23. P. L. Lions, B. Mercier: Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Analysis 16/6 (1979) 964–979.https://doi.org/10.1137/0716071Google Scholar
  24. P. L. Lions, B. Mercier: Augmented Lagrangian methods for the solution of variational problems, in: Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, R. Glowinski et al. (eds.), Society for Industrial and Applied Mathematics, Philadelphia (1989) 45–121.https://doi.org/10.1137/1.9781611970838.ch3Google Scholar
  25. Z.-Q. Luo, P. Tseng: Error bounds and convergence analysis of feasible descent methods: a general approach, Ann. Oper. Res. 46/1 (1993) 157–178.https://doi.org/10.1007/BF02096261Google Scholar
  26. R. Mifflin: Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optimization 15/6 (1977) 959–972.https://doi.org/10.1137/0315061Google Scholar
  27. V. I. Norkin: Generalized-differentiable functions, Cybernetics 16/1 (1980) 10–12.https://doi.org/10.1007/BF01099354Google Scholar
  28. W. de Oliveira, C. Sagastizábal: Bundle methods in the XXIst century: a bird’s-eye view, Pesquisa Operacional 34/3 (2014) 647–670.https://doi.org/10.1590/0101-7438.2014.034.03.0647Google Scholar
  29. S. M. Robinson: Linear convergence of epsilon-subgradient descent methods for a class of convex functions, Math. Programming 86/1 (1999) 41–50.https://doi.org/10.1007/s101070050078Google Scholar
  30. R. T. Rockafellar: Solving stochastic programming problems with risk measures by progressive hedging, Set-Valued Var. Analysis 26/4 (2018) 759–768.https://doi.org/10.1007/s11228-017-0437-4Google Scholar
  31. R. T. Rockafellar, R. J.-B. Wets: Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res. 16/1 (1991) 119–147.https://doi.org/10.1287/moor.16.1.119Google Scholar
  32. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Grundlehren der mathematischen Wissenschaften Band 317, Springer, Berlin (2009).Google Scholar
  33. C. Sagastizábal: Divide to conquer: decomposition methods for energy optimization, Math. Programming 134/1 (2012) 187–222.https://doi.org/10.1007/s10107-012-0570-7Google Scholar
  34. C. Sagastizábal: Composite proximal bundle method, Math. Programming 140/1 (2013) 189–233.https://doi.org/10.1007/s10107-012-0600-5Google Scholar
  35. C. Sagastizábal, M. V. Solodov: An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter, SIAM J. Optimization 16/1 (2005) 146–169.https://doi.org/10.1137/040603875Google Scholar
  36. M. L. L. dos Santos, E. Luiz da Silva, E. C. Finardi, R. E. C. Gonçalves: Practical aspects in solving the medium-term operation planning problem of hydrothermal power systems by using the progressive hedging method, Int. J. Electrical Power Energy Syst. 31/9 (2009) 546–552.https://doi.org/10.1016/j.ijepes.2009.03.032Google Scholar
  37. P. Tseng: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J. Control Optimization 29/1 (1991) 119–138.https://doi.org/10.1137/0329006Google Scholar
  38. J. J. Ye, X. Yuan, S. Zeng, J. Zhang: Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems, Set-Valued Var. Analysis 29/4 (2021) 803–837.https://doi.org/10.1007/s11228-021-00591-3Google Scholar

Suggested citation

F. Atenas, C. Sagastizábal. “A Bundle-Like Progressive Hedging Algorithm.” Journal of Convex Analysis 30 (2023), No. 2, 453–479. https://doi.org/10.68381/jca30027

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2023. Rights now held by Banach Press LLC.