{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T17:07:45Z","timestamp":1780592865231,"version":"3.54.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T00:00:00Z","timestamp":1748304000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T00:00:00Z","timestamp":1748304000000},"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- 0392"],"award-info":[{"award-number":["RGPIN-2018- 0392"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2026,1]]},"DOI":"10.1007\/s10898-025-01503-7","type":"journal-article","created":{"date-parts":[[2025,5,26]],"date-time":"2025-05-26T21:18:58Z","timestamp":1748294338000},"page":"3-34","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A linear-time algorithm to compute the conjugate of nonconvex bivariate piecewise linear-quadratic functions"],"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":[[2025,5,27]]},"reference":[{"key":"1503_CR1","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":"1503_CR2","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. Mathematical Programming 44, 139\u2013155 (1989)","journal-title":"Mathematical Programming"},{"key":"1503_CR3","doi-asserted-by":"publisher","unstructured":"Locatelli, M., Schoen, F.: On convex envelopes for bivariate functions over polytopes. Mathematical Programming 144(1-2, Ser. A), 65\u201391 (2014) https:\/\/doi.org\/10.1007\/s10107-012-0616-x","DOI":"10.1007\/s10107-012-0616-x"},{"issue":"2","key":"1503_CR4","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. Journal of global optimization 59(2), 477\u2013501 (2014). https:\/\/doi.org\/10.1007\/s10898-014-0177-z","journal-title":"Journal of global optimization"},{"issue":"4","key":"1503_CR5","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. Journal of global optimization 66(4), 629\u2013668 (2016). https:\/\/doi.org\/10.1007\/s10898-016-0418-4","journal-title":"Journal of global optimization"},{"issue":"2","key":"1503_CR6","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. Journal of global optimization 72(2), 277\u2013303 (2018). https:\/\/doi.org\/10.1007\/s10898-018-0626-1","journal-title":"Journal of global optimization"},{"key":"1503_CR7","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. Mathematics of operations research (2024). https:\/\/doi.org\/10.1287\/moor.2023.0001","journal-title":"Mathematics of operations research"},{"key":"1503_CR8","doi-asserted-by":"crossref","unstructured":"Al-Khayyal, F., Falk, J.: Jointly constrained biconvex programming. Mathematics of Operations Research 8 (1983)","DOI":"10.1287\/moor.8.2.273"},{"key":"1503_CR9","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. Annals of Operations Research 25, 197\u2013209 (1990)","journal-title":"Annals of Operations Research"},{"key":"1503_CR10","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. Mathematical Programming 2, 251\u2013282 (2005)","journal-title":"Mathematical Programming"},{"issue":"1\u20132","key":"1503_CR11","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. Mathematical programming 124(1\u20132), 33\u201343 (2010). https:\/\/doi.org\/10.1007\/s10107-010-0355-9","journal-title":"Mathematical programming"},{"key":"1503_CR12","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. Mathematical Programming 136, 233\u2013251 (2012)","journal-title":"Mathematical Programming"},{"issue":"2","key":"1503_CR13","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). Computational optimization and applications 87(2), 475\u2013499 (2024). https:\/\/doi.org\/10.1007\/s10589-023-00534-8","journal-title":"Computational optimization and applications"},{"key":"1503_CR14","unstructured":"Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, ??? (1998). http:\/\/www.springer.com\/math\/book\/978-3-540-62772-2"},{"key":"1503_CR15","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":"1503_CR16","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. Computational Optimization and Applications 58(1), 249\u2013272 (2014). https:\/\/doi.org\/10.1007\/s10589-013-9622-z","journal-title":"Computational Optimization and Applications"},{"key":"1503_CR17","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":"1503_CR18","unstructured":"Brenier, Y.: Un algorithme rapide pour le calcul de transform\u00e9es de Legendre\u2013Fenchel discr\u00e8tes. C. R. Acad. Sci. Paris S\u00e9r. I Math. 308, 587\u2013589 (1989)"},{"issue":"4","key":"1503_CR19","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":"1503_CR20","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. Computational optimization and Applications 6(1), 27\u201357 (1996)","journal-title":"Computational optimization and Applications"},{"issue":"2","key":"1503_CR21","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. Numerical Algorithms 16(2), 171\u2013185 (1997)","journal-title":"Numerical Algorithms"},{"issue":"2","key":"1503_CR22","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. Computational Optimization and Applications 70(2), 593\u2013613 (2018). https:\/\/doi.org\/10.1007\/s10589-018-0007-1","journal-title":"Computational Optimization and Applications"},{"key":"1503_CR23","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. Computational Optimization and Applications 43, 95\u2013118 (2009)","journal-title":"Computational Optimization and Applications"},{"key":"1503_CR24","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, ??? (2011). https:\/\/doi.org\/10.1007\/978-1-4419-9569-8_12","DOI":"10.1007\/978-1-4419-9569-8_12"},{"key":"1503_CR25","unstructured":"Lucet, Y.: Computational Convex Analysis (CCA) numerical library. GitHub (2017)"},{"key":"1503_CR26","unstructured":"Lucet, Y.: Computational Convex Analysis for bivariate piecewise linear-cubic functions (CCA2) numerical library. GitHub (2021)"},{"issue":"3","key":"1503_CR27","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. Journal of Convex Analysis 14(3), 657\u2013666 (2007)","journal-title":"Journal of Convex Analysis"},{"issue":"3","key":"1503_CR28","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":"1503_CR29","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":"1503_CR30","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":"1503_CR31","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 Journal on Optimization 31(1), 972\u2013990 (2021). https:\/\/doi.org\/10.1137\/19M1290851","journal-title":"SIAM Journal on Optimization"},{"key":"1503_CR32","unstructured":"Lucet, Y.: Computational Convex Analysis library 2 (2021). https:\/\/github.com\/ylucet\/CCA2"},{"issue":"3","key":"1503_CR33","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 Review 52(3), 505\u2013542 (2010)","journal-title":"SIAM Review"},{"key":"1503_CR34","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-030-21803-4_27","volume-title":"Optimization of Complex Systems: Theory, Models, Algorithms and Applications","author":"D Kumar","year":"2020","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)"},{"key":"1503_CR35","doi-asserted-by":"publisher","first-page":"209","DOI":"10.2140\/pjm.1970.33.209","volume":"33","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: On the maximal monotonicity of subdifferential mappings. Pacific J. Math. 33, 209\u2013216 (1970)","journal-title":"Pacific J. Math."},{"issue":"8","key":"1503_CR36","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":"1503_CR37","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. Mathematical Programming 139(1\u20132), 161\u2013184 (2013). https:\/\/doi.org\/10.1007\/s10107-013-0666-8","journal-title":"Mathematical Programming"},{"key":"1503_CR38","volume-title":"An Introduction to Convexity, Optimization, and Algorithms","author":"HH Bauschke","year":"2024","unstructured":"Bauschke, H.H., Moursi, W.M.: An Introduction to Convexity, Optimization, and Algorithms, vol. 34. Society for Industrial and Applied Mathematics, Philadelphia (2024)"},{"key":"1503_CR39","doi-asserted-by":"crossref","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms I. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 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":"1503_CR40","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":"1503_CR41","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, ??? (1970). http:\/\/press.princeton.edu\/titles\/1815.html"},{"key":"1503_CR42","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)"},{"key":"1503_CR43","doi-asserted-by":"publisher","unstructured":"Karmarkar, T.: Computing the conjugate of nonconvex bivariate piecewise linear-quadratic functions. Master\u2019s thesis, University of British Columbia (2024). https:\/\/doi.org\/10.14288\/1.0444097","DOI":"10.14288\/1.0444097"},{"issue":"4","key":"1503_CR44","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1007\/s00454-016-9785-3","volume":"56","author":"TM Chan","year":"2016","unstructured":"Chan, T.M.: A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions. Discrete & Computational Geometry 56(4), 860\u2013865 (2016). https:\/\/doi.org\/10.1007\/s00454-016-9785-3","journal-title":"Discrete & Computational Geometry"},{"key":"1503_CR45","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"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01503-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-025-01503-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01503-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T04:00:27Z","timestamp":1770609627000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-025-01503-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,27]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["1503"],"URL":"https:\/\/doi.org\/10.1007\/s10898-025-01503-7","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,27]]},"assertion":[{"value":"9 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Materials availability"}}]}}