Semidefinite Relaxation of Quadratic Optimization Problems

By Zhi-Quan Tom Luo, Wing-Kin Ma, Anthony Man-Cho So, Yinyu Ye, Shuzhong Zhang. IEEE Signal Processing Magazine, 2010

3,673 citations recorded by the source corpus.

Subfields: Computational Mechanics, Electrical and Electronic Engineering, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/2527f1b5d69b8abe14bb9d10c791a3b96c7cf1b4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Electrical and Electronic Engineering

In Numerical Analysis

Citations in the corpus

Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow (2016, background): “5) [44], [49] that does not scale well with the dimensionalityn.”
Learning to optimize: Training deep neural networks for wireless resource management (2017, positive): “[8], semidefinite relaxation based schemes [9]), admission”
Joint Transmit Beamforming for Multiuser MIMO Communications and MIMO Radar (2019, methodology): “In this subsection, we tackle the non-convex problem (25) using an SDR strategy [60], [61].”
Robust Beamforming for Secure Communication in Systems With Wireless Information and Power Transfer (2013, methodology): “Finally, we use semidefinite programming relaxation (SDR) [26], [27] to obtain the optimal resource allocation solution for the reformula ted problem.”
Phase Retrieval from Coded Diffraction Patterns (2013, neutral): “For related convex relaxations of quadratic problems, we refer the interested reader to the wonderful tutorial [52].”
Intelligent Reflecting Surface Aided Multigroup Multicast MISO Communication Systems (2019, methodology): “In order to reduce the high computational complexity of SDR, several low-complexity algorithms, such as successive convex approximation approach in the single-group multicast scenario [18], asymptotic approach [19] and heuristic algorithm [20] in the multigroup multicast scenario, have been proposed”
Moment/Sum-of-Squares Hierarchy for Complex Polynomial Optimization (2015, background): “Multivariate polynomial optimization where variables and data are complex numbers is a non-deterministic polynomial-time hard problem that arises in various applications such as electric power systems (Section 4), imaging science [10, 15, 32, 80], signal processing [1, 8, 20, 49, 52, 54], automatic ”
Fifty Years of MIMO Detection: The Road to Large-Scale MIMOs (2015, background): “SER performance.17 Furthermore, a bit-based SDPR detector capable of directly detecting the nonlinear Gray mapping aided rectangular high-order QAM symbols was proposed in [147], where the unequal error protection property (UEP) of QAM bits was exploited and the resultant SDPR detector was shown to ”
Optimal Resource Allocation in Coordinated Multi-Cell Systems (2013, methodology): “If we anyway would achieve a high-rank solution (although these have not been found in simulations), an approximate solution can be achieved by, for example, taking the dominating eigenvector of Sk as the beamforming direction v̄k or taking a realization from a zero-mean Gaussian distribution with t”
MU-MIMO Communications With MIMO Radar: From Co-Existence to Joint Transmission (2017, methodology): “For non-rank-1 solutions, an approximated solution is obtained by standard rank-1 approximation techniques, such as eigenvalue decomposition or Gaussian randomization [35].”
Connecting the Dots: Identifying Network Structure via Graph Signal Processing (2018, neutral): “Interestingly, this problem can be tackled using a convexification technique known as semidefinite relaxation [31].”
Distributed Optimal Power Flow for Smart Microgrids (2012, methodology): “Albeit polynomial, the computational complexity incurred by standard interior-point solvers for SDP does not scale we ll with the number of nodes N , and the number of constraints Nc [17].”
MIMO Radar Waveform Design With Constant Modulus and Similarity Constraints (2014, background): “However, in practical applications, constant modulus waveforms are often required due to the limit of nonlinear radar amplifiers.”
Outage Constrained Robust Transmit Optimization for Multiuser MISO Downlinks: Tractable Approximations by Conic Optimization (2011, background): “7 issue by semidefinite relaxation (SDR) [3], [25].”
Application of the Moment-SOS Approach to Global Optimization of the OPF Problem (2013, background): “They discard the rank constraint, as it is done in Shor’s relaxation [8], a well-known procedure which applies to quadratically constrained quadratic problems (see [9], [10] and the references therein).”
Full-Duplex Communication for ISAC: Joint Beamforming and Power Optimization (2022, methodology): “An additional procedure, such as Gaussian randomization [29], is generally exploited for recovering the beamforming vectors {vl}l=1, i.”
Simultaneously Transmitting And Reflecting (STAR) RIS Aided Wireless Communications (2021, methodology): “5 )) [10, 40], where K = 2 is the number of users.”