Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Computing the partial conjugate of convex piecewise linear-quadratic bivariate functions

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

Piecewise linear-quadratic (PLQ) functions are an important class of functions in convex analysis since the result of most convex operators applied to a PLQ function is a PLQ function. We modify a recent algorithm for computing the convex (Legendre-Fenchel) conjugate of convex PLQ functions of two variables, to compute its partial conjugate i.e. the conjugate with respect to one of the variables. The structure of the original algorithm is preserved including its time complexity (linear time with some approximation and log-linear time without approximation). Applying twice the partial conjugate (and a variable switching operator) recovers the full conjugate. We present our partial conjugate algorithm, which is more flexible and simpler than the original full conjugate algorithm. We emphasize the difference with the full conjugate algorithm and illustrate results by computing partial conjugates, partial Moreau envelopes, and partial proximal averages.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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
Algorithm 1

Similar content being viewed by others

References

  1. Alfeld, P., Schumaker, L.L.: Smooth macro-elements based on Powell-Sabin triangle splits. Adv. Comput. Math. 16, 29–46 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  2. 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 

  3. 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 

  4. Bauschke, H.H., Lucet, Y., Wang, X.: Primal-dual symmetric intrinsic methods for finding antiderivatives of cyclically monotone operators. SIAM J. Control Optim. 46, 2031–2051 (2007)

    Article  MATH  MathSciNet  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)

    Chapter  Google Scholar 

  6. Bauschke, H.H., Wang, X., Yao, L.: Autoconjugate representers for linear monotone operators. Math. Program. 123, 5–24 (2010)

    Article  MATH  MathSciNet  Google Scholar 

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

  8. Cao, J., Li, X., Wang, G., Qin, H.: Surface reconstruction using bivariate simplex splines on Delaunay configurations. In: IEEE International Conference on Shape Modeling and Applications. Computers & Graphics-UK, Tsinghua Univ, Beijing, P.R. China, Jun. 26–28, 2009, vol. 33, pp. 341–350 (2009)

    Google Scholar 

  9. CGAL: Computational geometry algorithms library. http://www.cgal.org

  10. CGLAB a Scilab toolbox for geometry based on CGAL. http://cglab.gforge.inria.fr/

  11. Consortium, S.: Scilab (1994). http://www.scilab.org

  12. 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 

  13. Dæhlen, M., Lyche, T.: Bivariate interpolation with quadratic box splines. Math. Comput. 51, 219–230 (1988)

    MATH  Google Scholar 

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

    MATH  Google Scholar 

  15. Dierckx, P., Van Leemput, S., Vermeire, T.: Algorithms for surface fitting using Powell-Sabin splines. IMA J. Numer. Anal. 12, 271–299 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  16. Gardiner, B., Lucet, Y.: Numerical computation of Fitzpatrick functions. J. Convex Anal. 16, 779–790 (2009)

    MATH  MathSciNet  Google Scholar 

  17. Gardiner, B., Lucet, Y.: Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis. Set-Valued Var. Anal. 18, 467–482 (2010)

    Article  MATH  MathSciNet  Google Scholar 

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

    Chapter  Google Scholar 

  19. Gardiner, B., Lucet, Y.: Computing the conjugate of convex piecewise linear-quadratic bivariate functions. Math. Program. 1–24 (2013)

  20. Goebel, R.: Convexity, convergence and feedback in optimal control. PhD thesis, University of Washington, Seattle (2000)

  21. Goebel, R.: Self-dual smoothing of convex and saddle functions. J. Convex Anal. 15, 179–190 (2008)

    MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  23. 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). Vol I: Fundamentals, Vol II: Advanced theory and bundle methods

    Google Scholar 

  24. Johnstone, J., Koch, V., Lucet, Y.: Convexity of the proximal average. J. Optim. Theory Appl. 148, 107–124 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  25. Lai, M.-J., Schumaker, L.L.: Spline Functions on Triangulations. Encyclopedia of Mathematics and Its Applications, vol. 110. Cambridge University Press, Cambridge (2007)

    Book  MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  27. Lucet, Y.: Computational convex analysis library, 1996–2011. https://people.ok.ubc.ca/ylucet/cca.html

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  30. Lucet, Y.: What shape is your conjugate? A survey of computational convex analysis and its applications. SIAM Rev. 52, 505–542 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  31. 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 

  32. Manni, C., Sablonnière, P.: Quadratic spline quasi-interpolants on Powell-Sabin partitions. Adv. Comput. Math. 26, 283–304 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  33. Moffat, S.M.: On the kernel average of n functions. Master’s thesis, Department of Mathematics, University of British Columbia (Dec 2009)

  34. 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 

  35. Patrinos, P., Sarimveis, H.: Convex parametric piecewise quadratic optimization: theory, algorithms and control applications. Tech. rep., National Technical University of Athens, Greece (2010)

  36. Patrinos, P., Sarimveis, H.: A new algorithm for solving convex parametric quadratic programs based on graphical derivatives of solution mappings. Automatica 46, 1405–1418 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  37. Patrinos, P., Sarimveis, H.: Convex parametric piecewise quadratic optimization: theory and algorithms. Automatica 47, 1770–1777 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  38. Penot, J.-P.: The relevance of convex analysis for the study of monotonicity. Nonlinear Anal. 58, 855–871 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  39. Powell, M.J.D., Sabin, M.A.: Piecewise quadratic approximations on triangles. ACM Trans. Math. Softw. 3, 316–325 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  40. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

  42. Sbibih, D., Serghini, A., Tijini, A.: Polar forms and quadratic spline quasi-interpolants on Powell-Sabin partitions. Appl. Numer. Math. 59, 938–958 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  43. Sbibih, D., Serghini, A., Tijini, A.: Bivariate simplex spline quasi-interpolants. Numer. Math. 3, 97–118 (2010)

    MATH  MathSciNet  Google Scholar 

  44. 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 

  45. Sorokina, T., Zeilfelder, F.: Optimal quasi-interpolation by quadratic C 1-splines on type-2 triangulations. In: Approximation Theory XI: Gatlinburg 2004, Mod. Methods Math., pp. 423–438. Nashboro Press, Brentwood (2005)

    Google Scholar 

  46. Speleers, H., Dierckx, P., Vandewalle, S.: Quasi-hierarchical Powell-Sabin B-splines. Comput. Aided Geom. Des. 26, 174–191 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  47. Wiley, D.F., Childs, H.R., Hamann, B., Joy, K.I., Max, N.L.: Best quadratic spline approximation for hierarchical visualization. In: Proceedings of the Symposium on Data Visualisation 2002, VISSYM ’02, Aire-la-Ville. Eurographics Association, Switzerland, pp. 133–140 (2002)

    Google Scholar 

  48. Willemans, K., Dierckx, P.: Surface fitting using convex Powell-Sabin splines. J. Comput. Appl. Math. 56, 263–282 (1994)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgements

Yves Lucet and Khan Jakee were 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 performed in the Computer-Aided Convex Analysis laboratory funded by the Canadian Foundation for Innovation.

Special thanks go to Rafal Goebel who pointed out the proof of Fact 3.3 in [20]. The authors are indebted to the referees for invaluable feedback that resulted in the inclusion of Fact 3.3, and greatly improved the presentation of the paper.

Author information

Authors and Affiliations

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

    Bryan Gardiner, Khan Jakee & Yves Lucet

Authors
  1. Bryan Gardiner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Khan Jakee
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. 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., Jakee, K. & Lucet, Y. Computing the partial conjugate of convex piecewise linear-quadratic bivariate functions. Comput Optim Appl 58, 249–272 (2014). https://doi.org/10.1007/s10589-013-9622-z

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-013-9622-z

Keywords

Search

Navigation