Abstract

Introduced in the 1960s, the Moreau envelope has grown to become a key tool in nonsmooth analysis and optimization. Essentially an infimal convolution with a parametrized norm squared, the Moreau envelope is used in many applications and optimization algorithms. An important aspect in applying the Moreau envelope to nonconvex functions is determining if the function is prox-bounded, that is, if there exists a point x and a parameter r such that the Moreau envelope is finite. The infimum of all such r is called the threshold of prox-boundedness (prox-threshold) of the function f. In this paper, we seek to understand the prox-thresholds of piecewise linear-quadratic (PLQ) functions. (A PLQ function is a function whose domain is a union of finitely many polyhedral sets, and that is linear or quadratic on each piece.) The main result provides a computational technique for determining the prox-threshold for a PLQ function, and further analyzes the behavior of the Moreau envelope of the function using the prox-threshold. We provide several examples to illustrate the techniques and challenges.

Author information

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

Warren L. Hare

Dept. of Mathematics, University of British Columbia, Okanagan Campus, 3333 University Way, Kelowna, BC, Canada V1V 1V7

warren.hare@ubc.ca

Chayne Planiden

Dept. of Mathematics, University of British Columbia, Okanagan Campus, 3333 University Way, Kelowna, BC, Canada V1V 1V7

chayneplaniden@hotmail.com

Keywords

  • Moreau Envelope
  • piecewise linear-quadratic
  • PLQ
  • prox-threshold

Mathematics Subject Classification

49J52, 49J53, 49N10

