{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:59Z","timestamp":1740109259799,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T00:00:00Z","timestamp":1556841600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T00:00:00Z","timestamp":1556841600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000149","name":"Division of Engineering Education and Centers","doi-asserted-by":"publisher","award":["CAREER Award"],"award-info":[{"award-number":["CAREER Award"]}],"id":[{"id":"10.13039\/100000149","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Google Faculty Award"],"award-info":[{"award-number":["Google Faculty Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007242","name":"Office of the Dean for Research, Princeton University","doi-asserted-by":"publisher","award":["SEAS Innovation Award"],"award-info":[{"award-number":["SEAS Innovation Award"]}],"id":[{"id":"10.13039\/100007242","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s10107-019-01396-x","type":"journal-article","created":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T12:05:00Z","timestamp":1556885100000},"page":"429-443","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On the complexity of detecting convexity over a box"],"prefix":"10.1007","volume":"182","author":[{"given":"Amir Ali","family":"Ahmadi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4580-3897","authenticated-orcid":false,"given":"Georgina","family":"Hall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,3]]},"reference":[{"key":"1396_CR1","unstructured":"Ahmadi, A.A., Jungers, R.M.: SOS-convex Lyapunov functions and stability of difference inclusions. \narXiv:1803.02070\n\n (2018)"},{"issue":"1\u20132","key":"1396_CR2","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s10107-011-0499-2","volume":"137","author":"AA Ahmadi","year":"2013","unstructured":"Ahmadi, A.A., Olshevsky, A., Parrilo, P.A., Tsitsiklis, J.N.: NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Program. 137(1\u20132), 453\u2013476 (2013)","journal-title":"Math. Program."},{"issue":"3","key":"1396_CR3","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1137\/S1052623400374756","volume":"12","author":"A Ben-Tal","year":"2002","unstructured":"Ben-Tal, A., Nemirovski, A.: On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty. SIAM J. Optim. 12(3), 811\u2013833 (2002)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1396_CR4","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1287\/moor.28.3.497.16392","volume":"28","author":"A Ben-Tal","year":"2003","unstructured":"Ben-Tal, A., Nemirovski, A., Roos, C.: Extended matrix cube theorems with applications to $$\\mu $$-theory in control. Math. Oper. Res. 28(3), 497\u2013523 (2003)","journal-title":"Math. Oper. Res."},{"key":"1396_CR5","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-1-4615-2025-2_3","volume-title":"Handbook of Global Optimization","author":"H Benson","year":"1995","unstructured":"Benson, H.: Concave minimization: theory, applications and algorithms. In: Horst, R., Pardalos, P. (eds.) Handbook of Global Optimization, pp. 43\u2013148. Springer, Boston (1995)"},{"key":"1396_CR6","volume-title":"Convex Optimization Theory","author":"DP Bertsekas","year":"2009","unstructured":"Bertsekas, D.P.: Convex Optimization Theory. Athena Scientific Belmont, Belmont (2009)"},{"issue":"6","key":"1396_CR7","doi-asserted-by":"publisher","first-page":"2118","DOI":"10.1137\/S0363012994272630","volume":"35","author":"V Blondel","year":"1997","unstructured":"Blondel, V., Tsitsiklis, J.N.: NP-hardness of some linear control design problems. SIAM J. Control Optim. 35(6), 2118\u20132127 (1997)","journal-title":"SIAM J. Control Optim."},{"key":"1396_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"issue":"10","key":"1396_CR9","doi-asserted-by":"publisher","first-page":"2431","DOI":"10.1109\/TAC.2008.2007857","volume":"53","author":"G Chesi","year":"2008","unstructured":"Chesi, G., Hung, Y.S.: Establishing convexity of polynomial Lyapunov functions and their sublevel sets. IEEE Trans. Autom. Control 53(10), 2431\u20132436 (2008)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"1\u20134","key":"1396_CR10","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1023\/A:1013178600790","volume":"104","author":"JW Chinneck","year":"2001","unstructured":"Chinneck, J.W.: Analyzing mathematical programs using MProbe. Ann. Oper. Res. 104(1\u20134), 33\u201348 (2001)","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"1396_CR11","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1287\/ijoc.1090.0321","volume":"22","author":"R Fourer","year":"2010","unstructured":"Fourer, R., Maheshwari, C., Neumaier, A., Orban, D., Schichl, H.: Convexity and concavity detection in computational graphs: tree walks for convexity assessment. INFORMS J. Comput. 22(1), 26\u201343 (2010)","journal-title":"INFORMS J. Comput."},{"key":"1396_CR12","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Co., San Francisco (1979)"},{"key":"1396_CR13","unstructured":"Gershgorin, S.A.: Uber die Abgrenzung der Eigenwerte einer Matrix. Bulletin de l\u2019Acad\u00e9mie des Sciences de l\u2019URSS. Classe des sciences mathematiques et naturelles 6, 749\u2013754 (1931)"},{"key":"1396_CR14","unstructured":"Grant, M., Boyd, S.: CVX: MATLAB software for disciplined convex programming, version 1.21. \nhttp:\/\/cvxr.com\/cvx\n\n (2010)"},{"key":"1396_CR15","unstructured":"Gurobi optimizer reference manual. \nhttp:\/\/www.gurobi.com\n\n (2012)"},{"key":"1396_CR16","unstructured":"Hall, G.: Optimization over nonnegative and convex polynomials with and without semidefinite programming. Ph.D. thesis, Princeton University. \narXiv:1806.06996\n\n (2018)"},{"issue":"1","key":"1396_CR17","first-page":"3261","volume":"14","author":"LA Hannah","year":"2013","unstructured":"Hannah, L.A., Dunson, D.B.: Multivariate convex regression with adaptive partitioning. J. Mach. Learn. Res. 14(1), 3261\u20133294 (2013)","journal-title":"J. Mach. Learn. Res."},{"issue":"4","key":"1396_CR18","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/2421119.2421135","volume":"43","author":"LA Hemaspaandra","year":"2012","unstructured":"Hemaspaandra, L.A., Williams, R.: SIGACT News-Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms. ACM SIGACT News 43(4), 70\u201389 (2012)","journal-title":"ACM SIGACT News"},{"key":"1396_CR19","volume-title":"Matrix Analysis","author":"RA Horn","year":"1995","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1995)"},{"key":"1396_CR20","first-page":"1","volume":"10","author":"A Khajavirad","year":"2017","unstructured":"Khajavirad, A., Sahinidis, N.V.: A hybrid LP\/NLP paradigm for global optimization relaxations. Math. Program. Comput. 10, 1\u201339 (2017)","journal-title":"Math. Program. Comput."},{"issue":"1","key":"1396_CR21","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1287\/opre.1110.1007","volume":"60","author":"E Lim","year":"2012","unstructured":"Lim, E., Glynn, P.W.: Consistency of multidimensional convex regression. Oper. Res. 60(1), 196\u2013208 (2012)","journal-title":"Oper. Res."},{"key":"1396_CR22","unstructured":"Magnani, A., Lall, S., Boyd, S.: Tractable fitting with convex polynomials via sum-of-squares. In: Proceedings of the 44th IEEE Conference on Decision and Control, pp. 1672\u20131677 (2005)"},{"key":"1396_CR23","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39, 117\u2013129 (1987)","journal-title":"Math. Program."},{"issue":"2","key":"1396_CR24","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01211741","volume":"6","author":"A Nemirovski","year":"1993","unstructured":"Nemirovski, A.: Several NP-hard problems arising in robust stability analysis. Math. Control Signals Syst. 6(2), 99\u2013105 (1993)","journal-title":"Math. Control Signals Syst."},{"issue":"1\u20133","key":"1396_CR25","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF01581088","volume":"57","author":"PM Pardalos","year":"1992","unstructured":"Pardalos, P.M., Vavasis, S.A.: Open questions in complexity theory for numerical optimization. Math. Program. 57(1\u20133), 337\u2013339 (1992)","journal-title":"Math. Program."},{"issue":"2","key":"1396_CR26","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF00138693","volume":"8","author":"N Sahinidis","year":"1996","unstructured":"Sahinidis, N.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8(2), 201\u2013205 (1996)","journal-title":"J. Glob. Optim."},{"key":"1396_CR27","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"2006","unstructured":"Sipser, M.: Introduction to the Theory of Computation, vol. 2. Thomson Course Technology, Boston (2006)"},{"issue":"6","key":"1396_CR28","doi-asserted-by":"publisher","first-page":"2624","DOI":"10.1214\/15-AOS1425","volume":"44","author":"M Xu","year":"2016","unstructured":"Xu, M., Chen, M., Lafferty, J.: Faithful variable screening for high-dimensional convex regression. Ann. Stat. 44(6), 2624\u20132660 (2016)","journal-title":"Ann. Stat."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01396-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01396-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01396-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,23]],"date-time":"2020-06-23T15:16:49Z","timestamp":1592925409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01396-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,3]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["1396"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01396-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2019,5,3]]},"assertion":[{"value":"15 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}