Optimization Online


Complex Quadratic Optimization and Semidefinite Programming

Shuzhong Zhang (zhang***at***se.cuhk.edu.hk)
Yongwei Huang (ywhuang***at***se.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society