Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

DOI10.1007/s10107-011-0464-0zbMath1230.90156OpenAlexW1999276385MaRDI QIDQ644908

Anthony Man-Cho So

Publication date: 7 November 2011

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

Full work available at URL: https://doi.org/10.1007/s10107-011-0464-0

zbMATH Keywords

convex programmingapproximation algorithmspolynomial optimizationdiameters of convex bodies

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational aspects related to convexity (52B55) Nonconvex programming, global optimization (90C26) Convex functions and convex programs in convex geometry (52A41) Approximation algorithms (68W25)

Related Items (30)

A tensor analogy of Yuan's theorem of the alternative and polynomial optimization with sign structure ⋮ On the spherical quasi-convexity of quadratic functions on spherically subdual convex sets ⋮ Concepts and techniques of optimization on the sphere ⋮ On the spherical quasi-convexity of quadratic functions ⋮ Extremal cubics on the circle and the 2-sphere ⋮ Rank-1 Tensor Properties with Applications to a Class of Tensor Optimization Problems ⋮ A note on semidefinite programming relaxations for polynomial optimization over a single sphere ⋮ On approximation algorithm for orthogonal low-rank tensor approximation ⋮ On norm compression inequalities for partitioned block tensors ⋮ Approximation algorithms for discrete polynomial optimization ⋮ On the spherical convexity of quadratic functions ⋮ Improved approximation results on standard quartic polynomial optimization ⋮ On solving biquadratic optimization via semidefinite relaxation ⋮ Approximating Tensor Norms via Sphere Covering: Bridging the Gap between Primal and Dual ⋮ Properties and methods for finding the best rank-one approximation to higher-order tensors ⋮ Approximation bounds for trilinear and biquadratic optimization problems over nonconvex constraints ⋮ Globally maximizing the sum of squares of quadratic forms over the unit sphere ⋮ Approximation algorithms for optimization of real-valued general conjugate complex forms ⋮ On cones of nonnegative quartic forms ⋮ A hybrid second-order method for homogenous polynomial optimization over unit sphere ⋮ Approximation algorithms for nonnegative polynomial optimization problems over unit spheres ⋮ Lower bounds for cubic optimization over the sphere ⋮ Approximation methods for complex polynomial optimization ⋮ On the tensor spectral \(p\)-norm and its dual norm via partitions ⋮ Bounds on the Spectral Norm and the Nuclear Norm of a Tensor Based on Tensor Partitions ⋮ An efficient alternating minimization method for fourth degree polynomial optimization ⋮ Inhomogeneous polynomial optimization over a convex set: An approximation approach ⋮ Probability Bounds for Polynomial Functions in Random Variables ⋮ Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems ⋮ Semi-definite representations for sets of cubics on the two-dimensional sphere

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tensor Decompositions and Applications
• Multiarray signal processing: tensor decomposition meets compressed sensing
• Approximation algorithms for homogeneous polynomial optimization with quadratic constraints
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• Z-eigenvalue methods for a global polynomial optimization problem
• Conditions for strong ellipticity of anisotropic elastic materials
• Conditions for strong ellipticity and M-eigenvalues
• Decoupling inequalities for polynomial chaos
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Geometric algorithms and combinatorial optimization.
• 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
• Global Optimization with Polynomials and the Problem of Moments
• Spectral methods for matrices and tensors
• A Semidefinite Relaxation Scheme for Multivariate Quartic Polynomial Optimization with Quadratic Constraints
• A Unified Theorem on SDP Rank Reduction
• 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
• Singular Value Decompositions and Low Rank Approximations of Tensors
• Most Tensor Problems Are NP-Hard

This page was built for publication: Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems