NP-hardness of deciding convexity of quartic polynomials and related problems
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 comple...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73527 https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1826189962010165248 |
|---|---|
| author | Ahmadi, Amir Ali Olshevsky, Alexander Parrilo, Pablo A. Tsitsiklis, John N. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Ahmadi, Amir Ali Olshevsky, Alexander Parrilo, Pablo A. Tsitsiklis, John N. |
| author_sort | Ahmadi, Amir Ali |
| collection | MIT |
| 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. |
| first_indexed | 2024-09-23T08:32:30Z |
| format | Article |
| id | mit-1721.1/73527 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:32:30Z |
| publishDate | 2012 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/735272022-09-23T12:49:15Z NP-hardness of deciding convexity of quartic polynomials and related problems Ahmadi, Amir Ali Olshevsky, Alexander Parrilo, Pablo A. Tsitsiklis, John N. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Ahmadi, Amir Ali Olshevsky, Alexander Parrilo, Pablo A. Tsitsiklis, John N. 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. National Science Foundation (U.S.). Focused Research Group (Grant DMS-0757207) National Science Foundation (U.S.) (Grant ECCS-0701623) 2012-10-01T19:11:27Z 2012-10-01T19:11:27Z 2011-11 2010-12 Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/73527 Ahmadi, Amir Ali et al. “NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems.” Mathematical Programming (2011). https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/10.1007/s10107-011-0499-2 Mathematical Programming Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Ahmadi, Amir Ali Olshevsky, Alexander Parrilo, Pablo A. Tsitsiklis, John N. NP-hardness of deciding convexity of quartic polynomials and related problems |
| title | NP-hardness of deciding convexity of quartic polynomials and related problems |
| title_full | NP-hardness of deciding convexity of quartic polynomials and related problems |
| title_fullStr | NP-hardness of deciding convexity of quartic polynomials and related problems |
| title_full_unstemmed | NP-hardness of deciding convexity of quartic polynomials and related problems |
| title_short | NP-hardness of deciding convexity of quartic polynomials and related problems |
| title_sort | np hardness of deciding convexity of quartic polynomials and related problems |
| url | http://hdl.handle.net/1721.1/73527 https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT ahmadiamirali nphardnessofdecidingconvexityofquarticpolynomialsandrelatedproblems AT olshevskyalexander nphardnessofdecidingconvexityofquarticpolynomialsandrelatedproblems AT parrilopabloa nphardnessofdecidingconvexityofquarticpolynomialsandrelatedproblems AT tsitsiklisjohnn nphardnessofdecidingconvexityofquarticpolynomialsandrelatedproblems |