NP-hardness of deciding convexity of quartic polynomials and related problems
type: Item
instance of: scholarly article
title: NP-hardness of deciding convexity of quartic polynomials and related problems
zbMATH Open document ID: 1274.90516
author: Amir Ali Ahmadi
author: Alex Olshevsky
author: Pablo A. Parrilo
author: John N. Tsitsiklis
published in: Mathematical Programming. Series A. Series B
publication date: 2013-03-18T00:00:00Z
full work available at URL: https://arxiv.org/abs/1012.1908
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6145965
zbMATH Keywords: NP-hardness of deciding convexity
zbMATH Keywords: polynomial time algorithms
zbMATH Keywords: computational complexity
zbMATH Keywords: global convexity
zbMATH Keywords: strict convexity
zbMATH Keywords: strong convexity
zbMATH Keywords: quasiconvexity
zbMATH Keywords: pseudoconvexity
zbMATH Keywords: even degree polynomials
zbMATH Keywords: odd degree polynomials
describes a project that uses: CVX
MaRDI profile type: Publication
OpenAlex ID: W1884347414
arXiv ID: 1012.1908
cites work: A convex polynomial that is not sos-convex
cites work: Quasi-Concave Programming
cites work: Algorithms in real algebraic geometry
cites work: A survey of computational complexity results in systems and control
cites work: Q4821526
cites work: Establishing Convexity of Polynomial Lyapunov Functions and Their Sublevel Sets
cites work: Positive semidefinite biquadratic forms
cites work: On pseudo-convex functions of nonnegative variables
cites work: Criteria for quasi-convexity and pseudo-convexity: Relationships and comparisons
cites work: The complexity of optimizing over a simplex, hypercube or sphere: a short survey
cites work: Matrix-theoretic criteria for the quasiconvexity of twice continuously differentiable functions
cites work: ON THE DIFFICULTY OF DECIDING THE CONVEXITY OF POLYNOMIALS OVER SIMPLEXES
cites work: Classical deterministic complexity of Edmonds' Problem and quantum entanglement
cites work: Semidefinite representation of convex sets
cites work: Convexity in SemiAlgebraic Geometry and Polynomial Optimization
cites work: Representation of nonnegative convex polynomials
cites work: Certificates of convexity for basic semi-algebraic sets
cites work: Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
cites work: Pseudo-Convex Functions
cites work: Maxima for Graphs and a New Proof of a Theorem of Turán
cites work: Some NP-complete problems in quadratic and nonlinear programming
cites work: Polynomial matrix inequality and semidefinite representation
cites work: Q4864690
cites work: Open questions in complexity theory for numerical optimization
cites work: Q4428719
cites work: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
cites work: Lagrange Multipliers and Optimality
cites work: A new decision method for elementary algebra
cites work: Q5807665
DOI: 10.1007/S10107-011-0499-2
description: scientific article