Bi-Quadratic Optimization over Unit Spheres and Semidefinite Programming Relaxations

This paper studies the so-called biquadratic optimization over unit spheres minx∈Rn,y∈Rm 1≤i,k≤n, 1≤j,l≤m bijklxiyjxkyl, subject to ‖x ‖ = 1, ‖y ‖ = 1. We show that this problem is NP-hard, and there is no polynomial time algorithm returning a positive relative approxi-mation bound. Then, we present various approximation methods based on semidefinite programming (SDP) relaxations. Our theoretical results are as follows: For general biquadratic forms, we develop a 1 2max{m,n}2-approximation algorithm under a slightly weaker approximation notion; for biquadratic forms that are square-free, we give a relative approximation bound 1 nm; when min{n,m} is a con-stant, we present two polynomial time approximation schemes (PTASs) which are based on sum of squares (SOS) relaxation hierarchy and grid sampling of the standard simplex. For practical com-putational purposes, we propose the first order SOS relaxation, a convex quadratic SDP relaxation, and a simple minimum eigenvalue method and show their error bounds. Some illustrative numerical examples are also included