Computing the conjugate of convex piecewise linear-quadratic bivariate functions. (English) Zbl 1271.90057

Summary: We present a new algorithm to compute the Legendre-Fenchel conjugate of convex piecewise linear-quadratic (PLQ) bivariate functions. The algorithm stores a function using a (primal) planar arrangement. It then computes the (dual) arrangement associated with the conjugate by looping through vertices, edges, and faces in the primal arrangement and building associated dual vertices, edges, and faces. Using optimal computational geometry data structures, the algorithm has a linear time worst-case complexity. We present the algorithm, and illustrate it with numerical examples. We proceed to build a toolbox for convex bivariate PLQ functions by implementing the addition, and scalar multiplication operations. Finally, we compose these operators to compute classical convex analysis operators such as the Moreau envelope, and the proximal average.


90C25 Convex programming
26A51 Convexity of real functions in one variable, generalizations
26B25 Convexity of real functions of several variables, generalizations
47H05 Monotone operators and generalizations


fenchel; CCA ; SCAT; CGAL; na24; na13; Scilab
Full Text: DOI


[1] Bauschke, HH; Goebel, R; Lucet, Y; Wang, X, The proximal average: basic theory, SIAM J. Optim., 19, 768-785, (2008) · Zbl 1172.26003
[2] Bauschke, H.H., Lucet, Y., Trienis, M.: How to transform one convex function continuously into another. SIAM Rev. 50(1), 115-132 (2008). URL: http://link.aip.org/link/?SIR/50/115/1 · Zbl 1145.90050
[3] Bauschke, H.H., Lucet, Y., Wang, X.: Primal-dual symmetric intrinsic methods for finding antiderivatives of cyclically monotone operators. SIAM J. Control Optim. 46(6), 2031-2051 (2007). URL: http://link.aip.org/link/?SJC/46/2031/1 · Zbl 1189.47050
[4] Bauschke, HH; Matoušková, E; Reich, S, Projection and proximal point methods: convergence results and counterexamples, Nonlinear Anal., 56, 715-738, (2004) · Zbl 1059.47060
[5] 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, Springer Optimization and Its Applications, vol. 49, pp. 23-32. Springer, New York (2011). doi:10.1007/978-1-4419-9569-8_2
[6] Bauschke, H.H., Mohrenschildt, M.V.: Symbolic computation of Fenchel conjugates. ACM Commun. Comput. Algebra 40(1), 18-28 (2006). doi:10.1145/1151446.1151453 · Zbl 1369.68356
[7] Borwein, J.M., Hamilton, C.H.: Symbolic Fenchel conjugation. Math. Program. 116(1), 17-35 (2008). doi:10.1007/s10107-007-0134-4 · Zbl 1158.90007
[8] Botelho, F.C., Lacerda, A., Menezes, G.V., Ziviani, N.: Minimal perfect hashing: a competitive method for indexing internal memory. Inf. Sci. 181(13), 2608-2625 (2011). URL: http://www.sciencedirect.com/science/article/pii/S0020025509005271 · Zbl 1172.26003
[9] Brenier, Y, Un algorithme rapide pour le calcul de transformées de Legendre-Fenchel discrètes, C. R. Acad. Sci. Paris Sér. I Math., 308, 587-589, (1989) · Zbl 0667.65006
[10] CGAL, Computational Geometry Algorithms Library. URL: http://www.cgal.org · Zbl 1365.68441
[11] CGLAB a Scilab toolbox for geometry based on CGAL. URL: http://cglab.gforge.inria.fr/
[12] Corrias, L.: Fast Legendre-Fenchel transform and applications to Hamilton-Jacobi equations and conservation laws. SIAM J. Numer. Anal. 33(4), 1534-1558 (1996). URL: http://www.jstor.org/stable/2158316 · Zbl 0856.49023
[13] Czech, Z.J., Havas, G., Majewski, B.S.: Perfect hashing. Theor. Comput. Sci. 182(1-2), 1-143 (1997). URL: http://www.sciencedirect.com/science/article/pii/S0304397596001466 · Zbl 0954.68060
[14] de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry, 3rd edn. Springer, Berlin (2008). URL: http://www.springer.com/computer/theoretical+computer+science/book/978-3-540-77973-5. Algorithms and applications · Zbl 0939.68134
[15] Gardiner, B., Lucet, Y.: Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis. Set-Valued Var. Anal. 18(3-4), 467-482 (2010). doi:10.1007/s11228-010-0157-5 · Zbl 1205.90222
[16] 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, Springer Optimization and Its Applications, vol. 49, pp. 243-259. Springer, New York (2011). doi:10.1007/978-1-4419-9569-8_12
[17] Goebel, R.: Self-dual smoothing of convex and saddle functions. J. Convex Anal. 15(1), 179-190 (2008). URL: http://www.heldermann.de/JCA/JCA15/JCA151/jca15012.htm · Zbl 1142.26010
[18] Goodrich, M.T., Tamassia, R.: Data Structures and Algorithms in Java, 5th edn. Wiley, New York (2010) · Zbl 1059.68022
[19] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 305-306. Springer, Berlin (1993). URL: http://www.springer.com/math/book/978-3-540-56850-6. Vol I: Fundamentals, Vol II: Advanced theory and bundle methods · Zbl 0667.65006
[20] Johnstone, J., Koch, V., Lucet, Y.: Convexity of the proximal average. J. Optim. Theory Appl. 148, 107-124 (2011). doi:10.1007/s10957-010-9747-5 · Zbl 1215.26010
[21] Lucet, Y.: A fast computational algorithm for the Legendre-Fenchel transform. Comput. Optim. Appl. 6(1), 27-57 (1996). URL: http://www.springerlink.com/content/x777265871618672/ · Zbl 0852.90117
[22] Lucet, Y.: Computational Convex Analysis Library (1996-2011). URL: https://people.ok.ubc.ca/ylucet/cca.html
[23] Lucet, Y.: Faster than the Fast Legendre Transform, the Linear-time Legendre Transform. Numer. Algorithms 16(2), 171-185 (1997). URL: http://www.springerlink.com/content/m41t352758814q50/ · Zbl 0909.65037
[24] Lucet, Y.: A linear Euclidean distance transform algorithm based on the Linear-time Legendre Transform. In: Proceedings of the Second Canadian Conference on Computer and Robot Vision (CRV 2005), pp. 262-267. IEEE Computer Society Press, Victoria BC (2005)
[25] Lucet, Y.: Fast Moreau envelope computation I: numerical algorithms. Numer. Algorithms 43(3), 235-249 (2006). doi:10.1007/s11075-006-9056-0. URL: http://www.springerlink.com/content/h80k45x24t1q7426/ · Zbl 1116.65027
[26] Lucet, Y.: What shape is your conjugate? A survey of computational convex analysis and its applications. SIAM Rev. 52(3), 505-542 (2010). doi:10.1137/100788458 · Zbl 1197.65072
[27] Lucet, Y., Bauschke, H.H., Trienis, M.: The piecewise linear-quadratic model for computational convex analysis. Comput. Optim. Appl. 43, 95-118 (2009). URL: http://www.springerlink.com/content/j726881521t4541l/ · Zbl 1186.90089
[28] Moffat, S.M.: On the Kernel Average of n Functions. Master’s thesis, Department of Mathematics, University of British Columbia (2009). URL: http://hdl.handle.net/2429/21932
[29] Moreau, J.J.: Proximité et dualité dans un espace Hilbertien. Bull. Soc. Math. France 93, 273-299 (1965). URL: http://www.numdam.org/item?id=BSMF_1965__93__273_0 · Zbl 0136.12101
[30] Noullez, A., Vergassola, M.: A fast Legendre transform algorithm and applications to the adhesion model. J. Sci. Comput. 9(3), 259-281 (1994). URL: http://www.springerlink.com/content/h8733538m6523g82 · Zbl 0823.76058
[31] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Berlin (1998). URL: http://www.springer.com/math/book/978-3-540-62772-2
[32] Scilab Consortium: Scilab (1994). URL: http://www.scilab.org
[33] She, Z.S., Aurell, E., Frisch, U.: The inviscid Burgers equation with initial data of Brownian type. Commun. Math. Phys. 148(3), 623-641 (1992). URL: http://projecteuclid.org/euclid.cmp/1104251047 · Zbl 0755.60104
[34] Sun, J.: On the structure of convex piecewise quadratic functions. J. Optim. Theory Appl. 72(3), 499-510 (1992). doi:10.1007/BF00939839 · Zbl 0807.90093
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.