Skip to main content
SpringerLink
Log in

Convex Hull Algorithms for Piecewise Linear-Quadratic Functions in Computational Convex Analysis

  • Published:
Set-Valued and Variational Analysis Aims and scope Submit manuscript

Abstract

Computing the convex envelope is a core operation in nonsmooth analysis that bridges the convex with the nonconvex world. Although efficient algorithms to compute fundamental transforms of convex analysis have been proposed over the years, they are limited to convex functions until an efficient algorithm becomes available to compute the convex envelope of a piecewise linear-quadratic function (of one variable) efficiently. We present two such algorithms, one based on maximum and conjugate computation that is easy to implement but has quadratic time complexity, and another based on direct computation that requires more work to implement but has optimal (linear time) complexity. We prove their time (and space) complexity, and compare their performances.

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

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, 768–785 (2008)

    Article  MathSciNet  Google Scholar 

  2. Bauschke, H.H., Lucet, Y., Trienis, M.: How to transform one convex function continuously into another. SIAM Rev. 50, 115–132 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bauschke, H.H., Wang, X.: The kernel average of two convex functions and its application to the extension and representation of monotone operators. Trans. Am. Math. Soc. 361, 5947–5965 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Taslakian, P.: Necklaces, convolutions, and X + Y. In: Algorithms—ESA 2006. Lecture Notes in Computer Science, vol. 4168, pp. 160–171. Springer, Berlin (2006)

    Chapter  Google Scholar 

  5. 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)

    MATH  MathSciNet  Google Scholar 

  6. Corrias, L.: Fast Legendre–Fenchel transform and applications to Hamilton–Jacobi equations and conservation laws. SIAM J. Numer. Anal. 33, 1534–1558 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  7. de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Algorithms and applications. In: Computational Geometry, 3rd edn. Springer, Berlin (2008)

    Google Scholar 

  8. Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATC Monographs on Theoretical Computer Science. Springer (1987)

  9. Felzenszwalb, P.F., Huttenlocher, D.P.: Distance Transforms of Sampled Functions. Tech. Rep. TR2004-1963, Cornell Computing and Information Science (2004)

  10. Gardiner, B., Lucet, Y.: Graph-Matrix Calculus for Computational Convex Analysis. Fixed-Point Algorithms for Inverse Problems in Science and Engineering. Springer Verlag series Optimization and Its Application (2010, in press)

  11. Hare, W.: A proximal average for nonconvex functions: a proximal stability perspective. SIAM J. Optim. 20, 650–666 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  12. Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex analysis and minimization algorithms. In: Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vols. 305–306. Springer, Berlin (1993); Vol I: Fundamentals. Vol II: Advanced Theory and Bundle Methods

    Google Scholar 

  13. Hiriart-Urruty, J.-B., Lucet, Y.: Parametric computation of the Legendre–Fenchel conjugate. J. Convex Anal. 14, 657–666 (2007)

    MathSciNet  Google Scholar 

  14. Koch, V., Johnstone, J., Lucet, Y.: Convexity of the proximal average. J. Optim. Theory Appl. (2010, in press)

  15. Lachand-Robert, T., Oudet, É.: Minimizing within convex bodies using a convex hull method. SIAM J. Optim. 16, 368–379 (2005, electronic)

    Article  MATH  MathSciNet  Google Scholar 

  16. Laraki, R., Lasserre, J.B.: Computing uniform convex approximations for convex envelopes and convex hulls. J. Convex Anal. 15, 635–654 (2008)

    MATH  MathSciNet  Google Scholar 

  17. Lucet, Y.: A fast computational algorithm for the Legendre–Fenchel transform. Comput. Optim. Appl. 6, 27–57 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  18. Lucet, Y.: Faster than the fast Legendre transform. The linear-time Legendre transform. Numer. Algorithms 16, 171–185 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  19. 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, Victoria BC. IEEE Computer Society Press (2005)

  20. Lucet, Y.: Fast Moreau envelope computation I: numerical algorithms. Numer. Algorithms 43, 235–249 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  21. Lucet, Y.: What shape is your conjugate? A survey of computational convex analysis and its applications. SIAM J. Optim. 20, 216–250 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  22. Lucet, Y., Bauschke, H.H., Trienis, M.: The piecewise linear-quadratic model for computational convex analysis. Comput. Optim. Appl. 43, 95–118 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  23. Moreau, J.-J.: Proximité et dualité dans un espace Hilbertien. Bull. Soc. Math. Fr. 93, 273–299 (1965)

    MATH  MathSciNet  Google Scholar 

  24. Noullez, A., Vergassola, M.: A fast Legendre transform algorithm and applications to the adhesion model. J. Sci. Comput. 9, 259–281 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  25. Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)

    Book  MATH  Google Scholar 

  26. She, Z.-S., Aurell, E., Frisch, U.: The inviscid Burgers equation with initial data of Brownian type. Commun. Math. Phys. 148, 623–641 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  27. Trienis, M.: Computational Convex Analysis: From Continuous Deformation to Finite Convex Integration. Master’s Thesis, University of British Columbia (2007)

Download references

Author information

Authors and Affiliations

  1. Computer Science, I. K. Barber School #4, University of British Columbia Okanagan, Kelowna, British Columbia, 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.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gardiner, B., Lucet, Y. Convex Hull Algorithms for Piecewise Linear-Quadratic Functions in Computational Convex Analysis. Set-Valued Anal 18, 467–482 (2010). https://doi.org/10.1007/s11228-010-0157-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11228-010-0157-5

Keywords

Mathematics Subject Classifications (2010)

Search

Navigation