Abstract

A hypodifferential is a compact family of affine mappings that defines a local max-type approximation of a nonsmooth convex function. We present a general theory of hypodifferentials of nonsmooth convex functions defined on a Banach space. In particular, we provide complete characterizations of hypodifferentiability and hypodifferentials of nonsmooth convex functions, derive calculus rules for hypodifferentials, and study the Lipschitz continuity/Lipschitz approximation property of hypodifferentials that can be viewed as a natural extension of the Lipschitz continuity of the gradient to the general nonsmooth setting. As an application of our theoretical results we study the rate of convergence of several versions of the method of hypodifferential descent for nonsmooth convex optimization and present an accelerated version of this method having the faster rate of convergence O(1/k2)\mathcal{O}(1/k^2).

Author information

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

Maksim V. Dolgopolik

Institute for Problems in Mechanical Engineering, Russian Academy of Sciences, Saint
Petersburg, Russia

dmv@ipme.ru

Keywords

  • Hypodifferential
  • subdifferential
  • convex analysis
  • convex optimization
  • nonsmooth optimization
  • first-order method

Mathematics Subject Classification

90C25, 90C56, 68Q25

References

  1. 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. Optim. 33/1 (2023) 89–115.https://doi.org/10.1137/21M1465445Google Scholar
  2. A. Barbero, J. López, J. R. Dorronsoro: An accelerated MDM algorithm for SVM training, in: Advances in Computational Intelligence and Learning, Proc. of the ESANN 2008 conference (2008) 421–426.Google Scholar
  3. J. Bolte, T. P. Nguyen, J. Peypouquet, B. W. Suter: From error bounds to the complexity of first-order descent methods for convex functions, Math. Program. 165 (2017) 471–507.https://doi.org/10.1007/s10107-016-1091-6Google Scholar
  4. J. F. Bonnnans, A. Shapiro: Perturbation Analysis of Optimization Problems, Springer, New York (2000).https://doi.org/10.1007/978-1-4612-1394-9Google Scholar
  5. S. Bubeck: Convex optimization: algorithms and complexity, Found. Trends Mach. Learn. 8/3-4 (2015) 231–357.https://doi.org/10.1561/2200000050Google Scholar
  6. M. Danilova, P. Dvurechensky, A. Gasnikov, E. Gorbunov, S. Guminov, D. Kamzolov, I. Shibaev: Recent theoretical advances in non-convex optimization, in: High-Dimensional Optimization and Probability, A. Nikeghbali et al. (eds.), Springer, Cham (2022) 79–163.https://doi.org/10.1007/978-3-031-00832-0_3Google Scholar
  7. V. F. Demyanov; Continuous generalized gradients for nonsmooth functions, in: Optimization, Parallel Processing and Applications, A. Kurzhanski et al. (eds.), Springer, Berlin (1988) 24–27.https://doi.org/10.1007/978-3-642-46631-1_3Google Scholar
  8. V. F. Demyanov: On codifferentiable functions, Vestn. Leningr. Univ. Math. 2 (1988) 22–26.Google Scholar
  9. V. F. Demyanov: Smoothness of nonsmooth functions, in: Nonsmooth Optimization and Related Topics, F. H. Clarke et al. (eds.), Springer, Boston (1989) 79–88.https://doi.org/10.1007/978-1-4757-6019-4_6Google Scholar
  10. V. F. Demyanov, A. M. Rubinov: Constructive Nonsmooth Analysis, Peter Lang, Frankfurt (1995).Google Scholar
  11. V. F. Demyanov, A. M. Rubinov (eds.): Quasidifferentiability and Related Topics, Kluwer, Dordrecht (2000),https://doi.org/10.1007/978-1-4757-3137-8Google Scholar
  12. V. F. Demyanov, G. E. Stavroulakis, L. N. Polyakova, P. D. Panagiotopoulos: Quasidifferentiability and Nonsmooth Modelling in Mechanics, Engineering and Economics, Kluwer, Dordrecht (1996).https://doi.org/10.1007/978-1-4615-4113-4Google Scholar
  13. V. F. Demyanov, G. Sh. Tamasyan: Exact penalty functions in isoperimetric problems, Optim. 60 (2011) 153–177.https://doi.org/10.1080/02331934.2010.534166Google Scholar
  14. V. F. Demyanov, G. Sh. Tamasyan: Direct methods in the parametric moving boundary variational problem, Numer. Funct. Anal. Optim. 35 (2014) 932–961.https://doi.org/10.1080/01630563.2014.922097Google Scholar
  15. M. V. Dolgopolik: Codifferential calculus in normed spaces, J. Math. Sci. 173 (2011) 441–462.https://doi.org/10.1007/s10958-011-0259-0Google Scholar
  16. M. Dolgopolik: Nonsmooth problems of calculus of variations via codifferentiation, ESAIM Control Optim. Calc. Var. 20/4 (2014) 1153–1180.https://doi.org/10.1051/cocv/2014010Google Scholar
  17. M. V. Dolgopolik: A convergence analysis of the method of codifferential descent, Comput. Optim. Appl. 71 (2018) 879–913.https://doi.org/10.1007/s10589-018-0024-0Google Scholar
  18. M. V. Dolgopolik: The method of codifferential descent for convex and global piecewise affine optimization, Optim. Methods Software 35/6 (2020) 1191–1222.https://doi.org/10.1080/10556788.2019.1571590Google Scholar
  19. M. V. Dolgopolik: New global optimality conditions for nonsmooth DC optimization problems, J. Glob. Optim. 76 (2020) 25–55.https://doi.org/10.1007/s10898-019-00833-7Google Scholar
  20. M. Dolgopolik: Constrained nonsmooth problems of the calculus of variations, ESAIM Control Optim. Calc. Var. 27 (2021) 1–35.https://doi.org/10.1051/cocv/2021074Google Scholar
  21. M. V. Dolgopolik: An efficient acceleration technique for methods for finding the nearest point in a polytope and computing the distance between two polytopes, arXiv: 2205.04553 (2022).Google Scholar
  22. Y. Drori, A. B. Taylor: Efficient first-order methods for convex minimization: a constructive approach, Math. Program. 184 (2020) 183–220.https://doi.org/10.1007/s10107-019-01410-2Google Scholar
  23. Y. Drori, M. Teboulle: An optimal variant of Kelley’s cutting-plane method, Math. Program. 160 (2016) 321–351.https://doi.org/10.1007/s10107-016-0985-7Google Scholar
  24. P. Dvurechensky, S. Shtern, M. Staudigl: First-order methods for convex optimization, EURO J. Comput. Optim. 9 (2021), art. no. 100015, 27p.https://doi.org/10.1016/j.ejco.2021.100015Google Scholar
  25. I. Ekeland, R. Temam: Convex Analysis and Variational Problems, SIAM, Philadelphia (1999).https://doi.org/10.1137/1.9781611971088Google Scholar
  26. A. V. Fominyh, V. V. Karelin, L. N. Polyakova: Application of the hypodifferential descent method to the problem of constructing an optimal control, Optim. Lett. 12/8 (2018) 1825–1839.https://doi.org/10.1007/s11590-017-1222-xGoogle Scholar
  27. A. V. Fominykh: Method of subdifferential and hypodifferential descent in the problem of constructing an integrally constrained program control, Autom. Remote Control. 78/4 (2017) 608–617.https://doi.org/10.1134/S0005117917040038Google Scholar
  28. R. M. Freund, H. Lu: New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure, Math. Program. 170 (2018) 445–477.https://doi.org/10.1007/s10107-017-1164-1Google Scholar
  29. E. G. Gilbert: An iterative procedure for computing the minimum of a quadratic form on a convex set, SIAM J. Control 4 (1966) 61–80.https://doi.org/10.1137/0304007Google Scholar
  30. G. N. Grapiglia, Y. Nesterov: Accelerated regularized Newton methods for minimizing composite convex functions, SIAM J. Optim. 29/1 (2019) 77–99.https://doi.org/10.1137/17M1142077Google Scholar
  31. A. D. Ioffe, V. M. Tihomirov: Theory of Extremal Problems, North-Holland, Amsterdam (1979).Google Scholar
  32. P. R. Johnstone, P. Mouline: Faster subgradient methods for functions with Hölderian growth, Math. Program. 180 (2020) 417–450.https://doi.org/10.1007/s10107-018-01361-0Google Scholar
  33. D. Kim, J. A. Fessler: Optimized first-order methods for smooth convex minimization, Math. Program. 159 (2016) 81–107.https://doi.org/10.1007/s10107-015-0949-3Google Scholar
  34. D. Kim, J. A. Fessler: Adaptive restart of the optimized gradient method for convex optimization, J. Optim. Theory Appl. 178/1 (2018) 240–263.https://doi.org/10.1007/s10957-018-1287-4Google Scholar
  35. H. Luo, L. Chen: From differential equation solvers to accelerated first-order method for convex optimization, Math. Program. 195 (2022) 735–781.https://doi.org/10.1007/s10107-021-01713-3Google Scholar
  36. Y. Nesterov: A method for unconstrained convex minimization problem with the rate of convergence O(1/k 2), Dokl. Akad. Nauk USSR 269/3 (1983) 543–547.Google Scholar
  37. Y. Nesterov: Introductory Lectures on Convex Optimization. A Basic Course, Kluwer, London (2004).https://doi.org/10.1007/978-1-4419-8853-9Google Scholar
  38. Y. Nesterov: Excessive gap technique in nonsmooth convex minimization, SIAM J. Optim. 16 (2005) 235–249.https://doi.org/10.1137/S1052623403422285Google Scholar
  39. Y. Nesterov: Smooth minimization of non-smooth functions, Math. Program. 103 (2005) 127–152.https://doi.org/10.1007/s10107-004-0552-5Google Scholar
  40. Y. Nesterov: Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009) 221–259.https://doi.org/10.1007/s10107-007-0149-xGoogle Scholar
  41. A. Neumaier: OSGA: a fast subgradient algorithm with optimal complexity, Math. Program. 158 (2016) 1–21.https://doi.org/10.1007/s10107-015-0911-4Google Scholar
  42. J.-P. Penot: Calculus Without Derivatives, Springer, New York (2013).https://doi.org/10.1007/978-1-4614-4538-8Google Scholar
  43. E. Polak: Optimization, Algorithms and Consistent Approximations, Springer, New York (1997).Google Scholar
  44. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  45. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  46. B. Shi, S. S. Du, M. I. Jordan, W. J. Su: Understanding the acceleration phenomenon via high-resolution differential equations, Math. Program. 195 (2022) 79–148.https://doi.org/10.1007/s10107-021-01681-8Google Scholar
  47. N. Z. Shor: Minimization Methods for Nondifferentiable Functions, Springer, Berlin (1985).https://doi.org/10.1007/978-3-642-82118-9Google Scholar
  48. A. B. Taylor, J. M. Hendrickx, F. Glineur: Exact worst-case convergence rates of the proximal gradient method for composite convex minimization, J. Optim. Theory Appl. 178 (2018) 455–476.https://doi.org/10.1007/s10957-018-1298-1Google Scholar
  49. M. Teboulle: A simplified view of first order methods for optimization, Math. Program. 170 (2018) 67–96.https://doi.org/10.1007/s10107-018-1284-2Google Scholar
  50. L. Thibault: Unilateral Variational Analysis in Banach Spaces. Part I: General Theory, World Scientific, Singapore (2023).https://doi.org/10.1142/12797Google Scholar
  51. J.-P. Vial: Strong and weak convexity of sets and functions, Math. Oper. Res. 8/2 (1983) 231–259.https://doi.org/10.1287/moor.8.2.231Google Scholar
  52. P. Wolfe: Finding the nearest point in a polytope, Math. Program. 11 (1976) 128–149.https://doi.org/10.1007/BF01580381Google Scholar
  53. Y. Xu: Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming, SIAM J. Optim. 27/3 (2017) 1459–1484.https://doi.org/10.1137/16M1082305Google Scholar
  54. T. Yang, Q. Lin: RSG: beating subgradient method without smoothness and strong convexity, J. Mach. Learn. Res. 19 (2018) 1–33.Google Scholar
  55. C. Zalinescu: Convex Analysis in General Vector Spaces, World Scientific, Singapore (2002).https://doi.org/10.1142/5021Google Scholar

Suggested citation

M. V. Dolgopolik. “Hypodifferentials of Nonsmooth Convex Functions and their Applications to Nonsmooth Convex Optimization.” Journal of Convex Analysis 32 (2025), No. 4, 1255–1298. https://doi.org/10.68381/jca32066

Download BibTeXPublished by Heldermann Verlag.

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