SDP relaxation of homogeneous quadratic optimization: Approximation bounds and applications

Zhi-Quan Luo, Tsung Hui Chang

Research output: Chapter in Book/Report/Conference proceedingChapter

34 Scopus citations

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. Introduction In this chapter, we consider several classes of nonconvex quadratic constrained quadratic programs (QCQPs) and a class of nonconvex fractional QCQPs. The importance of these classes of problems lies in their wide-ranging applications in signal processing and communications which include: • the Boolean least-squares (LS) problem in digital communications [1]; • the noncoherent maximum-likelihood detection problem in multiple-input multipleoutput (MIMO) communications [2, 3]; • the MAXCUT problem in network optimization [4]; • the large-margin parameter estimation problem in automatic speech recognition [5–8]; • the optimum coded waveform design for radar detection [9]; • the image segmentation problem in pattern recognition [10]; • the magnitude filter design problem in digital signal processing [11]; • the transmit B 1 shim and specific absorption rate computation in magnetic resonance imaging (MRI) systems [12, 13];• […]

Original languageEnglish (US)
Title of host publicationConvex Optimization in Signal Processing and Communications
PublisherCambridge University Press
Pages117-165
Number of pages49
Volume9780521762229
ISBN (Electronic)9780511804458
ISBN (Print)9780521762229
DOIs
StatePublished - Jan 1 2009

Fingerprint Dive into the research topics of 'SDP relaxation of homogeneous quadratic optimization: Approximation bounds and applications'. Together they form a unique fingerprint.

Cite this