Amir Ali Ahmadi

NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems

  • Amir Ali Ahmadi
  • Alex Olshevsky
  • Pablo A. Parrilo
  • John N. Tsitsiklis
    • Categories Convex Optimization, Global Optimization Theory Tags , , ,

    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 … Read more

    A convex polynomial that is not sos-convex

  • Amir Ali Ahmadi
  • Pablo A. Parrilo
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    A multivariate polynomial $p(x)=p(x_1,…,x_n)$ is sos-convex if its Hessian $H(x)$ can be factored as $H(x)= M^T(x) M(x)$ with a possibly nonsquare polynomial matrix $M(x)$. It is easy to see that sos-convexity is a sufficient condition for convexity of $p(x)$. Moreover, the problem of deciding sos-convexity of a polynomial can be cast as the feasibility of … Read more