{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T17:08:03Z","timestamp":1780592883184,"version":"3.54.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T00:00:00Z","timestamp":1774915200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T00:00:00Z","timestamp":1774915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2018-03928"],"award-info":[{"award-number":["RGPIN-2018-03928"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s10589-026-00781-5","type":"journal-article","created":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T12:09:42Z","timestamp":1774958982000},"page":"747-780","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computing the convex envelope of bivariate piecewise linear-quadratic functions in linear time"],"prefix":"10.1007","volume":"94","author":[{"given":"Tanmaya","family":"Karmarkar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0349-6737","authenticated-orcid":false,"given":"Yves","family":"Lucet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,3,31]]},"reference":[{"issue":"2","key":"781_CR1","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4171\/RMI\/643","volume":"27","author":"J-B Hiriart-Urruty","year":"2011","unstructured":"Hiriart-Urruty, J.-B., L\u00f3pez, M.A., Volle, M.: The $$\\epsilon $$-strategy in variational analysis: illustration with the closed convexification of a function. Rev. Mat. Iberoam. 27(2), 449\u2013474 (2011). https:\/\/doi.org\/10.4171\/RMI\/643","journal-title":"Rev. Mat. Iberoam."},{"key":"781_CR2","doi-asserted-by":"crossref","unstructured":"Locatelli, M., Schoen, F.: Global Optimization. MOS-SIAM Series on Optimization, p. 432. Society for Industrial and Applied Mathematics, Philadelphia, PA (2013). http:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611972672.fm","DOI":"10.1137\/1.9781611972672"},{"key":"781_CR3","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF01587085","volume":"44","author":"Y Crama","year":"1989","unstructured":"Crama, Y.: Recognition problems for special classes of polynomials in 0\u20131 variables. Math. Program. 44, 139\u2013155 (1989)","journal-title":"Math. Program."},{"issue":"1\u20132, Ser. A","key":"781_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10107-012-0616-x","volume":"144","author":"M Locatelli","year":"2014","unstructured":"Locatelli, M., Schoen, F.: On convex envelopes for bivariate functions over polytopes. Math. Program. 144(1\u20132, Ser. A), 65\u201391 (2014). https:\/\/doi.org\/10.1007\/s10107-012-0616-x","journal-title":"Math. Program."},{"issue":"2","key":"781_CR5","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/s10898-014-0177-z","volume":"59","author":"M Locatelli","year":"2014","unstructured":"Locatelli, M.: A technique to derive the analytical form of convex envelopes for some bivariate functions. J. Global Optim. 59(2), 477\u2013501 (2014). https:\/\/doi.org\/10.1007\/s10898-014-0177-z","journal-title":"J. Global Optim."},{"issue":"4","key":"781_CR6","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/s10898-016-0418-4","volume":"66","author":"M Locatelli","year":"2016","unstructured":"Locatelli, M.: Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes. J. Global Optim. 66(4), 629\u2013668 (2016). https:\/\/doi.org\/10.1007\/s10898-016-0418-4","journal-title":"J. Global Optim."},{"issue":"2","key":"781_CR7","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s10898-018-0626-1","volume":"72","author":"M Locatelli","year":"2018","unstructured":"Locatelli, M.: Convex envelopes of bivariate functions through the solution of KKT systems. J. Global Optim. 72(2), 277\u2013303 (2018). https:\/\/doi.org\/10.1007\/s10898-018-0626-1","journal-title":"J. Global Optim."},{"key":"781_CR8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2023.0001","author":"E Khademnia","year":"2024","unstructured":"Khademnia, E., Davarnia, D.: Convexification of bilinear terms over network polytopes. Math. Oper. Res. (2024). https:\/\/doi.org\/10.1287\/moor.2023.0001","journal-title":"Math. Oper. Res."},{"key":"781_CR9","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1287\/moor.8.2.273","volume":"8","author":"F Al-Khayyal","year":"1983","unstructured":"Al-Khayyal, F., Falk, J.: Jointly constrained biconvex programming. Math. Oper. Res. 8, 273\u2013286 (1983)","journal-title":"Math. Oper. Res."},{"key":"781_CR10","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/BF02283695","volume":"25","author":"H Sherali","year":"1990","unstructured":"Sherali, H., Alameddine, A.: An explicit characterization of the convex envelope of a bivariate bilinear function over special polytopes. Ann. Oper. Res. 25, 197\u2013209 (1990)","journal-title":"Ann. Oper. Res."},{"key":"781_CR11","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s10107-005-0582-7","volume":"2","author":"J Linderoth","year":"2005","unstructured":"Linderoth, J.: A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Program. 2, 251\u2013282 (2005)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"781_CR12","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-010-0355-9","volume":"124","author":"KM Anstreicher","year":"2010","unstructured":"Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124(1\u20132), 33\u201343 (2010). https:\/\/doi.org\/10.1007\/s10107-010-0355-9","journal-title":"Math. Program."},{"key":"781_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s10107-012-0602-3","volume":"136","author":"K Anstreicher","year":"2012","unstructured":"Anstreicher, K.: On convex relaxations for quadratically constrained quadratic programming. Math. Program. 136, 233\u2013251 (2012)","journal-title":"Math. Program."},{"issue":"2","key":"781_CR14","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/s10589-023-00534-8","volume":"87","author":"M Locatelli","year":"2024","unstructured":"Locatelli, M.: A new technique to derive tight convex underestimators (sometimes envelopes). Comput. Optim. Appl. 87(2), 475\u2013499 (2024). https:\/\/doi.org\/10.1007\/s10589-023-00534-8","journal-title":"Comput. Optim. Appl."},{"key":"781_CR15","unstructured":"Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Springer Dordrecht Heidelberg London New York (1998). http:\/\/www.springer.com\/math\/book\/978-3-540-62772-2"},{"key":"781_CR16","unstructured":"Goebel, R.: Convexity, convergence and feedback in optimal control. PhD thesis, University of Washington, Seattle (2000). https:\/\/digital.lib.washington.edu\/dspace\/handle\/1773\/5792"},{"issue":"1","key":"781_CR17","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10589-013-9622-z","volume":"58","author":"B Gardiner","year":"2014","unstructured":"Gardiner, B., Jakee, K., Lucet, Y.: Computing the partial conjugate of convex piecewise linear-quadratic bivariate functions. Comput. Optim. Appl. 58(1), 249\u2013272 (2014). https:\/\/doi.org\/10.1007\/s10589-013-9622-z","journal-title":"Comput. Optim. Appl."},{"key":"781_CR18","doi-asserted-by":"publisher","first-page":"273","DOI":"10.24033\/bsmf.1625","volume":"93","author":"J-J Moreau","year":"1965","unstructured":"Moreau, J.-J.: Proximit\u00e9 et dualit\u00e9 dans un espace Hilbertien. Bull. Soc. Math. France 93, 273\u2013299 (1965)","journal-title":"Bull. Soc. Math. France"},{"key":"781_CR19","unstructured":"Brenier, Y.: Un algorithme rapide pour le calcul de transform\u00e9es de Legendre\u2013Fenchel discr\u00e8tes. Comptes rendus de l\u2019Acad\u00e9mie des sciences. S\u00e9rie 1, Math\u00e9matique 308, 587\u2013589 (1989)"},{"issue":"4","key":"781_CR20","doi-asserted-by":"publisher","first-page":"1534","DOI":"10.1137\/S0036142993260208","volume":"33","author":"L Corrias","year":"1996","unstructured":"Corrias, L.: Fast Legendre-Fenchel transform and applications to Hamilton-Jacobi equations and conservation laws. SIAM J. Numer. Anal. 33(4), 1534\u20131558 (1996)","journal-title":"SIAM J. Numer. Anal."},{"issue":"1","key":"781_CR21","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/BF00248008","volume":"6","author":"Y Lucet","year":"1996","unstructured":"Lucet, Y.: A fast computational algorithm for the Legendre-Fenchel transform. Comput. Optim. Appl. 6(1), 27\u201357 (1996)","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"781_CR22","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1023\/A:1019191114493","volume":"16","author":"Y Lucet","year":"1997","unstructured":"Lucet, Y.: Faster than the Fast Legendre Transform, the Linear-time Legendre Transform. Numer. Algorithms 16(2), 171\u2013185 (1997)","journal-title":"Numer. Algorithms"},{"issue":"2","key":"781_CR23","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s10589-018-0007-1","volume":"70","author":"T Haque","year":"2018","unstructured":"Haque, T., Lucet, Y.: A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions. Comput. Optim. Appl. 70(2), 593\u2013613 (2018). https:\/\/doi.org\/10.1007\/s10589-018-0007-1","journal-title":"Comput. Optim. Appl."},{"key":"781_CR24","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10589-007-9124-y","volume":"43","author":"Y Lucet","year":"2009","unstructured":"Lucet, Y., Bauschke, H.H., Trienis, M.: The piecewise linear-quadratic model for computational convex analysis. Comput. Optim. Appl. 43, 95\u2013118 (2009)","journal-title":"Comput. Optim. Appl."},{"key":"781_CR25","doi-asserted-by":"publisher","unstructured":"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\u2013259. Springer, New York, NY (2011). https:\/\/doi.org\/10.1007\/978-1-4419-9569-8_12","DOI":"10.1007\/978-1-4419-9569-8_12"},{"key":"781_CR26","unstructured":"Lucet, Y.: Computational Convex Analysis (CCA) numerical library. GitHub (2017)"},{"key":"781_CR27","unstructured":"Lucet, Y.: Computational Convex Analysis for bivariate piecewise linear-cubic functions (CCA2) numerical library. GitHub (2021)"},{"issue":"3","key":"781_CR28","first-page":"657","volume":"14","author":"J-B Hiriart-Urruty","year":"2007","unstructured":"Hiriart-Urruty, J.-B., Lucet, Y.: Parametric computation of the Legendre-Fenchel conjugate. J. Convex Anal. 14(3), 657\u2013666 (2007)","journal-title":"J. Convex Anal."},{"issue":"3","key":"781_CR29","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s11075-006-9056-0","volume":"43","author":"Y Lucet","year":"2006","unstructured":"Lucet, Y.: Fast Moreau envelope computation I: numerical algorithms. Numer. Algorithms 43(3), 235\u2013249 (2006). https:\/\/doi.org\/10.1007\/s11075-006-9056-0","journal-title":"Numer. Algorithms"},{"issue":"2","key":"781_CR30","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1137\/070687542","volume":"19","author":"HH Bauschke","year":"2008","unstructured":"Bauschke, H.H., Goebel, R., Lucet, Y., Wang, X.: The proximal average: basic theory. SIAM J. Optim. 19(2), 768\u2013785 (2008)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"781_CR31","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1137\/060664513","volume":"50","author":"HH Bauschke","year":"2008","unstructured":"Bauschke, H.H., Lucet, Y., Trienis, M.: How to transform one convex function continuously into another. SIAM Rev. 50(1), 115\u2013132 (2008)","journal-title":"SIAM Rev."},{"issue":"1","key":"781_CR32","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1137\/19M1290851","volume":"31","author":"S Singh","year":"2021","unstructured":"Singh, S., Lucet, Y.: Linear-time convexity test for low-order piecewise polynomials. SIAM J. Optim. 31(1), 972\u2013990 (2021). https:\/\/doi.org\/10.1137\/19M1290851","journal-title":"SIAM J. Optim."},{"key":"781_CR33","unstructured":"Lucet, Y.: Computational Convex Analysis library 2 (2021). https:\/\/github.com\/ylucet\/CCA2"},{"issue":"3","key":"781_CR34","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/100788458","volume":"52","author":"Y Lucet","year":"2010","unstructured":"Lucet, Y.: What shape is your conjugate? a survey of computational convex analysis and its applications. SIAM Rev. 52(3), 505\u2013542 (2010)","journal-title":"SIAM Rev."},{"key":"781_CR35","unstructured":"Berg, M., Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry, 3rd edn., p. 386. Springer, Berlin (2008). Algorithms and applications. http:\/\/www.springer.com\/computer\/theoretical+computer+science\/book\/978-3-540-77973-5"},{"key":"781_CR36","doi-asserted-by":"crossref","unstructured":"Kumar, D., Lucet, Y.: Towards the biconjugate of bivariate piecewise quadratic functions. In: Le Thi, H.A., Le, H.M., Pham Dinh, T. (eds.) Optimization of Complex Systems: Theory, Models, Algorithms and Applications, pp. 257\u2013266. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-21803-4_27"},{"key":"781_CR37","unstructured":"Karmarkar, T.: Computing the conjugate of nonconvex bivariate piecewise linear-quadratic functions. Master\u2019s thesis, University of British Columbia (2024). https:\/\/dx.doi.org\/10.14288\/1.0444097"},{"key":"781_CR38","doi-asserted-by":"crossref","unstructured":"Karmarkar, T., Lucet, Y.: A linear-time algorithm to compute the conjugate of nonconvex bivariate piecewise linear-quadratic functions. J. Global Optim. (2025)","DOI":"10.1007\/s10589-026-00781-5"},{"key":"781_CR39","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton Mathematical Series. Princeton University Press, Princeton, N. J. (1970). http:\/\/press.princeton.edu\/titles\/1815.html"},{"issue":"8","key":"781_CR40","doi-asserted-by":"publisher","first-page":"1770","DOI":"10.1016\/j.automatica.2011.04.003","volume":"47","author":"P Patrinos","year":"2011","unstructured":"Patrinos, P., Sarimveis, H.: Convex parametric piecewise quadratic optimization: theory and algorithms. Automatica 47(8), 1770\u20131777 (2011)","journal-title":"Automatica"},{"issue":"1\u20132","key":"781_CR41","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10107-013-0666-8","volume":"139","author":"B Gardiner","year":"2013","unstructured":"Gardiner, B., Lucet, Y.: Computing the conjugate of convex piecewise linear-quadratic bivariate functions. Math. Program. 139(1\u20132), 161\u2013184 (2013). https:\/\/doi.org\/10.1007\/s10107-013-0666-8","journal-title":"Math. Program."},{"key":"781_CR42","doi-asserted-by":"crossref","unstructured":"Bauschke, H.H., Moursi, W.M.: An Introduction to Convexity, Optimization, and Algorithms, vol. 34. Society for Industrial and Applied Mathematics, Philadelphia (2024)","DOI":"10.1137\/1.9781611977806"},{"key":"781_CR43","doi-asserted-by":"crossref","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms I. Grundlehren der Mathematischen Wissenschaften , vol. 305. Springer, Berlin (1993). Vol I: Fundamentals. http:\/\/www.springer.com\/math\/book\/978-3-540-56850-6","DOI":"10.1007\/978-3-662-02796-7"},{"key":"781_CR44","doi-asserted-by":"crossref","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms II. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 306. Springer, Berlin (1993). Vol II: Advanced theory and bundle methods. http:\/\/www.springer.com\/math\/book\/978-3-540-56850-6","DOI":"10.1007\/978-3-662-06409-2"},{"key":"781_CR45","unstructured":"Kumar, D.: Conjugate of some rational functions and convex envelope of quadratic functions over a polytope. Master\u2019s thesis, University of British Columbia (2019)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-026-00781-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-026-00781-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-026-00781-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T09:56:58Z","timestamp":1780307818000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-026-00781-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,31]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["781"],"URL":"https:\/\/doi.org\/10.1007\/s10589-026-00781-5","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,31]]},"assertion":[{"value":"25 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}