TY - JOUR

T1 - Approximation algorithms for homogeneous polynomial optimization with quadratic constraints

AU - He, Simai

AU - Li, Zhening

AU - Zhang, Shuzhong

PY - 2010/10

Y1 - 2010/10

N2 - In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization 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, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time approximation algorithms. In particular, we first study optimization 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 be dependent only on the dimensions of the model. The methods are then extended to optimize a generic multi-variate homogeneous polynomial function with spherical constraint. Likewise, approximation algorithms are proposed with provable approximation performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids; namely, we consider maximization of a homogeneous polynomial over the intersection of ellipsoids 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.

AB - In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization 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, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time approximation algorithms. In particular, we first study optimization 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 be dependent only on the dimensions of the model. The methods are then extended to optimize a generic multi-variate homogeneous polynomial function with spherical constraint. Likewise, approximation algorithms are proposed with provable approximation performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids; namely, we consider maximization of a homogeneous polynomial over the intersection of ellipsoids 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.

KW - Approximation algorithm

KW - Multi-linear tensor form

KW - Polynomial function optimization

UR - http://www.scopus.com/inward/record.url?scp=77958088475&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77958088475&partnerID=8YFLogxK

U2 - 10.1007/s10107-010-0409-z

DO - 10.1007/s10107-010-0409-z

M3 - Article

AN - SCOPUS:77958088475

SN - 0025-5610

VL - 125

SP - 353

EP - 383

JO - Mathematical Programming

JF - Mathematical Programming

IS - 2

ER -