Complex Quadratic Optimization and Semidefinite Programming

Complex Quadratic Optimization and Semidefinite Programming
复制标题

DOI：
10.1137/04061341x
复制
发表时间：
2006-03
期刊：
SIAM J. Optim.
影响因子：
--
通讯作者：
Shuzhong Zhang;Yongwei Huang
Shuzhong Zhang;Yongwei Huang
中科院分区：
其他
文献类型：
--
作者：
Shuzhong Zhang;Yongwei Huang

文献摘要

被引文献

相似文献

在本文中，我们研究了Hermitian复合形式中一类离散二次优化问题的近似算法。我们研究的问题的特殊情况对应于Goemans和Williamson J. Comput的最新论文中使用的最大3切割模型。 System Sci。，68（2004），第442-470页。我们首先开发封闭形式的公式，以计算复杂值正态分布的双变量随机矢量的概率为在给定的角区域。该公式使我们能够根据复杂的半决赛编程松弛问题的最佳解决方案计算随机（具有特定舍入规则）解决方案的预期值。特别是，我们提出$ [m^2（1- \ cos \ frac {2 \ pi} {m}）/8 \ pi] $ - 近似算法，然后研究该模型的限制，其中该模型的限制仍然是NP-HARD。我们表明，如果目的是最大化积极的半菲尼特遗产形式，那么随机调整程序可以保证$ \ pi/4 \约0.7854 $的最差案例性能比率，这比$ 2/\ pi更好\在Nesterov造成的实际情况下，其对应物的大约0.6366 $。此外，如果物镜矩阵是具有非阳性异基因元素的实值阳性半限定的，则性能比将提高到0.9349。
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 $[m^2(1-\cos\frac{2\pi}{m})/8\pi]$-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 $\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 real-valued positive semidefinite with nonpositive off-diagonal elements, then the performance ratio improves to 0.9349.