A note on approximating quadratic programming with rank constraint

Abstract

The quadratic maximization problem with rank constraint means

where n and m are two given positive integers with n ≤ m, Q is a given real symmetric matrix, is the unit sphere in and stands for the Euclidean inner product. In this note, motivated by Briët, Filho and Vallentin's and Ye's excellent works [J. Briët, F. Filho, and F. Vallentin, The positive semidefinite Grothendieck problem with rank constraint, Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6198, 2010, pp. 31–42.; Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program. 84 (1999), pp. 219–226], we first derive the relative approximation ratio for the above problem with arbitrary symmetric matrix Q. While Q was supposed to be positive semidefinite in [J. Briët, F. Filhom, and F. Vallentin, The positive semidefinite Grothendieck problem with rank constraint, Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6198, 2010, pp. 31–42.]. Secondly, we extend such a relative approximation ratio to a generalization of the above optimization problem. Finally, a slightly improved relative approximation ratio for the optimization problem considered in [Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program. 84 (1999), pp. 219–226] is presented.

Keywords:

• quadratic programming
• rank constraint
• semidefinite programming
• relative approximation ratio

AMS Subject Classifications:

• 90C20
• 90C26

Acknowledgements

The authors are very grateful to the editor and three referees for their valuable comments and suggestions, which have considerably improved the presentation of this article. This work is partially supported by the National Natural Science Foundation of China (Grant No. 10871144).