NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
arXiv:1012.1908 · doi:10.1007/s10107-011-0499-2
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.
20 pages
References in corpus (2)
Cited by in corpus (27)
- Extraction of the proton radius from electron-proton scattering data
- Consistency of the Standard Model Effective Field Theory
- Positive Signs in Massive Gravity
- A Complete Characterization of the Gap between Convexity and SOS-Convexity
- Polyhedral approximation in mixed-integer convex optimization
- Computational Complexity of Vacua and Near-Vacua in Field and String Theory
- Convergence guarantees for a class of non-convex and non-smooth optimization problems
- Extended Formulations in Mixed-integer Convex Programming
- Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis
- Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
- Global Convergence to the Equilibrium of GANs using Variational Inequalities
- Classical and strong convexity of sublevel sets and application to attainable sets of nonlinear systems
- On the complexity of quasiconvex integer minimization problem
- Global optimization test problems based on random field composition
- Deciding positivity of multisymmetric polynomials
- On Difference-of-SOS and Difference-of-Convex-SOS Decompositions for Polynomials
- Semidefinite programming relaxations for linear semi-infinite polynomial programming
- Geometry of 3D Environments and Sum of Squares Polynomials
- Maximum entropy methods as the bridge between macroscopic and microscopic theory
- A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization
- A Moment-SOS Hierarchy for Robust Polynomial Matrix Inequality Optimization with SOS-Convexity
- On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization
- A survey of hidden convex optimization
- An SDP method for Fractional Semi-infinite Programming Problems with SOS-convex polynomials
- Moment-sos and spectral hierarchies for polynomial optimization on the sphere and quantum de Finetti theorems
- Complexity Aspects of Fundamental Questions in Polynomial Optimization
- On Solving a Class of Fractional Semi-infinite Polynomial Programming Problems