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

From MaRDI portal
scientific article
Language Label Description Also known as
English
On approximating complex quadratic optimization problems via semidefinite programming relaxations
scientific article

    Statements

    On approximating complex quadratic optimization problems via semidefinite programming relaxations (English)
    0 references
    0 references
    0 references
    0 references
    19 April 2007
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    Hermitian quadratic functions
    0 references
    complex quadratic programming
    0 references
    complex semidefinite programming
    0 references
    Grothendieck's inequality
    0 references
    0 references