Abstract

We propose and study the weak convergence of a projective splitting algorithm studied by A. Alotaibi, P. Combettes, and N. Shahzad [Solving coupled composite monotone inclusions by successive Fejér approximations of their Kuhn-Tucker set, SIAM J. Optim. 24/4 (2014) 2076–2095] and by J. Eckstein and B. F. Svaiter [A family of projective splitting methods for the sum of two maximal monotone operators, Math. Programming Ser. B 111/1-2 (2008) 173–199] for solving multi-term composite monotone inclusion problems involving the finite sum of n maximal monotone operators, each of which having an inner four-block structure: sum of maximal monotone, Lipschitz continuous, cocoercive and smooth differentiable operators. We show how to perform backward and half-forward steps [see L. M. Briceno Arias and D. Davis [Forward-backward-half forward algorithm for solving monotone inclusions, SIAM J. Optim. 28/4 (2018) 2839–2871] with respect to the maximal monotone and Lipschitz + cocoercive components, respectively, while performing proximal-Newton steps with respect to smooth differentiable blocks.

Author information

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

Maicon Marques Alves

Departamento de Matemática, Universidade Federal de Santa Catarina, Florianópolis, Brazil

maicon.alves@ufsc.br

Keywords

  • Projective splitting algorithm
  • monotone inclusions
  • operator-splitting
  • proximal-Newton algorithm

Mathematics Subject Classification

47H05, 49M27, 47N10

References

  1. M. A. Alghamdi, A. Alotaibi, P. L. Combettes, N. Shahzad: A primal-dual method of partial inverses for composite inclusions, Optim. Letters 8/8 (2014) 2271–2284.https://doi.org/10.1007/s11590-014-0734-xGoogle Scholar
  2. A. Alotaibi, P. L. Combettes, N. Shahzad: Solving coupled composite monotone inclusions by successive Fejér approximations of their Kuhn-Tucker set, SIAM J. Optim. 24/4 (2014) 2076–2095.https://doi.org/10.1137/130950616Google Scholar
  3. A. Alotaibi, P. L. Combettes, N. Shahzad: Best approximation from the Kuhn-Tucker set of composite monotone inclusions, Numer. Funct. Analysis Optim. 36/12 (2015) 1513–1532.https://doi.org/10.1080/01630563.2015.1077864Google Scholar
  4. M. M. Alves: Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods, Optim. Methods Software 37/6 (2022) 2021–2051.https://doi.org/10.1080/10556788.2021.2022148Google Scholar
  5. M. M. Alves, M. Geremia, R. T. Marcavillaca: A relative-error inertial-relaxed inexact projective splitting algorithm, J. Convex Analysis 31/1 (2024) 1–24.https://doi.org/10.68381/jca31001Google Scholar
  6. M. M. Alves, R. T. Marcavillaca: On inexact relative-error hybrid proximal extragradient, forward-backward and Tseng’s modified forward-backward methods with inertial effects, Set-Valued Var. Analysis 28/2 (2020) 301–325.https://doi.org/10.1007/s11228-019-00510-7Google Scholar
  7. H. Attouch, M. M. Alves, B. F. Svaiter: A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity O(1/n2), J. Convex Analysis 23/1 (2016) 139–180.https://doi.org/10.68381/jca23006Google Scholar
  8. H. Attouch, A. Cabot: Convergence of a relaxed inertial proximal algorithm for maximally monotone operators, Math. Programming Ser. A 184/1-2 (2020) 243–287.https://doi.org/10.1007/s10107-019-01412-0Google Scholar
  9. H. Attouch, A. Cabot, Z. Chbani, H. Riahi: Inertial forward-backward algorithms with perturbations: application to Tikhonov regularization, J. Optim. Theory Appl. 179/1 (2018) 1–36.https://doi.org/10.1007/s10957-018-1369-3Google Scholar
  10. H. Attouch, J. Peypouquet: Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators, Math. Programming Ser. B 174/1-2 (2019) 391–432.https://doi.org/10.1007/s10107-018-1252-xGoogle Scholar
  11. F. Bach: Self-concordant analysis for logistic regression, Electron. J. Stat. 4 (2010) 384–414.https://doi.org/10.1214/09-EJS521Google Scholar
  12. M. Barré, A. Taylor, F. Bach: A note on approximate accelerated forward-backward methods with absolute and relative errors, and possibly strongly convex objectives., Open J. Math. Optim. 3 (2022), art. no. 1, 15p.https://doi.org/10.5802/ojmo.12Google Scholar
  13. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics, Springer, New York (2011).https://doi.org/10.1007/978-1-4419-9467-7Google Scholar
  14. H. H. Bauschke, W. M. Moursi: On the behavior of the Douglas-Rachford algorithm for minimizing a convex function subject to a linear constraint, SIAM J. Optim. 30/3 (2020) 2559–2576.https://doi.org/10.1137/19M1281538Google Scholar
  15. A. Beck, M. Teboulle: A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2/1 (2009) 183–202.https://doi.org/10.1137/080716542Google Scholar
  16. R. I. Boţ, E. R. Csetnek: ADMM for monotone operators: convergence analysis and rates, Adv. Comput. Math. 45/1 (2019) 327–359.https://doi.org/10.1007/s10444-018-9619-3Google Scholar
  17. S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein: Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learning 3/1 (2011) 1–122.https://doi.org/10.1561/2200000016Google Scholar
  18. L. M. Briceño Arias, D. Davis: Forward-backward-half forward algorithm for solving monotone inclusions, SIAM J. Optim. 28/4 (2018) 2839–2871.https://doi.org/10.1137/17M1120099Google Scholar
  19. M. N. Bùi, P. L. Combettes: Warped proximal iterations for monotone inclusions, J. Math. Analysis Appl. 491/1 (2020), art. no. 124315, 21p.https://doi.org/10.1016/j.jmaa.2020.124315Google Scholar
  20. M. N. Bùi, P. L. Combettes: Multivariate monotone inclusions in saddle form, Math. Oper. Res. 47/2 (2022) 1082–1109.https://doi.org/10.1287/moor.2021.1161Google Scholar
  21. B. Bullins, K. A. Lai: Higher-order methods for convex-concave min-max optimization and monotone variational inequalities, SIAM J. Optim. 32/3 (2022) 2208–2229.https://doi.org/10.1137/21M1395764Google Scholar
  22. L. Chen, X. Li, D. Sun, K.-C. Toh: On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming, Math. Programming Ser. A.185/1-2 (2021) 111–161.https://doi.org/10.1007/s10107-019-01423-xGoogle Scholar
  23. P. L. Combettes, J. Eckstein: Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions, Math. Programming Ser. B 168/1-2 (2018) 645–672.https://doi.org/10.1007/s10107-016-1044-0Google Scholar
  24. P. L. Combettes, Q. V. Nguyen: Solving composite monotone inclusions in reflexive Banach spaces by constructing best Bregman approximations from their Kuhn-Tucker set, J. Convex Analysis 23/2 (2016) 481–510.https://doi.org/10.68381/jca23018Google Scholar
  25. P. L. Combettes, J.-C. Pesquet: Proximal splitting methods in signal processing, in: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, H. H. Bauschke et al. (eds.), Springer Optimization and its Applications 49, Springer, New York (2011) 185–212.https://doi.org/10.1007/978-1-4419-9569-8_10Google Scholar
  26. L. Condat: A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl. 158/2 (2013) 460–479.https://doi.org/10.1007/s10957-012-0245-9Google Scholar
  27. D. Davis, W. Yin: A three-operator splitting scheme and its optimization applications, Set-Valued Var. Analysis 25/4 (2017) 829–858.https://doi.org/10.1007/s11228-017-0421-zGoogle Scholar
  28. J. E. Dennis Jr., R. B. Schnabel: Numerical Methods for Unconstrained Optimization and Nonlinear Equations, corrected reprint of the 1983 original, Classics in Applied Mathematics 16, Society for Industrial and Applied Mathematics, Philadelphia (1996).https://doi.org/10.1137/1.9781611971200Google Scholar
  29. J. Eckstein, D. P. Bertsekas: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Programming 55/3 (1992) 293–318.https://doi.org/10.1007/BF01581204Google Scholar
  30. J. Eckstein, B. F. Svaiter: A family of projective splitting methods for the sum of two maximal monotone operators, Math. Programming Ser. B 111/1-2 (2008) 173–199.https://doi.org/10.1007/s10107-006-0070-8Google Scholar
  31. J. Eckstein, B. F. Svaiter: General projective splitting methods for sums of maximal monotone operators, SIAM J. Control Optim. 48/2 (2009) 787–811.https://doi.org/10.1137/070698816Google Scholar
  32. P. Giselsson: Nonlinear forward-backward splitting with projection correction, SIAM J. Optim. 31/3 (2021) 2199–2226.https://doi.org/10.1137/20M1345062Google Scholar
  33. R. Glowinski, S. J. Osher, W. Yin (eds.): Splitting Methods in Communication, Imaging, Science, and Engineering, Scientific Computation, Springer, Cham (2016).https://doi.org/10.1007/978-3-319-41589-5Google Scholar
  34. W. W. Hager, H. Zhang: Convergence rates for an inexact ADMM applied to separable convex optimization, Comput. Optim. Appl. 77/3 (2020) 729–754.https://doi.org/10.1007/s10589-020-00221-yGoogle Scholar
  35. B. He, X. Yuan: On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Analysis 50/2 (2020) 700–709.https://doi.org/10.1137/110836936Google Scholar
  36. R. Jiang, A. Mokhtari: Generalized optimistic methods for convex-concave saddle point problems, arXiv: 2202.09674 (2022).Google Scholar
  37. P. R. Johnstone, J. Eckstein: Convergence rates for projective splitting, SIAM J. Optim. 29/3 (2019) 1931–1957.https://doi.org/10.1137/18M1203523Google Scholar
  38. P. R. Johnstone, J. Eckstein: Single-forward-step projective splitting: exploiting cocoercivity, Comput. Optim. Appl. 78/1 (2021) 125–166.https://doi.org/10.1007/s10589-020-00238-3Google Scholar
  39. P. R. Johnstone, J. Eckstein: Projective splitting with forward steps, Math. Programming Ser. A 191/2 (2022) 631–670.https://doi.org/10.1007/s10107-020-01565-3Google Scholar
  40. P. Johnstone, J. Eckstein, T. Flynn, S. Yoo: Stochastic projective splitting, Comput. Optim. Appl. 87/4 (2024) 397–437.https://doi.org/10.1007/s10589-023-00528-6Google Scholar
  41. A. Lenoir, P. Mahey: A survey on operator splitting and decomposition of convex programs, RAIRO Oper. Res. 51/1 (2017) 17–41.https://doi.org/10.1051/ro/2015065Google Scholar
  42. T. Lin, M. I. Jordan: A control-theoretic perspective on optimal high-order optimization, Math. Programming Ser. A 195/1-2 (2022) 929–975.https://doi.org/10.1007/s10107-021-01721-3Google Scholar
  43. T. Lin, M. I. Jordan: Monotone inclusions, acceleration, and closed-loop control, Math. Oper. Res. 48/4 (2023) 2353–2382.https://doi.org/10.1287/moor.2022.1343Google Scholar
  44. T. Lin, M. I. Jordan: Perseus: A simple and optimal high-order method for variational inequalities, Math. Programming Ser. A 209/1-2 (2025) 609–650.https://doi.org/10.1007/s10107-024-02075-2Google Scholar
  45. 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
  46. D. A. Lorenz, T. Pock: An inertial forward-backward algorithm for monotone inclusions, J. Math. Imaging Vision 51/2 (2015) 311–325.https://doi.org/10.1007/s10851-014-0523-2Google Scholar
  47. D. A. Lorenz, Q. Tran-Dinh: Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence, Comput. Optim. Appl. 74/1 (2019) 67–92.https://doi.org/10.1007/s10589-019-00106-9Google Scholar
  48. U. Marteau-Ferey, F. Bach, A. Rudi: Globally convergent newton methods for ill-conditioned generalized self-concordant losses, Advances in Neural Information Processing Systems (NeurIPS) (2019).Google Scholar
  49. R. D. C. Monteiro, B. F. Svaiter: On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean, SIAM J. Optim. 20/6 (2010) 2755–2787.https://doi.org/10.1137/090753127Google Scholar
  50. R. D. C. Monteiro, B. F. Svaiter: Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems, SIAM J. Optim. 22/3 (2012) 914–935.https://doi.org/10.1137/11083085XGoogle Scholar
  51. R. D. C. Monteiro, B. F. Svaiter: Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers, SIAM J. Optim. 23/1 (2013) 475–507.https://doi.org/10.1137/110849468Google Scholar
  52. Y. Nesterov: Lectures on Convex Optimization, 2nd ed., Springer Optimization and Its Applications 137, Springer, Cham (2018).https://doi.org/10.1007/978-3-319-91578-4_2Google Scholar
  53. G. B. Passty: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Analysis Appl. 72/2 (1979) 383–390.https://doi.org/10.1016/0022-247X(79)90234-8Google Scholar
  54. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  55. R. T. Rockafellar: On the maximality of sums of nonlinear monotone operators, Trans. Amer. Math. Soc. 149 (1970) 75–88.https://doi.org/10.1090/S0002-9947-1970-0282272-5Google Scholar
  56. E. Ryu, W. Yin: Large-Scale Convex Optimization: Algorithms and Analyses via Monotone Operators, Cambridge University Press, Cambridge (2023).https://doi.org/10.1017/9781009160865Google Scholar
  57. S. Salzo, S. Villa: Inexact and accelerated proximal point algorithms, J. Convex Analysis 19/4 (2012) 1167–1192.https://doi.org/10.68381/jca19062Google Scholar
  58. S. Salzo, S. Villa: Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis, Math. Programming Ser. A 193/1 (2022) 225–269.https://doi.org/10.1007/s10107-020-01602-1Google Scholar
  59. P. Tseng: A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim. 38/2 (2000) 431–446 (electronic).https://doi.org/10.1137/S0363012998338806Google Scholar

Suggested citation

M. M. Alves. “Projective Splitting with Backward, Half-Forward and Proximal-Newton Steps.” Journal of Convex Analysis 32 (2025), No. 4, 1199–1226. https://doi.org/10.68381/jca32063

Download BibTeXPublished by Heldermann Verlag.

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