Abstract

In Variational Analysis, VU\mathcal{VU}-theory provides a set of tools that is helpful for understanding and exploiting the structure of nonsmooth functions. The theory takes advantage of the fact that at any point, the space can be separated into two orthogonal subspaces: one that describes the direction of nonsmoothness of the function, and the other on which the function behaves smoothly and has a gradient. For a composite function, this work establishes a chain rule that facilitates the computation of such gradients and characterizes the smooth subspace under reasonable conditions. From the chain rule presented, formulae for the separation, smooth perturbation and sum of functions are provided. Several nonsmooth examples are explored, including norm functions, max-of-quadratic functions and LASSO-type regularizations.

Author information

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

Warren Hare

Dept. of Mathematics, University of British Columbia, Okanagan, Kelowna, Canada

warren.hare@ubc.ca

Chayne Planiden

Dept. of Mathematics and Applied Statistics, University of Wollongong, New South Wales, Australia

chayne@uow.edu.au

Keywords

  • Chain rule
  • fast track
  • finite-max function
  • manifold
  • nonsmooth analysis
  • partly smooth function
  • primal-dual gradient
  • strong transversality
  • U-Lagrangian
  • VU-algorithm
  • VU-decomposition

Mathematics Subject Classification

58C05, 90C47; 49A52, 65K10, 90C25

