{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:16:52Z","timestamp":1781259412931,"version":"3.54.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T00:00:00Z","timestamp":1322611200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2013,2]]},"DOI":"10.1007\/s10107-011-0499-2","type":"journal-article","created":{"date-parts":[[2011,11,29]],"date-time":"2011-11-29T04:47:17Z","timestamp":1322542037000},"page":"453-476","source":"Crossref","is-referenced-by-count":85,"title":["NP-hardness of deciding convexity of quartic polynomials and related problems"],"prefix":"10.1007","volume":"137","author":[{"given":"Amir Ali","family":"Ahmadi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Olshevsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pablo A.","family":"Parrilo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John N.","family":"Tsitsiklis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2011,11,30]]},"reference":[{"key":"499_CR1","unstructured":"Ahmadi, A.A.: Algebraic relaxations and hardness results in polynomial optimization and Lyapunov analysis. PhD thesis, Massachusetts Institute of Technology, September (2011)"},{"key":"499_CR2","doi-asserted-by":"crossref","unstructured":"Ahmadi, A.A., Parrilo, P.A.: A positive definite polynomial Hessian that does not factor. In: Proceedings of the 48th IEEE Conference on Decision and Control (2009)","DOI":"10.1109\/CDC.2009.5400519"},{"key":"499_CR3","doi-asserted-by":"crossref","unstructured":"Ahmadi, A.A., Parrilo, P.A.: On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials. In: Proceedings of the 49th IEEE Conference on Decision and Control (2010)","DOI":"10.1109\/CDC.2010.5717510"},{"key":"499_CR4","doi-asserted-by":"crossref","unstructured":"Ahmadi, A.A., Parrilo, P.A.: A convex polynomial that is not sos-convex. Math. Program. (2011) doi: 10.1007\/s10107-011-0457-z","DOI":"10.1007\/s10107-011-0457-z"},{"issue":"4","key":"499_CR5","doi-asserted-by":"crossref","first-page":"779","DOI":"10.2307\/1911819","volume":"29","author":"K.J. Arrow","year":"1961","unstructured":"Arrow K.J., Enthoven A.C.: Quasi-concave programming. Econometrica 29(4), 779\u2013800 (1961)","journal-title":"Econometrica"},{"key":"499_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry, volume 10 of Algorithms and Computation in Mathematics","author":"S. Basu","year":"2006","unstructured":"Basu S., Pollack R., Roy M.F.: Algorithms in Real Algebraic Geometry, volume 10 of Algorithms and Computation in Mathematics, 2nd edn. Springer, Berlin (2006)","edition":"2"},{"key":"499_CR7","doi-asserted-by":"crossref","DOI":"10.1002\/0471787779","volume-title":"Nonlinear Programming","author":"M.S. Bazaraa","year":"2006","unstructured":"Bazaraa M.S., Sherali H.D., Shetty C.M.: Nonlinear Programming, 3rd edn. Wiley-Interscience, London (2006)","edition":"3"},{"issue":"9","key":"499_CR8","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.1016\/S0005-1098(00)00050-9","volume":"36","author":"V.D. Blondel","year":"2000","unstructured":"Blondel V.D., Tsitsiklis J.N.: A survey of computational complexity results in systems and control. Automatica 36(9), 1249\u20131274 (2000)","journal-title":"Automatica"},{"key":"499_CR9","doi-asserted-by":"crossref","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)"},{"key":"499_CR10","doi-asserted-by":"crossref","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 460\u2013469. ACM, New York (1988)","DOI":"10.1145\/62212.62257"},{"issue":"10","key":"499_CR11","doi-asserted-by":"crossref","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. Automat. Control 53(10), 2431\u20132436 (2008)","journal-title":"IEEE Trans. Automat. Control"},{"key":"499_CR12","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0024-3795(75)90058-0","volume":"12","author":"M.D. Choi","year":"1975","unstructured":"Choi M.D.: Positive semidefinite biquadratic forms. Linear Algebra Appl. 12, 95\u2013100 (1975)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"499_CR13","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF01584075","volume":"1","author":"R.W. Cottle","year":"1971","unstructured":"Cottle R.W., Ferland J.A.: On pseudo-convex functions of nonnegative variables. Math. Program. 1(1), 95\u2013101 (1971)","journal-title":"Math. Program."},{"issue":"2","key":"499_CR14","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF01583788","volume":"23","author":"J.P. Crouzeix","year":"1982","unstructured":"Crouzeix J.P., Ferland J.A.: Criteria for quasiconvexity and pseudoconvexity: relationships and comparisons. Math. Program. 23(2), 193\u2013205 (1982)","journal-title":"Math. Program."},{"key":"499_CR15","unstructured":"Crusius, C.A.R.: Automated analysis of convexity properties of nonlinear programs. PhD thesis, Department of Electrical Engineering, Stanford University (2002)"},{"issue":"2","key":"499_CR16","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s10100-007-0052-9","volume":"16","author":"E. Klerk de","year":"2008","unstructured":"de Klerk E.: The complexity of optimizing over a simplex, hypercube or sphere: a short survey. CEJOR Cent. Eur. J. Oper. Res. 16(2), 111\u2013125 (2008)","journal-title":"CEJOR Cent. Eur. J. Oper. Res."},{"key":"499_CR17","doi-asserted-by":"crossref","unstructured":"Doherty, A.C., Parrilo, P.A., Spedalieri, F.M.: Distinguishing separable and entangled states. Phys. Rev. Lett. 88(18) (2002)","DOI":"10.1103\/PhysRevLett.88.187904"},{"key":"499_CR18","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0024-3795(81)90007-0","volume":"38","author":"J.A. Ferland","year":"1981","unstructured":"Ferland J.A.: Matrix-theoretic criteria for the quasiconvexity of twice continuously differentiable functions. Linear Algebra Appl. 38, 51\u201363 (1981)","journal-title":"Linear Algebra Appl."},{"key":"499_CR19","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey M.R., Johnson D.S.: Computers and Intractability. W. H. Freeman and Co., San Francisco (1979)"},{"key":"499_CR20","unstructured":"Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 1.21. http:\/\/cvxr.com\/cvx , May (2010)"},{"issue":"2","key":"499_CR21","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1142\/S0218195996000150","volume":"6","author":"B. Guo","year":"1996","unstructured":"Guo B.: On the difficulty of deciding the convexity of polynomials over simplexes. Int. J. Comput. Geometry Appl. 6(2), 227\u2013229 (1996)","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"499_CR22","doi-asserted-by":"crossref","unstructured":"Gurvits, L.: Classical deterministic complexity of Edmonds\u2019 problem and quantum entanglement. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 10\u201319 (electronic). ACM, New York (2003)","DOI":"10.1145\/780543.780545"},{"issue":"1(Ser. A)","key":"499_CR23","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10107-008-0240-y","volume":"122","author":"J.W. Helton","year":"2010","unstructured":"Helton J.W., Nie J.: Semidefinite representation of convex sets. Math. Program. 122(1(Ser. A)), 21\u201364 (2010)","journal-title":"Math. Program."},{"key":"499_CR24","volume-title":"Matrix Analysis","author":"R.A. Horn","year":"1995","unstructured":"Horn R.A., Johnson C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1995)"},{"issue":"4","key":"499_CR25","doi-asserted-by":"crossref","first-page":"1995","DOI":"10.1137\/080728214","volume":"19","author":"J.B. Lasserre","year":"2008","unstructured":"Lasserre J.B.: Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19(4), 1995\u20132014 (2008)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"499_CR26","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1007\/s00013-008-2687-8","volume":"91","author":"J.B. Lasserre","year":"2008","unstructured":"Lasserre J.B.: Representation of nonnegative convex polynomials. Arch. Math. 91(2), 126\u2013130 (2008)","journal-title":"Arch. Math."},{"issue":"8","key":"499_CR27","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1016\/j.aml.2010.04.009","volume":"23","author":"J.B. Lasserre","year":"2010","unstructured":"Lasserre J.B.: Certificates of convexity for basic semi-algebraic sets. Appl. Math. Lett. 23(8), 912\u2013916 (2010)","journal-title":"Appl. Math. Lett."},{"key":"499_CR28","first-page":"409","volume-title":"Production Economics: A Dual Approach to Theory and Applications","author":"L.J. Lau","year":"1978","unstructured":"Lau L.J.: Testing and imposing monotonicity, convexity and quasiconvexity constraints. In: Fuss, M.A., McFadden, D.L. (eds.) Production Economics: A Dual Approach to Theory and Applications, pp. 409\u2013453. North-Holland Publishing Company, New York (1978)"},{"issue":"3","key":"499_CR29","doi-asserted-by":"crossref","first-page":"1286","DOI":"10.1137\/080729104","volume":"20","author":"C. Ling","year":"2009","unstructured":"Ling C., Nie J., Qi L., Ye Y.: Biquadratic optimization over unit spheres and semidefinite programming relaxations. SIAM J. Optim. 20(3), 1286\u20131310 (2009)","journal-title":"SIAM J. Optim."},{"key":"499_CR30","doi-asserted-by":"crossref","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 (2005)","DOI":"10.1109\/CDC.2005.1582399"},{"key":"499_CR31","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/0303020","volume":"3","author":"O.L. Mangasarian","year":"1965","unstructured":"Mangasarian O.L.: Pseudo-convex functions. J. Soc. Ind. Appl. Math. Ser. A Control 3, 281\u2013290 (1965)","journal-title":"J. Soc. Ind. Appl. Math. Ser. A Control"},{"key":"499_CR32","unstructured":"Mangasarian, O.L.: Nonlinear programming. SIAM, 1994. First published in 1969 by the McGraw-Hill Book Company, New York"},{"key":"499_CR33","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0127011","volume":"27","author":"P. Mereau","year":"1974","unstructured":"Mereau P., Paquet J.G.: Second order conditions for pseudo-convex functions. SIAM J. Appl. Math. 27, 131\u2013137 (1974)","journal-title":"SIAM J. Appl. Math."},{"key":"499_CR34","doi-asserted-by":"crossref","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"T.S. Motzkin","year":"1965","unstructured":"Motzkin T.S., Straus E.G.: Maxima for graphs and a new proof of a theorem of Tur\u00e1n. Can. J. Math. 17, 533\u2013540 (1965)","journal-title":"Can. J. Math."},{"key":"499_CR35","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"K.G. 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."},{"key":"499_CR36","unstructured":"Nie, J.: Polynomial matrix inequality and semidefinite representation. arXiv:0908.0364 (2009)"},{"key":"499_CR37","volume-title":"Complexity in Numerical Optimization","year":"1993","unstructured":"Pardalos, P.M. (ed.): Complexity in Numerical Optimization. World Scientific, River Edge (1993)"},{"issue":"2","key":"499_CR38","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF01581088","volume":"57","author":"P.M. Pardalos","year":"1992","unstructured":"Pardalos P.M., Vavasis S.A.: Open questions in complexity theory for numerical optimization. Math. Program. 57(2), 337\u2013339 (1992)","journal-title":"Math. Program."},{"key":"499_CR39","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1090\/dimacs\/060\/08","volume":"60","author":"P.A. Parrilo","year":"2003","unstructured":"Parrilo P.A., Sturmfels B.: Minimizing polynomial functions. Algorithm. Quantitat. Real Algebr. Geometry DIMACS Ser. Discr. Math. Theoret. Comput. Sci. 60, 83\u201399 (2003)","journal-title":"Algorithm. Quantitat. Real Algebr. Geometry DIMACS Ser. Discr. Math. Theoret. Comput. Sci."},{"key":"499_CR40","doi-asserted-by":"crossref","unstructured":"Rademacher, L., Vempala, S.: Testing geometric convexity. In: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, volume 3328 of Lecture Notes in Comput. Sci., pp. 469\u2013480. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-30538-5_39"},{"key":"499_CR41","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1137\/1035044","volume":"35","author":"R.T. Rockafellar","year":"1993","unstructured":"Rockafellar R.T.: Lagrange multipliers and optimality. SIAM Rev. 35, 183\u2013238 (1993)","journal-title":"SIAM Rev."},{"key":"499_CR42","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. (2) 60, 365\u2013374 (1954)","journal-title":"Ann. Math. (2)"},{"key":"499_CR43","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"A. Tarski","year":"1951","unstructured":"Tarski A.: A Decision Method for Elementary Algebra and Geometry, 2nd edn. University of California Press, Berkeley (1951)","edition":"2"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-011-0499-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-011-0499-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-011-0499-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,18]],"date-time":"2021-12-18T03:37:41Z","timestamp":1639798661000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-011-0499-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,30]]},"references-count":43,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["499"],"URL":"https:\/\/doi.org\/10.1007\/s10107-011-0499-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,30]]}}}