Hardness and Approximation Results for Lp-Ball Constrained Homogeneous Polynomial Optimization Problems
From MaRDI portal
Publication:5247613
DOI10.1287/moor.2014.0644zbMath1310.90091arXiv1210.8284MaRDI QIDQ5247613
Publication date: 24 April 2015
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1210.8284
52C07: Lattices and convex bodies in (n) dimensions (aspects of discrete geometry)
90C26: Nonconvex programming, global optimization
90C59: Approximation methods and heuristics in mathematical programming
15A69: Multilinear algebra, tensor calculus
Related Items
Approximating Tensor Norms via Sphere Covering: Bridging the Gap between Primal and Dual, Approximation algorithms for optimization of real-valued general conjugate complex forms, Approximation methods for complex polynomial optimization, Self-concordance is NP-hard, On norm compression inequalities for partitioned block tensors, Some inequalities on the spectral radius of nonnegative tensors, On the tensor spectral \(p\)-norm and its dual norm via partitions
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation algorithms for homogeneous polynomial optimization with quadratic constraints
- Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints
- Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems
- On approximating complex quadratic optimization problems via semidefinite programming relaxations
- Block tensors and symmetric embeddings
- On solving biquadratic optimization via semidefinite relaxation
- NP-hardness of deciding convexity of quartic polynomials and related problems
- Eigenvalues of a real supersymmetric tensor
- Integration and optimization of multivariate polynomials by restriction onto a random subspace
- A PTAS for the minimization of polynomials of fixed degree over the simplex
- Grothendieck-Type Inequalities in Combinatorial Optimization
- The cubic spherical optimization problems
- A Semidefinite Relaxation Scheme for Multivariate Quartic Polynomial Optimization with Quadratic Constraints
- The UGC Hardness Threshold of the Lp Grothendieck Problem
- Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies
- Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
- Deterministic and randomized polynomial‐time approximation of radii
- Semidefinite relaxation approximation for multivariate bi‐quadratic optimization with quadratic constraints
- Probability Bounds for Polynomial Functions in Random Variables
- Norm attaining polynomials
- Grothendieck’s Theorem, past and present
- Most Tensor Problems Are NP-Hard
- Approximating the Cut-Norm via Grothendieck's Inequality
- The Grothendieck Constant is Strictly Smaller than Krivine's Bound
- On Polyhedral Approximations of the Second-Order Cone
