Skip to main content
SpringerLink
Log in

Computing the conjugate of convex piecewise linear-quadratic bivariate functions

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

References

  1. Bauschke, H.H., Goebel, R., Lucet, Y., Wang, X.: The proximal average: basic theory. SIAM J. Optim. 19(2), 768–785 (2008). doi:10.1137/070687542

    Article  MathSciNet  Google Scholar 

  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

    Google Scholar 

  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

  4. Bauschke, H.H., Matoušková, E., Reich, S.: Projection and proximal point methods: Convergence results and counterexamples. Nonlinear Anal. 56(5), 715–738 (2004). doi:10.1016/j.na.2003.10.010

    Article  MathSciNet  MATH  Google Scholar 

  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

  7. Borwein, J.M., Hamilton, C.H.: Symbolic Fenchel conjugation. Math. Program. 116(1), 17–35 (2008). doi:10.1007/s10107-007-0134-4

  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

  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)

    MathSciNet  MATH  Google Scholar 

  10. CGAL, Computational Geometry Algorithms Library. URL: http://www.cgal.org

  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

  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

  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

  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

  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

    Google Scholar 

  18. Goodrich, M.T., Tamassia, R.: Data Structures and Algorithms in Java, 5th edn. Wiley, New York (2010)

    Google Scholar 

  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

  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

    Google Scholar 

  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/

  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/

  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/

    Google Scholar 

  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

    Google Scholar 

  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/

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  34. Sun, J.: On the structure of convex piecewise quadratic functions. J. Optim. Theory Appl. 72(3), 499–510 (1992). doi:10.1007/BF00939839

    Google Scholar 

Download references

Acknowledgments

The authors would like to thank an anonymous referee for pointing out reference [34], constructive comments that improved the presentation of the algorithm, and pointing a special configuration that resulted in adding Sect. 3.4 to explain the complexity of the algorithm.

Author information

Authors and Affiliations

  1. Computer Science, I. K. Barber School, ASC 350, University of British Columbia Okanagan, Kelowna, BC, V1V 1V7, Canada

    Bryan Gardiner & Yves Lucet

Authors
  1. Bryan Gardiner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yves Lucet
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yves Lucet.

Additional information

Yves Lucet was partially supported by a Discovery grant from the Natural Sciences and Engineering Research Council of Canada (NSERC). Bryan Gardiner was partially supported by an NSERC Undergraduate Student Research Award. Part of the research was done in the Computer-Aided Convex Analysis laboratory funded by the Canadian Foundation for Innovation under a Leaders Opportunity Fund.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gardiner, B., Lucet, Y. Computing the conjugate of convex piecewise linear-quadratic bivariate functions. Math. Program. 139, 161–184 (2013). https://doi.org/10.1007/s10107-013-0666-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-013-0666-8

Keywords

Mathematics Subject Classification (2000)

Search

Navigation