{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T19:08:24Z","timestamp":1770232104278,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,7,6]],"date-time":"2019-07-06T00:00:00Z","timestamp":1562371200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,6]],"date-time":"2019-07-06T00:00:00Z","timestamp":1562371200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["Young Faculty Award"],"award-info":[{"award-number":["Young Faculty Award"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000084","name":"Directorate for Engineering","doi-asserted-by":"publisher","award":["CAREER Award"],"award-info":[{"award-number":["CAREER Award"]}],"id":[{"id":"10.13039\/100000084","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","award":["Sloan Fellowship"],"award-info":[{"award-number":["Sloan Fellowship"]}],"id":[{"id":"10.13039\/100000879","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\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["Young Investigator Prize"],"award-info":[{"award-number":["Young Investigator Prize"]}],"id":[{"id":"10.13039\/100000181","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,11]]},"DOI":"10.1007\/s10107-019-01411-1","type":"journal-article","created":{"date-parts":[[2019,7,6]],"date-time":"2019-07-06T02:02:36Z","timestamp":1562378556000},"page":"221-241","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On the complexity of testing attainment of the optimal value in nonlinear optimization"],"prefix":"10.1007","volume":"184","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1590-7281","authenticated-orcid":false,"given":"Amir Ali","family":"Ahmadi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,6]]},"reference":[{"key":"1411_CR1","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s10107-017-1144-5","volume":"169","author":"AA Ahmadi","year":"2015","unstructured":"Ahmadi, A.A., Hall, G.: DC decomposition of nonconvex polynomials with algebraic techniques. Math. Program. 169, 69\u201394 (2015)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1411_CR2","doi-asserted-by":"crossref","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."},{"key":"1411_CR3","first-page":"194","volume":"4","author":"V Andronov","year":"1982","unstructured":"Andronov, V., Belousov, E., Shironin, V.: On solvability of the problem of polynomial programming. Izvestija Akadem. Nauk SSSR Tekhnicheskaja Kibernetika 4, 194\u2013197 (1982)","journal-title":"Izvestija Akadem. Nauk SSSR Tekhnicheskaja Kibernetika"},{"key":"1411_CR4","unstructured":"Bajbar, T., Behrends, S.: How fast do coercive polynomials grow? Technical report, Instituts f\u00fcr Numerische und Angewandte Mathematik, Georg-August-Universit\u00e4t G\u00f6ttingen (2017)"},{"issue":"3","key":"1411_CR5","doi-asserted-by":"crossref","first-page":"1542","DOI":"10.1137\/140980624","volume":"25","author":"T Bajbar","year":"2015","unstructured":"Bajbar, T., Stein, O.: Coercive polynomials and their Newton polytopes. SIAM J. Optim. 25(3), 1542\u20131570 (2015)","journal-title":"SIAM J. Optim."},{"issue":"12","key":"1411_CR6","doi-asserted-by":"crossref","first-page":"1270","DOI":"10.1016\/j.jsc.2010.06.009","volume":"45","author":"S Basu","year":"2010","unstructured":"Basu, S., Roy, M.-F.: Bounding the radii of balls meeting every connected component of semi-algebraic sets. J. Symb. Comput. 45(12), 1270\u20131279 (2010)","journal-title":"J. Symb. Comput."},{"issue":"1","key":"1411_CR7","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1023\/A:1014813701864","volume":"22","author":"EG Belousov","year":"2002","unstructured":"Belousov, E.G., Klatte, D.: A Frank\u2013Wolfe type theorem for convex polynomial programs. Comput. Optim. Appl. 22(1), 37\u201348 (2002)","journal-title":"Comput. Optim. Appl."},{"key":"1411_CR8","volume-title":"Nonlinear Programming","author":"DP Bertsekas","year":"1999","unstructured":"Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999)"},{"issue":"2","key":"1411_CR9","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s10107-006-0003-6","volume":"110","author":"DP Bertsekas","year":"2007","unstructured":"Bertsekas, D.P., Tseng, P.: Set intersection theorems and existence of optimal solutions. Math. Program. 110(2), 287\u2013314 (2007)","journal-title":"Math. Program."},{"key":"1411_CR10","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611972290","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry","author":"G Blekherman","year":"2012","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R.R.: Semidefinite Optimization and Convex Algebraic Geometry. SIAM, Philadelphia (2012)"},{"issue":"1\u20132","key":"1411_CR11","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. (NRL) 3(1\u20132), 95\u2013110 (1956)","journal-title":"Naval Res. Logist. (NRL)"},{"key":"1411_CR12","volume-title":"Computers and Intractability","author":"MR Garey","year":"2002","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. WH Freeman, New York (2002)"},{"issue":"1","key":"1411_CR13","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1070\/RM1961v016n01ABEH004100","volume":"16","author":"EA Gorin","year":"1961","unstructured":"Gorin, E.A.: Asymptotic properties of polynomials and algebraic functions of several variables. Russ. Math. Surv. 16(1), 93\u2013119 (1961)","journal-title":"Russ. Math. Surv."},{"key":"1411_CR14","doi-asserted-by":"crossref","unstructured":"Greuet, A., Safey El\u00a0Din, M.: Deciding reachability of the infimum of a multivariate polynomial. In: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, pp. 131\u2013138. ACM (2011)","DOI":"10.1145\/1993886.1993910"},{"issue":"3","key":"1411_CR15","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1137\/130931308","volume":"24","author":"A Greuet","year":"2014","unstructured":"Greuet, A., Safey El Din, M.: Probabilistic algorithm for polynomial optimization over a real algebraic set. SIAM J. Optim. 24(3), 1313\u20131343 (2014)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1411_CR16","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1007\/s10957-014-0545-3","volume":"163","author":"V Jeyakumar","year":"2014","unstructured":"Jeyakumar, V., Lasserre, J.B., Li, G.: On polynomial optimization over non-compact semi-algebraic sets. J. Optim. Theory Appl. 163(3), 707\u2013718 (2014)","journal-title":"J. Optim. Theory Appl."},{"issue":"1","key":"1411_CR17","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF02807438","volume":"12","author":"J-L Krivine","year":"1964","unstructured":"Krivine, J.-L.: Anneaux pr\u00e9ordonn\u00e9s. Journal d\u2019analyse math\u00e9matique 12(1), 307\u2013326 (1964)","journal-title":"Journal d\u2019analyse math\u00e9matique"},{"issue":"3","key":"1411_CR18","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"key":"1411_CR19","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry, pp. 157\u2013270. Springer (2009)","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"1411_CR20","unstructured":"Lombardi, H., Perrucci, D., Roy, M.-F.: An elementary recursive bound for effective Positivstellensatz and Hilbert\u2019s 17th problem (2014). \narXiv:1404.2338"},{"issue":"1\u20133","key":"1411_CR21","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1023\/A:1008652705980","volume":"13","author":"Z-Q Luo","year":"1999","unstructured":"Luo, Z.-Q., Zhang, S.: On extensions of the Frank\u2013Wolfe theorems. Comput. Optim. Appl. 13(1\u20133), 87\u2013110 (1999)","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"1411_CR22","doi-asserted-by":"crossref","first-page":"575","DOI":"10.4153\/CMB-2003-054-7","volume":"46","author":"M Marshall","year":"2003","unstructured":"Marshall, M.: Optimization of polynomial functions. Can. Math. Bull. 46(4), 575\u2013587 (2003)","journal-title":"Can. Math. Bull."},{"issue":"1\u20132","key":"1411_CR23","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10107-013-0680-x","volume":"146","author":"J Nie","year":"2014","unstructured":"Nie, J.: Optimality conditions and finite convergence of the Lasserre hierarchy. Math. Program. 146(1\u20132), 97\u2013121 (2014)","journal-title":"Math. Program."},{"issue":"3","key":"1411_CR24","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1007\/s10107-005-0672-6","volume":"106","author":"J Nie","year":"2006","unstructured":"Nie, J., Demmel, J., Sturmfels, B.: Minimizing polynomials via sum of squares over the gradient ideal. Math. Program. 106(3), 587\u2013606 (2006)","journal-title":"Math. Program."},{"issue":"2","key":"1411_CR25","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"PA Parrilo","year":"2003","unstructured":"Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2), 293\u2013320 (2003)","journal-title":"Math. Program."},{"issue":"4","key":"1411_CR26","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1023\/A:1008203903341","volume":"10","author":"L Porkolab","year":"1997","unstructured":"Porkolab, L., Khachiyan, L.: On the complexity of semidefinite programs. J. Glob. Optim. 10(4), 351\u2013365 (1997)","journal-title":"J. Glob. Optim."},{"key":"1411_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04648-7","volume-title":"Positive Polynomials: From Hilbert\u2019s 17th Problem to Real Algebra. Springer Monographs in Mathematics","author":"A Prestel","year":"2001","unstructured":"Prestel, A., Delzell, C.N.: Positive Polynomials: From Hilbert\u2019s 17th Problem to Real Algebra. Springer Monographs in Mathematics. Springer, Berlin (2001)"},{"issue":"3","key":"1411_CR28","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1512\/iumj.1993.42.42045","volume":"42","author":"M Putinar","year":"1993","unstructured":"Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3), 969\u2013984 (1993)","journal-title":"Indiana Univ. Math. J."},{"key":"1411_CR29","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216\u2013226. ACM (1978)","DOI":"10.1145\/800133.804350"},{"key":"1411_CR30","doi-asserted-by":"crossref","first-page":"365","DOI":"10.2307\/1969640","volume":"60","author":"A Seidenberg","year":"1954","unstructured":"Seidenberg, A.: A new decision method for elementary algebra. Ann. Math. 60, 365\u2013374 (1954)","journal-title":"Ann. Math."},{"issue":"2","key":"1411_CR31","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01362149","volume":"207","author":"G Stengle","year":"1974","unstructured":"Stengle, G.: A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Math. Ann. 207(2), 87\u201397 (1974)","journal-title":"Math. Ann."},{"key":"1411_CR32","doi-asserted-by":"crossref","unstructured":"Tarski, A.: A decision method for elementary algebra and geometry. In: Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 24\u201384. Springer (1998)","DOI":"10.1007\/978-3-7091-9459-1_3"},{"key":"1411_CR33","unstructured":"Wagner, S.: Archimedean quadratic modules: a decision problem for real multivariate polynomials. Ph.D. thesis, University of Konstanz (2009)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01411-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01411-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01411-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T10:52:11Z","timestamp":1602759131000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01411-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,6]]},"references-count":33,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["1411"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01411-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,6]]},"assertion":[{"value":"20 March 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}