On approximating complex quadratic optimization problems via semidefinite programming relaxations (Q877200)

The paper is concerned with both a NP-hard discrete and a continuous quadratic optimization problem in the complex Hermitian form, and it provides a generic algorithm as well as a unified approach for the approximation of these problems by semidefinite programming (SDP) relaxations. An example of the studied type of discrete problem is the MAX-3-CUT problem with a positive semidefinite Laplacian matrix, and examples of the continuous problem occur in connection with robust optimization and in control theory. For the discrete problem a \((k\sin (\pi /k))^{2}/(4\pi )\)-algorithm is given under the assumptions that the decision variables are \(k\)-ary and the objective matrix is positive semidefinite. For the continuous problem with positive semidefinite objective matrix the well-known \(\pi /4\)-approximation result is obtained, however, in comparison to earlier proofs of this result, by a simpler analysis and within a more general framework for such problems. Moreover it is shown that, in the latter case, the gap between the optimal values of the given problem and its SDP relaxation can be arbitrarily close to \(\pi /4\). At last, the new approach is used to demonstrate that an \(\Omega (1/\log (n))\)-approximation algorithm can be derived when the matrix in the quadratic objective of the continuous problem is not positive semidefinite.