Complex Quadratic Optimization and Semidefinite Programming

Shuzhong Zhang (zhangse.cuhk.edu.hk)
Yongwei Huang (ywhuangse.cuhk.edu.hk)

Abstract: In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson. We first develop a closed-form formula to compute the probability of a complex-valued normally distributed bivariate random vector to be in a given angular region. This formula allows us to compute the expected value of a randomized (with a specific rounding rule) solution based on the optimal solution of the complex SDP relaxation problem. In particular, we study the limit of that model, in which the problem remains NP-hard. We show that if the objective is to maximize a positive semidefinite Hermitian form, then the randomization-rounding procedure guarantees a worst-case performance ratio of $\pi/4 \approx 0.7854$, which is better than the ratio of $2/\pi \approx 0.6366$ for its counter-part in the real case due to Nesterov. Furthermore, if the objective matrix is real-valued positive semidefinite with non-positive off-diagonal elements, then the performance ratio improves to 0.9349.

Keywords: Hermitian quadratic functions, approximation ratio, randomized algorithms, complex SDP relaxation.

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical Report SEEM2004-3, Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong.

Download: [PDF]

Entry Submitted: 08/31/2004
Entry Accepted: 08/31/2004
Entry Last Modified: 08/31/2004

Modify/Update this entry