Return to Colloquia & Seminar listing
Deciding polynomial convexity is NP-hard
Optimization| Speaker: | Amirali Ahmadi, MIT |
| Location: | 1147 MSB |
| Start time: | Tue, Mar 15 2011, 4:10PM |
Description
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.