- 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/2004Entry Accepted: 08/31/2004Entry Last Modified: 08/31/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.