  


Complex Quadratic Optimization and Semidefinite Programming
Shuzhong Zhang (zhangse.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 max3cut model used in a recent paper of Goemans and Williamson. We first develop a closedform formula to compute the probability of a complexvalued 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 NPhard. We show that if the objective is to maximize a positive semidefinite Hermitian form, then the randomizationrounding procedure guarantees a worstcase performance ratio of $\pi/4 \approx 0.7854$, which is better than the ratio of $2/\pi \approx 0.6366$ for its counterpart in the real case due to Nesterov. Furthermore, if the objective matrix is realvalued positive semidefinite with nonpositive offdiagonal 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 (Semidefinite Programming ) Citation: Technical Report SEEM20043, Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong. Download: [PDF] Entry Submitted: 08/31/2004 Modify/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  