References

  1. H. Bauschke, Y. Lucet, M. Trienis: How to transform one convex function continuously into another, SIAM Rev. 50(1) (2008) 115–132.https://doi.org/10.1137/060664513Google Scholar
  2. A. Beck, M. Teboulle: Smoothing and first order methods: a unified framework, SIAM J. Optim. 22(2) (2012) 557–580.https://doi.org/10.1137/100818327Google Scholar
  3. O. Bretscher: Linear Algebra. With Applications, Prentice-Hall, Upper Saddle River (1997).Google Scholar
  4. J. Chen, S. Pan: A proximal-like algorithm for a class of nonconvex programming, Pac. J. Optim. 4(2) (2008) 319–333.Google Scholar
  5. P. Combettes, D. Dũng, B. Vũ: Proximity for sums of composite functions, J. Math. Anal. Appl. 380(2) (2011) 680–688.https://doi.org/10.1016/j.jmaa.2011.02.079Google Scholar
  6. P. Combettes, J. Pesquet: Proximal thresholding algorithm for minimization over orthonormal bases, SIAM J. Optim. 18(4) (2007) 1351–1376.https://doi.org/10.1137/060669498Google Scholar
  7. R. Dembo, R. Anderson: An efficient linesearch for convex piecewise-linear/ quadratic functions, in: Advances in Numerical Partial Differential Equations and Optimization (Mérida, 1989), S. Gómez et al. (ed.), SIAM, Philadelphia (1991) 1–8.Google Scholar
  8. B. Gardiner, Y. Lucet: Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis, Set-Valued Var. Anal. 18(3–4) (2010) 467–482.https://doi.org/10.1007/s11228-010-0157-5Google Scholar
  9. O. Güler: On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim. 29(2) (1991) 403–419.https://doi.org/10.1137/0329022Google Scholar
  10. W. Hare: A proximal average for nonconvex functions: a proximal stability perspective, SIAM J. Optim. 20(2) (2009) 650–666.https://doi.org/10.1137/07070913XGoogle Scholar
  11. W. Hare, C. Planiden: The NC-proximal average for multiple functions, Optim. Lett. 8(3) (2014) 849–860.https://doi.org/10.1007/s11590-013-0641-6Google Scholar
  12. W. Hare, C. Planiden: Parametrically prox-regular functions, J. Convex Analysis 21(4) (2014) 901–923.https://doi.org/10.68381/jca21049Google Scholar
  13. W. Hare, R. Poliquin: Prox-regularity and stability of the proximal mapping, J. Convex Analysis 14(3) (2007) 589–606.https://doi.org/10.68381/jca14035Google Scholar
  14. W. Hare, C. Sagastizábal: Computing proximal points of nonconvex functions, Math. Program., Ser. B 116(1–2) (2009) 221–258.https://doi.org/10.1007/s10107-007-0124-6Google Scholar
  15. J. Johnstone, V. Koch, Y. Lucet: Convexity of the proximal average, J. Optim. Theory Appl. 148(1) (2011) 107–124.https://doi.org/10.1007/s10957-010-9747-5Google Scholar
  16. A. Jourani, L. Thibault, D. Zagrodny: Differential properties of the Moreau envelope, J. Funct. Anal. 266(3) (2014) 1185–1237.https://doi.org/10.1016/j.jfa.2013.11.008Google Scholar
  17. C. Kan, W. Song: The Moreau envelope function and proximal mapping in the sense of the Bregman distance, Nonlinear Anal. 75(3) (2012) 1385–1399.https://doi.org/10.1016/j.na.2011.07.031Google Scholar
  18. A. Kaplan, R. Tichatschke: Proximal point methods and nonconvex optimization, J. Glob. Optim. 13(4) (1998) 389–406.https://doi.org/10.1023/A:1008321423879Google Scholar
  19. Y. Lucet: Fast Moreau envelope computation. I. Numerical algorithms, Numer. Algorithms 43(3) (2006) 235–249.https://doi.org/10.1007/s11075-006-9056-0Google Scholar
  20. Y. Lucet: What shape is your conjugate? A survey of computational convex analysis and its applications, SIAM Rev. 52(3) (2010) 505–542.https://doi.org/10.1137/100788458Google Scholar
  21. Y. Lucet, H. Bauschke, M. Trienis: The piecewise linear-quadratic model for computational convex analysis, Comput. Optim. Appl. 43(1) (2009) 95–118.https://doi.org/10.1007/s10589-007-9124-yGoogle Scholar
  22. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Franç. Inform. Rech. Opér. 4 (R–3) (1970) 154–158.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  23. J.-J. Moreau: Propriétés des applications “prox”, C. R. Acad. Sci., Paris 256 (1963) 1069–1071.Google Scholar
  24. J.-J. Moreau: Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. Fr. 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  25. R. Poliquin, R. Rockafellar: Generalized Hessian properties of regularized nonsmooth functions, SIAM J. Optim. 6(4)(1996) 1121–1137.https://doi.org/10.1137/S1052623494279316Google Scholar
  26. R. Poliquin, R. Rockafellar: Prox-regular functions in variational analysis, Trans. Amer. Math. Soc. 348(5) (1996) 1805–1838.https://doi.org/10.1090/S0002-9947-96-01544-9Google Scholar
  27. A. Rantzer, M. Johansson: Piecewise linear quadratic optimal control, IEEE Trans. Automat. Control 45(4) (2000) 629–637.https://doi.org/10.1109/9.847100Google Scholar
  28. P. A. Rey, C. Sagastizábal: Dynamical adjustment of the prox-parameter in bundle methods, Optimization 51(2) (2002) 423–447.https://doi.org/10.1080/02331930290019495Google Scholar
  29. R. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14(5) (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  30. R. Rockafellar: On the essential boundedness of solutions to problems in piecewise linear-quadratic optimal control, in: Analyse Mathématique et Applications, Gauthier-Villars, Montrouge (1988) 437–443.Google Scholar
  31. R. Rockafellar, R. Wets: Variational Analysis, Grundlehren der Mathematischen Wissenschaften 317, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  32. W.-Y. Sun, R. J. B. Sampaio, M. A. B. Candido: Proximal point algorithm for minimization of DC function, J. Comput. Math. 21(4) (2003) 451–462.Google Scholar
  33. I. Yamada, M. Yukawa, M. Yamagishi: Minimizing the Moreau envelope of nonsmooth convex functions over the fixed point set of certain quasi-nonexpansive mappings, in: Fixed-Point Algorithms for Inverse Problems in Science and Engineering (Banff, 2009), H. H. Bauschke et al. (ed.), Springer Optim. Appl. 49, Springer, New York (2011) 345–390.https://doi.org/10.1007/978-1-4419-9569-8_17Google Scholar
  34. K. Yosida: Functional Analysis, Grundlehren der Mathematischen Wissenschaften 123, Springer, Berlin (1965).Google Scholar

Suggested citation

W. L. Hare, C. Planiden. “Thresholds of Prox-Boundedness of PLQ Functions.” Journal of Convex Analysis 23 (2016), No. 3, 691–718. https://doi.org/10.68381/jca23027

Download BibTeXPublished by Heldermann Verlag.

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