Hardness and Approximation Results for Lp-Ball Constrained Homogeneous Polynomial Optimization Problems
From MaRDI portal
Publication:5247613
DOI10.1287/moor.2014.0644zbMath1310.90091arXiv1210.8284OpenAlexW2153145191MaRDI 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
Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Nonconvex programming, global optimization (90C26) Approximation methods and heuristics in mathematical programming (90C59) Multilinear algebra, tensor calculus (15A69)
Related Items (7)
On norm compression inequalities for partitioned block tensors ⋮ Self-concordance is NP-hard ⋮ Some inequalities on the spectral radius of nonnegative tensors ⋮ 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 ⋮ 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
This page was built for publication: Hardness and Approximation Results for Lp-Ball Constrained Homogeneous Polynomial Optimization Problems
