SDP relaxation of homogeneous quadratic optimization: approximation bounds and applications
Lists
Only you see this
Abstract
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.
BibTeX
@inproceedings{luo2009sdp,
author = {Zhi‐Quan Luo and Tsung‐Hui Chang},
title = {{SDP relaxation of homogeneous quadratic optimization: approximation bounds and applications}},
booktitle = {Cambridge},
year = {2009},
doi = {10.1017/cbo9780511804458.005},
}Loading related content...