Abstract

Based on the needs of convergence proofs of preconditioned proximal point methods, we introduce notions of partial strong submonotonicity and partial (metric) subregularity of set-valued maps. We study relationships between these two concepts, neither of which is generally weaker or stronger than the other one. For our algorithmic purposes, the novel submonotonicity turns out to be easier to employ than more conventional error bounds obtained from subregularity. Using strong submonotonicity, we demonstrate the linear convergence of the Primal-Dual Proximal Splitting method to some strictly complementary solutions of example problems from image processing and data science. This is without the conventional assumption that all the objective functions of the involved saddle point problem are strongly convex.

Author information

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

Tuomo Valkonen

Dept. of Mathematics and Statistics, University of Helsinki, Finland
and: ModeMat, Escuela Politécnica Nacional, Quito, Ecuador
and: Department of Mathematical Sciences, University of Liverpool, United Kingdom

tuomo.valkonen@iki.fi

Keywords

  • Subregularity
  • submonotonicity
  • error bounds
  • partial
  • proximal point method

Mathematics Subject Classification

49J52, 47H05, 49M05, 49M29

References

  1. S. Adly, R. Cibulka, H. V. Ngai: Newton’s method for solving inclusions using set-valued approximations, SIAM J. Optimization 25 (2015) 159–184.https://doi.org/10.1137/130926730Google Scholar
  2. F. J. Aragón Artacho, M. Gaydu: A Lyusternik-Graves theorem for the proximal point method, Comp. Optimization Appl. 52 (2012) 785–803.https://doi.org/10.1007/s10589-011-9439-6Google Scholar
  3. F. J. Aragón Artacho, M. H. Geoffroy: Characterization of metric regularity of subdifferentials, J. Convex Analysis 15 (2008) 365–380.https://doi.org/10.68381/jca15026Google Scholar
  4. F. J. Aragón Artacho, M. H. Geoffroy: Metric subregularity of the convex subdifferential in Banach spaces, J. Nonlinear Convex Analysis 15 (2014) 35–47.Google Scholar
  5. T. Aspelmeier, C. Charitha, D. R. Luke: Local linear convergence of the ADMM/Douglas-Rachford algorithms without strong convexity and application to statistical imaging, SIAM J. Imaging Sciences 9 (2016) 842–868.https://doi.org/10.1137/15M103580XGoogle Scholar
  6. J.-P. Aubin: Lipschitz behavior of solutions to convex minimization problems, Math. Oper. Res. 9 (1984) 87–111.https://doi.org/10.1287/moor.9.1.87Google Scholar
  7. J. Aubin, H. Frankowska: Set-Valued Analysis, Springer, Berlin (1990).Google Scholar
  8. A. Chambolle, T. Pock: A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40 (2011) 120–145.https://doi.org/10.1007/s10851-010-0251-1Google Scholar
  9. N. H. Chieu, G. M. Lee, B. S. Mordukhovich, T. T. A. Nghia: Coderivative characterizations of maximal monotonicity for set-valued mappings, J. Convex Analysis 23 (2016) 461–480.https://doi.org/10.68381/jca23017Google Scholar
  10. R. Cibulka, A. Dontchev, A. Kruger: Strong metric subregularity of mappings in variational analysis and optimization, J Math. Analysis Appl. 457 (2018) 1247–1282.https://doi.org/10.1016/j.jmaa.2016.11.045Google Scholar
  11. C. Clason, T. Valkonen: Stability of saddle points via explicit coderivatives of pointwise subdifferentials, Set-Valued Var. Analysis 25 (2017) 69–112.https://doi.org/10.1007/s11228-016-0366-7Google Scholar
  12. C. Clason, T. Valkonen: Introduction to nonsmooth analysis and optimization, work in progress, arXiv: 2001.00216 (2020).Google Scholar
  13. A. Dontchev, R. Rockafellar: Implicit Functions and Solution Mappings: A View from Variational Analysis, Springer Series in Operations Research and Financial Engineering, Springer, New York (2014).https://doi.org/10.1007/978-1-4939-1037-3Google Scholar
  14. A. L. Dontchev, R. T. Rockafellar: Regularity and conditioning of solution mappings in variational analysis, Set-Valued Var. Analysis 12 (2004) 79–109.https://doi.org/10.1023/B:SVAN.0000023394.19482.30Google Scholar
  15. M. Durea, M. Panţiruc, R. Strugariu: A new type of directional regularity for mappings and applications to optimization, SIAM J. Optimization 27 (2017) 1204–1229.https://doi.org/10.1137/16M1067342Google Scholar
  16. I. Ekeland: On the variational principle, J. Math. Analysis Appl. 47 (1974) 324–353.https://doi.org/10.1016/0022-247X(74)90025-0Google Scholar
  17. E. Esser, X. Zhang, T. F. Chan: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sciences 3 (2010) 1015–1046.https://doi.org/10.1137/09076934XGoogle Scholar
  18. H. Gfrerer: First order and second order characterizations of metric subregularity and calmness of constraint set mappings, SIAM J. Optimization 21 (2011) 1439–1474.https://doi.org/10.1137/100813415Google Scholar
  19. H. Gfrerer: On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs, Set-Valued Var. Analysis 21 (2013) 151–176.https://doi.org/10.1007/s11228-012-0220-5Google Scholar
  20. H. Gfrerer, B. S. Mordukhovich: Robinson stability of parametric constraint systems via variational analysis, SIAM J. Optimization 27 (2017) 438–465.https://doi.org/10.1137/16M1086881Google Scholar
  21. D. Han, X. Yuan: Local linear convergence of the alternating direction method of multipliers for quadratic programs, SIAM J. Num. Analysis 51 (2013) 3446–3457.https://doi.org/10.1137/120886753Google Scholar
  22. B. He, X. Yuan: Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective, SIAM J. Imaging Sciences 5 (2012) 119–149.https://doi.org/10.1137/100814494Google Scholar
  23. R. Henrion, T. Surowiec: On calmness conditions in convex bilevel programming, Appl. Analysis 90 (2011) 951–970.https://doi.org/10.1080/00036811.2010.495339Google Scholar
  24. A. D. Ioffe: Regular points of Lipschitz functions, Trans. Amer. Math. Soc. 251 (1979) 61–69.https://doi.org/10.1090/S0002-9947-1979-0531969-6Google Scholar
  25. A. D. Ioffe: Variational Analysis of Regular Mappings: Theory and Applications, Springer Monographs in Mathematics, Springer, Berlin (2017).https://doi.org/10.1007/978-3-319-64277-2Google Scholar
  26. A. Y. Kruger: Error bounds and metric subregularity, Optimization 64 (2015) 49–79.https://doi.org/10.1080/02331934.2014.938074Google Scholar
  27. D. Leventhal: Metric subregularity and the proximal point method, J. Math. Analysis Appl. 360 (2009) 681–688.https://doi.org/10.1016/j.jmaa.2009.07.012Google Scholar
  28. A. S. Lewis, S. Zhang: Partial smoothness, tilt stability, and generalized hessians, SIAM J. Optimization 23 (2013) 74–94.https://doi.org/10.1137/110852103Google Scholar
  29. G. Li, B. S. Mordukhovich: Hölder metric subregularity with applications to proximal point method, SIAM J. Optimization 22 (2012) 1655–1684.https://doi.org/10.1137/120864660Google Scholar
  30. J. Liang, J. Fadili, G. Peyré: Local linear convergence of forward-backward under partial smoothness, Adv. Neural Information Processing Systems 27 (2014) 1970–1978.Google Scholar
  31. Z.-Q. Luo, P. Tseng: Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem, SIAM J. Optimization 2 (1992) 43–54.https://doi.org/10.1137/0802004Google Scholar
  32. B. Martinet: Brève communication. Régularisation d’inéquations variationnelles par approximations successives, ESAIM: Math. Modelling Numer. Analysis 4 (1970) 154–158.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  33. S. Mazurenko, J. Jauhiainen, T. Valkonen: Primal-dual block-proximal splitting for a class of non-convex problems, arXiv: 1911.06284 (2019).https://doi.org/10.1553/etna_vol52s509Google Scholar
  34. B. S. Mordukhovich: Variational Analysis and Generalized Differentiation. I: Basic Theory, Grundlehren der mathematischen Wissenschaften 330, Springer, Berlin (2006).https://doi.org/10.1007/3-540-31246-3Google Scholar
  35. B. S. Mordukhovich, T. T. A. Nghia: Local monotonicity and full stability for parametric variational systems, SIAM J. Optimization 26 (2016) 1032–1059.https://doi.org/10.1137/15M1036890Google Scholar
  36. H. V. Ngai, M. Théra: Error bounds in metric spaces and application to the perturbation stability of metric regularity, SIAM J. Optimization 19 (2008) 1–20.https://doi.org/10.1137/060675721Google Scholar
  37. H. V. Ngai, M. Théra: Directional metric regularity of multifunctions, Math. Oper. Res. 40 (2015) 969–991.https://doi.org/10.1287/moor.2014.0705Google Scholar
  38. S. M. Robinson: Stability theory for systems of inequalities. II: Differentiable nonlinear systems, SIAM J. Numer. Analysis 13 (1976) 497–513.https://doi.org/10.1137/0713043Google Scholar
  39. S. M. Robinson: Some continuity properties of polyhedral multifunctions, in: Mathematical Programming at Oberwolfach, H. König, B. Korte, K. Ritter (eds), Mathematical Programming Studies 14, Springer, Berlin (1981) 206–214.https://doi.org/10.1007/BFb0120929Google Scholar
  40. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1972).Google Scholar
  41. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Optimization 14 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  42. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  43. T. Valkonen: Testing and non-linear preconditioning of the proximal point method, Appl. Math. Optimization, doi.org/10.1007/s00245-018-9541-6 (2018).https://doi.org/10.1007/s00245-018-9541-6Google Scholar
  44. T. Valkonen: Block-proximal methods with spatially adapted acceleration, Electronic Trans. Numer. Analysis 51 (2019) 15–49.https://doi.org/10.1553/etna_vol51s15Google Scholar
  45. T. Valkonen, T. Pock: Acceleration of the PDHGM on partially strongly convex functions, J. Math. Imaging Vision 59 (2017) 394–414.https://doi.org/10.1007/s10851-016-0692-2Google Scholar
  46. H. Van Ngai, A. Y. Kruger, M. Théra: Slopes of multifunctions and extensions of metric regularity, Vietnam J. Mathematics 40 (2012) 355–369.https://doi.org/10.1007/s10957-013-0385-6Google Scholar
  47. J. J. Ye and D. L. Zhu: Optimality conditions for bilevel programming problems, Optimization 33 (1995) 9–27.https://doi.org/10.1080/02331939508844060Google Scholar
  48. Z. Zhou, A. M.-C. So: A unified approach to error bounds for structured convex optimization problems, Math. Programming 165 (2017) 689–728.https://doi.org/10.1007/s10107-016-1100-9Google Scholar
  49. M. Zhu, T. Chan: An efficient primal-dual hybrid gradient algorithm for total variation image restoration, CAM Report 08-34, UCLA, Los Angeles (2008).Google Scholar

Suggested citation

T. Valkonen. “Preconditioned Proximal Point Methods and Notions of Partial Subregularity.” Journal of Convex Analysis 28 (2021), No. 1, 251–278. https://doi.org/10.68381/jca28017

Download BibTeXPublished by Heldermann Verlag.

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