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

DOI10.1007/s10107-011-0499-2zbMath1274.90516arXiv1012.1908OpenAlexW1884347414MaRDI QIDQ1942256

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

Publication date: 18 March 2013

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.1908

zbMATH Keywords

computational complexity quasiconvexity pseudoconvexity strict convexity polynomial time algorithms strong convexity odd degree polynomials global convexity even degree polynomials NP-hardness of deciding convexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

Amoebas, nonnegative polynomials and sums of squares supported on circuits, A hybrid LP/NLP paradigm for global optimization relaxations, Convergence guarantees for a class of non-convex and non-smooth optimization problems, Positive signs in massive gravity, Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere, Optimality conditions and optimization methods for quartic polynomial optimization, Extended Formulations in Mixed-Integer Convex Programming, Maximum entropy methods as the bridge between microscopic and macroscopic theory, Optimization on the Euclidean Unit Sphere, A survey of hidden convex optimization, Self-concordance is NP-hard, Minimization of even conic functions on the two-dimensional integral lattice, Sum-of-squares methods for controlled invariant sets with applications to model-predictive control, Geometric control of hybrid systems, On the estimation of Pareto front and dimensional similarity in many-objective evolutionary algorithm, On the complexity of detecting convexity over a box, On the complexity of quasiconvex integer minimization problem, Deciding positivity of multisymmetric polynomials, A new technique to derive tight convex underestimators (sometimes envelopes), An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials, How Do Exponential Size Solutions Arise in Semidefinite Programming?, On New Classes of Nonnegative Symmetric Tensors, Some computable quasiconvex multiwell models in linear subspaces without rank-one matrices, On the complexity of testing attainment of the optimal value in nonlinear optimization, Polynomial Norms, A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization, On solving a class of fractional semi-infinite polynomial programming problems, On the convexity bound of the generalized Drucker's yield function CB2001 for orthotropic sheets, DC decomposition of nonconvex polynomials with algebraic techniques, Global optimization test problems based on random field composition, On cones of nonnegative quartic forms, Linear interval parametric approach to testing pseudoconvexity, Testing pseudoconvexity via interval computation, Polyhedral approximation in mixed-integer convex optimization, On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems, Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere, Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems, Continuous cubic formulations for cluster detection problems in networks, A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem

Uses Software

CVX

Cites Work