TY - JOUR

T1 - Complex quadratic optimization and semidefinite programming

AU - Zhang, Shuzhong

AU - Huang, Yongwei

PY - 2006

Y1 - 2006

N2 - 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 [J. Comput. System Sci., 68 (2004), pp. 442-470]. 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 semidefinite programming relaxation problem. In particular, we present an {m2(1 -cos 2π/m)/87π]-approximation algorithm, and then 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 π/4 ≈ 0.7854, which is better than the ratio of 2/π ≈ 0.6366 for its counterpart in the real case due to Nesterov. Furthermore, if the objective matrix is real-valued positive semidefinite with nonpositive off-diagonal elements, then the performance ratio improves to 0.9349.

AB - 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 [J. Comput. System Sci., 68 (2004), pp. 442-470]. 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 semidefinite programming relaxation problem. In particular, we present an {m2(1 -cos 2π/m)/87π]-approximation algorithm, and then 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 π/4 ≈ 0.7854, which is better than the ratio of 2/π ≈ 0.6366 for its counterpart in the real case due to Nesterov. Furthermore, if the objective matrix is real-valued positive semidefinite with nonpositive off-diagonal elements, then the performance ratio improves to 0.9349.

KW - Approximation ratio

KW - Complex semidefmite programming relaxation

KW - Hermitian quadratic functions

KW - Randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=33747159547&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33747159547&partnerID=8YFLogxK

U2 - 10.1137/04061341X

DO - 10.1137/04061341X

M3 - Article

AN - SCOPUS:33747159547

VL - 16

SP - 871

EP - 890

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 3

ER -