Approximation Algorithms for Homogeneous Polynomial Optimization with Quadratic Constraints

In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such opti-mization models have wide applications, e.g., in signal processing, magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions are non-convex in general, the problems under consideration are all NP-hard. In this paper we shall focus on polynomial-time approximation algorithms. In particular, we first study optimiza-tion of a multi-linear tensor function over the Cartesian product of spheres. We shall propose approximation algorithms for such problem and derive worst-case performance ratios, which are shown to depend only on the dimensions of the models. The methods are then extended to op-timize a generic multi-variate homogeneous polynomial function with spherical constraint. Like-wise, approximation algorithms are proposed with provable relative approximation performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids. In particular, we consider maximization of a homogeneous polynomial over the intersection of ellip-soids centered at the origin, and propose polynomial-time approximation algorithms with provable worst-case performance ratios. Numerical results are reported, illustrating the effectiveness of the approximation algorithms studied