SDP relaxation of homogeneous quadratic optimization: Approximation bounds and applications
SDP relaxation of homogeneous quadratic optimization: Approximation bounds and applications
复制标题
DOI：
10.1017/cbo9780511804458.005
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Z. Luo;Tsung-Hui Chang
中科院分区：
文献类型：
--
作者：
Z. Luo;Tsung-Hui Chang
许多重要的工程问题可以转化为二次约束二次规划（QCQP）或分式QCQP的形式。一般来说，这些问题是非凸的和NP-困难的。本章介绍了半定规划（SDP）松弛过程，这类二次优化问题，可以产生一个可证明的近似最优解的随机多项式时间复杂度。我们说明了使用SDP松弛的上下文中的下行链路发射波束成形，并表明SDP松弛的方法可以生成全局最优解，或提供一个近似最优的解决方案，保证最坏情况下的近似性能。此外，我们描述了SDP松弛方法可以用于幅度滤波器设计和磁共振成像系统。
Many important engineering problems can be cast in the form of a quadratically constrained quadratic program (QCQP) or a fractional QCQP. In general, these problems are nonconvex and NP-hard. This chapter introduces a semidefinite programming (SDP) relaxation procedure for this class of quadratic optimization problems which can generate a provably approximately optimal solution with a randomized polynomial time complexity. We illustrate the use of SDP relaxation in the context of downlink transmit beamforming, and show that the SDP relaxation approach can either generate the global optimum solution, or provide an approximately optimal solution with a guaranteed worst-case approximation performance. Moreover, we describe how the SDP relaxation approach can be used in magnitude filter design and in magnetic resonance imaging systems.