×

Computation of the epsilon-subdifferential of convex piecewise linear-quadratic functions in optimal worst-case time. (English) Zbl 07115099

Summary: The epsilon-subdifferential of convex univariate piecewise linear-quadratic (PLQ) functions can be computed in linear worst-case time complexity as the level-set of a convex function. Using binary search, we improve the complexity to logarithmic worst-case time, and prove such complexity is optimal. In addition, a new algorithm to compute the entire graph of the epsilon-subdifferential in (optimal) linear time is presented. Both algorithms are not limited to convex PLQ functions but are also applicable to any convex piecewise-defined functions with little restrictions.

MSC:

65K10 Numerical optimization and variational techniques

Software:

na13; CCA ; SCAT; fenchel; na24
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Bajaj, A., Hare, W., Lucet, Y.: Visualization of the \(đťś–\)-subdifferential of piecewise linear-quadratic functions, Comput. Optim. Appl. Accepted for publication (2016) · Zbl 1406.90092
[2] Bauschke, H.H., Combettes, P.L.: Convex analysis and monotone operator theory in Hilbert spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 2nd edn. Springer, Cham (2017). With a foreword by Hédy Attouch
[3] Bauschke, HH; Goebel, R.; Lucet, Y.; Wang, X., The proximal average: Basic theory, SIAM J. Optim., 19, 768-785, (2008) · Zbl 1172.26003
[4] Bauschke, H.H., Moffat, S.M., Wang, X.: Self-dual smooth approximations of convex functions via the proximal average. In: Bauschke, H. H., Burachik, R. S., Combettes, P. L., Elser, V., Luke, D. R., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering, vol. 49 of Springer Optimization and Its Applications, pp. 23-32. Springer, New York (2011) · Zbl 1250.26015
[5] Bauschke, HH; Mohrenschildt, Mv, Symbolic computation of Fenchel conjugates, ACM Commun. Comput. Algebra, 40, 18-28, (2006) · Zbl 1369.68356
[6] Borwein, J.M., Hamilton, C.H.: Symbolic computation of multidimensional Fenchel conjugates. In: ISSAC 2006, pp. 23-30. ACM, New York (2006) · Zbl 1356.68270
[7] Borwein, JM, Symbolic Fenchel conjugation, Math. Program., 116, 17-35, (2008) · Zbl 1158.90007
[8] Brøndsted, A.; Rockafellar, RT, On the subdifferentiability of convex functions, Proc. Amer. Math. Soc., 16, 605-611, (1965) · Zbl 0141.11801
[9] Contento, L.; Ern, A.; Vermiglio, R., A linear-time approximate convex envelope algorithm using the double Legendre-Fenchel transform with application to phase separation, Comput. Optim. Appl., 60, 231-261, (2015) · Zbl 1320.90079
[10] Gardiner, B., Lucet, Y.: Graph-matrix calculus for computational convex analysis. In: Bauschke, H. H., Burachik, R. S., Combettes, P. L., Elser, V., Luke, D. R., Wolkowicz, H. (eds.) Fixed-point Algorithms for Inverse Problems in Science and Engineering, vol. 49 of Springer Optimization and Its Applications, pp. 243-259. Springer, New York (2011)
[11] Goebel, R., The proximal average for saddle functions and its symmetry properties with respect to partial and saddle conjugacy, J. Nonlinear Convex Anal., 11, 1-11, (2010) · Zbl 1190.26006
[12] Goebel, R.; Hare, W.; Wang, X., The optimal value and optimal solutions of the proximal average of convex functions, Nonlinear Anal. Theory Methods Appl., 75, 1290-1304, (2012) · Zbl 1254.90165
[13] Hare, W., A proximal average for nonconvex functions: A proximal stability perspective, SIAM J. Optim., 20, 650-666, (2009) · Zbl 1206.26019
[14] Hiriart-Urruty, J.-B.: From convex optimization to nonconvex optimization. Necessary and sufficient conditions for global optimality. In: Nonsmooth Optimization and Related Topics (Erice, 1988), vol. 43 of Ettore Majorana Internat. Sci. Ser. Phys. Sci., pp. 219-239. Plenum, New York (1989) · Zbl 0735.90056
[15] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I, vol. 305 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin (1993). Vol I: Fundamentals
[16] Hiriart-Urruty, J.-B.: Convex Analysis and Minimization Algorithms II, vol. 306 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin (1993). Vol II: Advanced theory and bundle methods
[17] Hiriart-Urruty, J-B; Lucet, Y., Parametric computation of the Legendre-Fenchel conjugate, J. Convex Anal., 14, 657-666, (2007)
[18] Ioffe, AD, Approximate subdifferentials and applications. I. The finite-dimensional theory, Trans. Amer. Math Soc., 281, 389-416, (1984) · Zbl 0531.49014
[19] Johnstone, J.; Koch, V.; Lucet, Y., Convexity of the proximal average, J. Optim. Theory Appl., 148, 107-124, (2011) · Zbl 1215.26010
[20] Lucet, Y., A fast computational algorithm for the Legendre-Fenchel transform, Comput. Optim. Appl., 6, 27-57, (1996) · Zbl 0852.90117
[21] Lucet, Y.: Computational Convex Analysis library, 1996-2013 · Zbl 0852.90117
[22] Lucet, Y., Faster than the fast legendre transform, the linear-time legendre transform, Numer. Algorithms, 16, 171-185, (1997) · Zbl 0909.65037
[23] Lucet, Y., Fast Moreau envelope computation I: Numerical algorithms, Numer. Algorithms, 43, 235-249, (2006) · Zbl 1116.65027
[24] Lucet, Y., What shape is your conjugate? A survey of computational convex analysis and its applications, SIAM Rev., 52, 505-542, (2010) · Zbl 1197.65072
[25] Lucet, Y.: Techniques and open questions in computational convex analysis. In: Computational and Analytical Mathematics, vol. 50 of Springer Proc. Math. Stat., pp. 485-500. Springer, New York (2013) · Zbl 1286.90111
[26] Lucet, Y.; Bauschke, HH; Trienis, M., The piecewise linear-quadratic model for computational convex analysis, Comput. Optim. Appl., 43, 95-118, (2009) · Zbl 1186.90089
[27] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer-Verlag, Berlin (1998) · Zbl 0888.49001
[28] Trienis, M.: Computational convex analysis: From continuous deformation to finite convex integration, Master’s thesis, University of British Columbia (2007)
[29] Tseng, P.; Luo, Z-Q, On computing the nested sums and infimal convolutions of convex piecewise-linear functions, J. Algorithms, 21, 240-266, (1996) · Zbl 0857.68051
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.