Approximation algorithms for homogeneous polynomial optimization with quadratic constraints

DOI10.1007/s10107-010-0409-zzbMath1206.90124OpenAlexW2076426934MaRDI QIDQ607501

Simai He, Zhening Li, Shu-Zhong Zhang

Publication date: 22 November 2010

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

Full work available at URL: https://researchportal.port.ac.uk/portal/en/publications/approximation-algorithms-for-homogeneous-polynomial-optimization-with-quadratic-constraints(66108c79-caa8-440a-a77a-3eb5714d6cec).html

zbMATH Keywords

approximation algorithmmulti-linear tensor formpolynomial function optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

A tensor analogy of Yuan's theorem of the alternative and polynomial optimization with sign structure, Concepts and techniques of optimization on the sphere, The cubic spherical optimization problems, 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, Several approximation algorithms for sparse best rank-1 approximation to higher-order tensors, Global optimality conditions and optimization methods for constrained polynomial programming problems, On norm compression inequalities for partitioned block tensors, Self-concordance is NP-hard, Approximation algorithms for discrete polynomial optimization, Jacobi-type algorithms for homogeneous polynomial optimization on Stiefel manifolds with applications to tensor approximations, Nonlinear Perron--Frobenius Theorems for Nonnegative Tensors, Maximization of homogeneous polynomials over the simplex and the sphere: structure, stability, and generic behavior, On solving biquadratic optimization via semidefinite relaxation, The convergence properties of infeasible inexact proximal alternating linearized minimization, Practical approximation algorithms for \(\ell_1\)-regularized sparse rank-1 approximation to higher-order tensors, Variational Characterization of Monotone Nonlinear Eigenvector Problems and Geometry of Self-Consistent Field Iteration, Extreme Ratio Between Spectral and Frobenius Norms of Nonnegative Tensors, Approximating Tensor Norms via Sphere Covering: Bridging the Gap between Primal and Dual, Two extremal problems related to orders, On New Classes of Nonnegative Symmetric Tensors, On Orthogonal Tensors and Best Rank-One Approximation Ratio, Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems, Alternating direction method for bi-quadratic programming, 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, On local convexity of quadratic transformations, The Epsilon-Alternating Least Squares for Orthogonal Low-Rank Tensor Approximation and Its Global Convergence, On decompositions and approximations of conjugate partial-symmetric tensors, Semidefinite relaxation approximation for multivariate bi‐quadratic optimization with quadratic constraints, Approximation algorithms for optimization of real-valued general conjugate complex forms, On cones of nonnegative quartic forms, Convergence analysis of a block improvement method for polynomial optimization over unit spheres, A feasible method for optimization with orthogonality constraints, An approach for minimizing a quadratically constrained fractional quadratic problem with application to the communications over wireless channels, Linear operators and positive semidefiniteness of symmetric tensor spaces, Penalized semidefinite programming for quadratically-constrained quadratic optimization, A concise proof to the spectral and nuclear norm bounds through tensor partitions, Approximation algorithms for nonnegative polynomial optimization problems over unit spheres, Lower bounds for cubic optimization over the sphere, Characterizing Real-Valued Multivariate Complex Polynomials and Their Symmetric Tensor Representations, Approximation methods for complex polynomial optimization, Shifted eigenvalue decomposition method for computing C-eigenvalues of a piezoelectric-type tensor, 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, A Unifying Perron--Frobenius Theorem for Nonnegative Tensors via Multihomogeneous Maps, 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, Computing the largest C-eigenvalue of a tensor using convex relaxation

Uses Software

• SDPA
• SeDuMi
• SDPT3
• GloptiPoly
• CVX

Cites Work

• Unnamed Item
• Unnamed Item
• Eigenvalues and invariants of tensors
• A tensor product matrix approximation problem in quantum physics
• Jackson-type theorems in homogeneous approximation
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• Global optimization of higher order moments in portfolio selection
• Approximating global quadratic optimization with convex quadratic constraints
• Multivariate polynomial minimization and its application in signal processing
• Semidefinite programming relaxations for semialgebraic problems
• Approximating quadratic programming with bound and quadratic constraints
• Quadratic maximization and semidefinite relaxation
• Penalized maximum-likelihood estimation, the Baum-Welch algorithm, diagonal balancing of symmetric matrices and applications to training acoustic data
• On maximization of quadratic form over intersection of ellipsoids with common center
• On the use of homogeneous polynomials to develop anisotropic yield functions with applications to sheet forming
• Eigenvalues of a real supersymmetric tensor
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Extrema of a real polynomial
• Global Optimization with Polynomials and the Problem of Moments
• Lectures on Modern Convex Optimization
• Polynomials nonnegative on a grid and discrete optimization
• On the Best Rank-1 Approximation of Higher-Order Supersymmetric Tensors
• A Semidefinite Relaxation Scheme for Multivariate Quartic Polynomial Optimization with Quadratic Constraints
• A Unified Theorem on SDP Rank Reduction
• GloptiPoly 3: moments, optimization and semidefinite programming
• Classical deterministic complexity of Edmonds' Problem and quantum entanglement
• Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
• Global Optimization of the Scenario Generation and Portfolio Selection Problems
• Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Multivariate Nonnegative Quadratic Mappings
• Global Minimization of Normal Quartic Polynomials Based on Global Descent Directions
• An Eigenvalue Method for Testing Positive Definiteness of a Multivariate Form
• Blind constant modulus equalization via convex optimization
• Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints
• GloptiPoly
• Complex Quadratic Optimization and Semidefinite Programming
• Approximation by homogeneous polynomials