References

  1. Z. Akbari, R. Yousefpour, M. Reza Peyghami: A new nonsmooth trust region algorithm for locally Lipschitz unconstrained optimization problems, J. Optim. Theory Appl. 164(3) (2015) 733–754.https://doi.org/10.1007/s10957-014-0534-6Google Scholar
  2. J. Bello Cruz, A. Iusem: A strongly convergent method for nonsmooth convex minimization in Hilbert spaces, Numer. Funct. Anal. Optim. 32(10) (2011) 1009–1018.https://doi.org/10.1080/01630563.2011.590914Google Scholar
  3. A. Belloni, C. Sagastizábal: Dynamic bundle methods, Math. Program. Ser. A 120(2) (2009) 289–311.https://doi.org/10.1007/s10107-008-0215-zGoogle Scholar
  4. 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. Learn. 3(1) (2011) 1–122.https://doi.org/10.1561/2200000016Google Scholar
  5. J. Burke, A. Lewis, M. Overton: A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim. 15(3) (2005) 751–779.https://doi.org/10.1137/030601296Google Scholar
  6. J. Burke, J. Moré: On the identification of active constraints, SIAM J. Num. Anal. 25(5) (1988) 1197–1211.https://doi.org/10.1137/0725068Google Scholar
  7. P. Calamai, J. Moré: Projected gradient methods for linearly constrained problems, Math. Program. 39(1) (1987) 93–116.https://doi.org/10.1007/BF02592073Google Scholar
  8. X. Chen: Smoothing methods for nonsmooth, nonconvex minimization, Math. Program. Ser. B 134(1) (2012) 71–99.https://doi.org/10.1007/s10107-012-0569-0Google Scholar
  9. A. Conn, N. Gould, P. Toint: Trust-Region Methods, MPS/SIAM Series on Optimization, Philadelphia (2000).https://doi.org/10.1137/1.9780898719857Google Scholar
  10. R. de Sampaio, J. Yuan, W. Sun: Trust region algorithm for nonsmooth optimization, Appl. Math. Comput. 85(2-3) (1997) 109–116.https://doi.org/10.1016/S0096-3003(96)00112-9Google Scholar
  11. J. Dunn: On the convergence of projected gradient processes to singular critical points, J. Optim. Theory Appl. 55(2) (1987) 203–216.https://doi.org/10.1007/BF00939081Google Scholar
  12. J. Eckstein, D. Bertsekas: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program. 55(1-3) (1992) 293–318.https://doi.org/10.1007/BF01581204Google Scholar
  13. S. Flåm: On finite convergence and constraint identification of subgradient projection methods, Math. Program. 57(1) (1992) 427–437.https://doi.org/10.1007/BF01581092Google Scholar
  14. W. Hare: Functions and sets of smooth substructure: relationships and examples, Comput. Optim. Appl. 33(2-3) (2006) 249–270.https://doi.org/10.1007/s10589-005-3059-4Google Scholar
  15. W. Hare: Numerical analysis of VU-decomposition, U-gradient, and U-Hessian approximations, SIAM J. Optim. 24(4) (2014) 1890–1913.https://doi.org/10.1137/130933691Google Scholar
  16. W. Hare, A. Lewis: Identifying active manifolds, Alg. Oper. Res. 2(2) (2007) 75.Google Scholar
  17. W. Hare, C. Planiden: Computing proximal points of convex functions with inexact subgradients, Set-Valued Var. Anal. 26(3) (2018) 469–492.https://doi.org/10.1007/s11228-016-0394-3Google Scholar
  18. W. Hare, C. Planiden, C. Sagastizábal: A derivative-free VU-algorithm for convex finite-max functions, preprint, arXiv:1903.11184 (2019).https://doi.org/10.1080/10556788.2019.1668944Google Scholar
  19. W. Hare, C. Sagastizábal: A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim. 20(5) (2010) 2442–2473.https://doi.org/10.1137/090754595Google Scholar
  20. W. Hare, C. Sagastizábal, M. Solodov: A proximal bundle method for nonsmooth nonconvex functions with inexact information, Comput. Optim. Appl. 63(1) (2016) 1–28.https://doi.org/10.1007/s10589-015-9762-4Google Scholar
  21. L. Hou, W. Sun: On the global convergence of a nonmonotone proximal bundle method for convex nonsmooth minimization, Optim. Methods Softw. 23(2) (2008) 227–235.https://doi.org/10.1080/10556780701549960Google Scholar
  22. N. Karmitsa, A. Bagirov, M. Mäkelä: Comparing different nonsmooth minimization methods and software, Optim. Methods Softw. 27(1) (2012) 131–153.https://doi.org/10.1080/10556788.2010.526116Google Scholar
  23. K. Kiwiel: Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics 1133, Springer, Berlin (1985).https://doi.org/10.1007/BFb0074500Google Scholar
  24. C. Lemaréchal, F. Oustry, C. Sagastizábal: The U -Lagrangian of a convex function, Trans. Amer. Math. Soc. 352(2) (2000) 711–729.https://doi.org/10.1090/S0002-9947-99-02243-6Google Scholar
  25. C. Lemaréchal, C. Sagastizábal: Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries, SIAM J. Optim. 7(2) (1997) 367–385.https://doi.org/10.1137/S1052623494267127Google Scholar
  26. A. Lewis: Active sets, nonsmoothness, and sensitivity, SIAM J. Optim. 13(3) (2002) 702–725.https://doi.org/10.1137/S1052623401387623Google Scholar
  27. Sh. Liu, C. Sagastizábal: Beyond first order: VU-decomposition methods, in: Special Methods for Nonsmooth Optimization, Springer, Cham (2018).Google Scholar
  28. S. Min, L. Jing: A linearly convergent conjugate gradient method for unconstrained optimization problems, Acta Math. Vietnam. 36(3) (2011) 611–622.Google Scholar
  29. J. Martínez, A. Moretti: A trust region method for minimization of nonsmooth functions with linear constraints, Math. Program. Ser. B 76(3) (1997) 431–449.https://doi.org/10.1007/BF02614392Google Scholar
  30. R. Mifflin, C. Sagastizábal: VU-decomposition derivatives for convex max-functions, in: Ill-Posed Variational Problems and Regularization Techniques, Trier 1998, Lecture Notes Econ. Math. Systems 477, Springer, Berlin (1999) 167–186.https://doi.org/10.1007/978-3-642-45780-7_11Google Scholar
  31. R. Mifflin, C. Sagastizábal: Functions with primal-dual gradient structure and U-Hessians, in: Nonlinear Optimization and Related Topics, Erice 1998, Applied Optimization 36, Kluwer Academic Publishers, Dordrecht (2000) 219–233.https://doi.org/10.1007/978-1-4757-3226-9_12Google Scholar
  32. R. Mifflin, C. Sagastizábal: On VU-theory for functions with primal-dual gradient structure, SIAM J. Optim. 11(2) (2000) 547–571 (electronic).https://doi.org/10.1137/S1052623499350967Google Scholar
  33. R. Mifflin, C. Sagastizábal: Proximal points are on the fast track, J. Convex Analysis 9(2) (2002) 563–579.https://doi.org/10.68381/jca09033Google Scholar
  34. R. Mifflin, C. Sagastizábal: Primal-dual gradient structured functions: second-order results; links to epi-derivatives and partly smooth functions, SIAM J. Optim. 13(4) (2003) 1174–1194.https://doi.org/10.1137/S1052623402412441Google Scholar
  35. R. Mifflin, C. Sagastizábal: VU-smoothness and proximal point results for some nonconvex functions, Optim. Methods Softw. 19(5) (2004) 463–478.https://doi.org/10.1080/10556780410001704902Google Scholar
  36. R. Mifflin, C. Sagastizábal: A VU-algorithm for convex minimization, Math. Program. Ser. B 104(2-3) (2005) 583–608.https://doi.org/10.1007/s10107-005-0630-3Google Scholar
  37. Y. Nesterov: Smooth minimization of non-smooth functions, Math. Program. Ser. A 103(1) (2005) 127–152.https://doi.org/10.1007/s10107-004-0552-5Google Scholar
  38. M. Overton: Large-scale optimization of eigenvalues, SIAM J. Optim. 2(1) (1992) 88–120.https://doi.org/10.1137/0802007Google Scholar
  39. R. Rockafellar, R. Wets: Variational Analysis, Grundlehren der Mathematischen Wissenschaften, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  40. C. Sagastizábal: A VU point of view of nonsmooth optimization, in: Proceedings of the International Congress of Mathematicians 2018 - Invited Lectures, volume 3 (2018) 3785–3806.https://doi.org/10.1142/9789813272880_0201Google Scholar
  41. A. Shapiro: On a class of nonsmooth composite functions, Math. Oper. Res. 28(4) (2003) 677–692.https://doi.org/10.1287/moor.28.4.677.20512Google Scholar
  42. M. Teboulle: A simplified view of first order methods for optimization, Math. Program. 170(1) (2018) 67–96.https://doi.org/10.1007/s10107-018-1284-2Google Scholar
  43. B. Wen, X. Chen, T. Pong: Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems, SIAM J. Optim. 27(1) (2017) 124–145.https://doi.org/10.1137/16M1055323Google Scholar
  44. J. Wilkinson: The algebraic eigenvalue problem, Clarendon Press, Oxford (1965).Google Scholar
  45. J. Xiao, M. Ng, Y. Yang: On the convergence of nonconvex minimization methods for image recovery, IEEE Trans. Image Process. 24(5) (2015) 1587–1598.https://doi.org/10.1109/TIP.2015.2401430Google Scholar

Suggested citation

W. Hare, C. Planiden, C. Sagastizábal. “The Chain Rule for VU-Decompositions of Nonsmooth Functions.” Journal of Convex Analysis 27 (2020), No. 1, 335–360. https://doi.org/10.68381/jca27019

Download BibTeXPublished by Heldermann Verlag.

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