Skip to main content
SpringerLink
Log in

NP-hardness of deciding convexity of quartic polynomials and related problems

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic polynomials. We also prove that deciding strict convexity, strong convexity, quasiconvexity, and pseudoconvexity of polynomials of even degree four or higher is strongly NP-hard. By contrast, we show that quasiconvexity and pseudoconvexity of odd degree polynomials can be decided in polynomial time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahmadi, A.A.: Algebraic relaxations and hardness results in polynomial optimization and Lyapunov analysis. PhD thesis, Massachusetts Institute of Technology, September (2011)

  2. 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)

  3. 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)

  4. Ahmadi, A.A., Parrilo, P.A.: A convex polynomial that is not sos-convex. Math. Program. (2011) doi:10.1007/s10107-011-0457-z

  5. Arrow K.J., Enthoven A.C.: Quasi-concave programming. Econometrica 29(4), 779–800 (1961)

    Article  MathSciNet  MATH  Google Scholar 

  6. 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)

    Google Scholar 

  7. Bazaraa M.S., Sherali H.D., Shetty C.M.: Nonlinear Programming, 3rd edn. Wiley-Interscience, London (2006)

    Book  MATH  Google Scholar 

  8. Blondel V.D., Tsitsiklis J.N.: A survey of computational complexity results in systems and control. Automatica 36(9), 1249–1274 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  9. Boyd S., Vandenberghe L.: Convex Optimization. Cambridge University Press, Cambridge (2004)

    MATH  Google Scholar 

  10. Canny, J.: Some algebraic and geometric computations in PSPACE. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 460–469. ACM, New York (1988)

  11. Chesi G., Hung Y.S.: Establishing convexity of polynomial Lyapunov functions and their sublevel sets. IEEE Trans. Automat. Control 53(10), 2431–2436 (2008)

    Article  MathSciNet  Google Scholar 

  12. Choi M.D.: Positive semidefinite biquadratic forms. Linear Algebra Appl. 12, 95–100 (1975)

    Article  MATH  Google Scholar 

  13. Cottle R.W., Ferland J.A.: On pseudo-convex functions of nonnegative variables. Math. Program. 1(1), 95–101 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  14. Crouzeix J.P., Ferland J.A.: Criteria for quasiconvexity and pseudoconvexity: relationships and comparisons. Math. Program. 23(2), 193–205 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  15. Crusius, C.A.R.: Automated analysis of convexity properties of nonlinear programs. PhD thesis, Department of Electrical Engineering, Stanford University (2002)

  16. 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–125 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  17. Doherty, A.C., Parrilo, P.A., Spedalieri, F.M.: Distinguishing separable and entangled states. Phys. Rev. Lett. 88(18) (2002)

  18. Ferland J.A.: Matrix-theoretic criteria for the quasiconvexity of twice continuously differentiable functions. Linear Algebra Appl. 38, 51–63 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  19. Garey M.R., Johnson D.S.: Computers and Intractability. W. H. Freeman and Co., San Francisco (1979)

    MATH  Google Scholar 

  20. Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 1.21. http://cvxr.com/cvx, May (2010)

  21. Guo B.: On the difficulty of deciding the convexity of polynomials over simplexes. Int. J. Comput. Geometry Appl. 6(2), 227–229 (1996)

    Article  MATH  Google Scholar 

  22. Gurvits, L.: Classical deterministic complexity of Edmonds’ problem and quantum entanglement. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 10–19 (electronic). ACM, New York (2003)

  23. Helton J.W., Nie J.: Semidefinite representation of convex sets. Math. Program. 122(1(Ser. A)), 21–64 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  24. Horn R.A., Johnson C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1995)

    Google Scholar 

  25. Lasserre J.B.: Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19(4), 1995–2014 (2008)

    Article  MathSciNet  Google Scholar 

  26. Lasserre J.B.: Representation of nonnegative convex polynomials. Arch. Math. 91(2), 126–130 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  27. Lasserre J.B.: Certificates of convexity for basic semi-algebraic sets. Appl. Math. Lett. 23(8), 912–916 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  28. 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–453. North-Holland Publishing Company, New York (1978)

    Google Scholar 

  29. Ling C., Nie J., Qi L., Ye Y.: Biquadratic optimization over unit spheres and semidefinite programming relaxations. SIAM J. Optim. 20(3), 1286–1310 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  30. 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)

  31. Mangasarian O.L.: Pseudo-convex functions. J. Soc. Ind. Appl. Math. Ser. A Control 3, 281–290 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  32. Mangasarian, O.L.: Nonlinear programming. SIAM, 1994. First published in 1969 by the McGraw-Hill Book Company, New York

  33. Mereau P., Paquet J.G.: Second order conditions for pseudo-convex functions. SIAM J. Appl. Math. 27, 131–137 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  34. Motzkin T.S., Straus E.G.: Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17, 533–540 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  35. Murty K.G., Kabadi S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39, 117–129 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  36. Nie, J.: Polynomial matrix inequality and semidefinite representation. arXiv:0908.0364 (2009)

  37. Pardalos, P.M. (ed.): Complexity in Numerical Optimization. World Scientific, River Edge (1993)

    MATH  Google Scholar 

  38. Pardalos P.M., Vavasis S.A.: Open questions in complexity theory for numerical optimization. Math. Program. 57(2), 337–339 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  39. Parrilo P.A., Sturmfels B.: Minimizing polynomial functions. Algorithm. Quantitat. Real Algebr. Geometry DIMACS Ser. Discr. Math. Theoret. Comput. Sci. 60, 83–99 (2003)

    MathSciNet  Google Scholar 

  40. 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–480. Springer, Berlin (2004)

  41. Rockafellar R.T.: Lagrange multipliers and optimality. SIAM Rev. 35, 183–238 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  42. Seidenberg A.: A new decision method for elementary algebra. Ann. Math. (2) 60, 365–374 (1954)

    Article  MathSciNet  MATH  Google Scholar 

  43. Tarski A.: A Decision Method for Elementary Algebra and Geometry, 2nd edn. University of California Press, Berkeley (1951)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratory for Information and Decision Systems, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA

    Amir Ali Ahmadi, Alex Olshevsky, Pablo A. Parrilo & John N. Tsitsiklis

Authors
  1. Amir Ali Ahmadi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alex Olshevsky
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pablo A. Parrilo
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. John N. Tsitsiklis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pablo A. Parrilo.

Additional information

This research was partially supported by the NSF Focused Research Group Grant on Semidefinite Optimization and Convex Algebraic Geometry DMS-0757207 and by the NSF grant ECCS-0701623.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ahmadi, A.A., Olshevsky, A., Parrilo, P.A. et al. NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Program. 137, 453–476 (2013). https://doi.org/10.1007/s10107-011-0499-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-011-0499-2

Mathematics Subject Classification (2000)

Search

Navigation