Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Springer eBooks

Semidefinite Relaxations, Multivariate Normal Distributions, and Order Statistics

Dimitris Bertsimas, Yinyu Ye

Published Jan 1, 1998• 67 citations
Publisher
DOI
10.1007/978-1-4613-0303-9_24

Related papers

Quadratic maximization and semidefinite relaxation

Shuzhong Zhang

Mathematical Programming•May 1, 2000•168 citations

Fixing variables in semidefinite relaxations

Christoph Heimberg

Lecture notes in computer science•Jan 1, 1997•4 citations

Covariance for quasi-probability distributions

Leon W. Cohen

Foundations of Physics•Dec 1, 1976•7 citations

Approximate maximum-likelihood estimation using semidefinite programming

J. Dahl, Bernard H. Fleury, Lieven Vandenberghe

We consider semidefinite relaxations of a quadratic optimization problem with polynomial constraints. This is an extension of quadratic problems with Boolean variables. Such combinatorial problems cannot, in general, be solved in polynomial time. Semidefinite relaxation has been proposed as a promising technique to give provable good bounds on certain Boolean quadratic problems in polynomial time. We formulate the extensions from Boolean variables to quarternary variables using (i) a polynomial relaxation or (ii) standard semidefinite relaxations of a linear transformation of Boolean variables. We compare the two different relaxation approaches analytically. The relaxations can all be expressed as semidefinite programs, which can be solved efficiently using e.g. interior point methods. Applications of our results include maximum likelihood estimation in communication systems, which we explore in simulations in order to compare the quality of the different relaxations with optimal solutions.

IEEE International Conference on Acoustics Speech and Signal Processing•Mar 22, 2004•9 citations

Algorithm 950: Ncpol2sdpa—Sparse Semidefinite Programming Relaxations for Polynomial Optimization Problems of Noncommuting Variables

Péter Wittek

A hierarchy of semidefinite programming (SDP) relaxations approximates the global optimum of polynomial optimization problems of noncommuting variables. Generating the relaxation, however, is a computationally demanding task, and only problems of commuting variables have efficient generators. We develop an implementation for problems of noncommuting variables that creates the relaxation to be solved by SDPA--a high-performance solver that runs in a distributed environment. We further exploit the inherent sparsity of optimization problems in quantum physics to reduce the complexity of the resulting relaxations. Constrained problems with a relaxation of order two may contain up to a hundred variables. The implementation is available in Python. The tool helps solve such as finding the ground state energy or testing quantum correlations.

arXiv:1308.6029•ACM Transactions on Mathematical Software•Jun 1, 2015•88 citations

Optimal Cooperative Relaying and Jamming for Secure Communication

Esa R. Alotaibi, Khairi Ashour Hamdi

This letter considers joint cooperative beamforming and jamming schemes in a cooperative relay network where distributed relay nodes perform cooperative beamforming. The problem of interest is to keep the eavesdropper's signal to interference and noise ratio (SINR) as low as possible while maintaining the legitimate receiver's SINR requirement. Applying semidefinite relaxation (SDR) technique, it is shown that a rank-one optimal solution always exists if perfect channel information is available. An optimal relay beamforming scheme has also been proposed for the scenario where only the second-order statistics of the eavesdropper's channel is available.

IEEE Wireless Communications Letters•Sep 29, 2015•25 citations
We consider semidefinite relaxations of a quadratic optimization problem with polynomial constraints. This is an extension of quadratic problems with Boolean variables. Such combinatorial problems cannot, in general, be solved in polynomial time. Semidefinite relaxation has been proposed as a promising technique to give provable good bounds on certain Boolean quadratic problems in polynomial time. We formulate the extensions from Boolean variables to quarternary variables using (i) a polynomial relaxation or (ii) standard semidefinite relaxations of a linear transformation of Boolean variables. We compare the two different relaxation approaches analytically. The relaxations can all be expressed as semidefinite programs, which can be solved efficiently using e.g. interior point methods. Applications of our results include maximum likelihood estimation in communication systems, which we explore in simulations in order to compare the quality of the different relaxations with optimal solutions.
A hierarchy of semidefinite programming (SDP) relaxations approximates the global optimum of polynomial optimization problems of noncommuting variables. Generating the relaxation, however, is a computationally demanding task, and only problems of commuting variables have efficient generators. We develop an implementation for problems of noncommuting variables that creates the relaxation to be solved by SDPA--a high-performance solver that runs in a distributed environment. We further exploit the inherent sparsity of optimization problems in quantum physics to reduce the complexity of the resulting relaxations. Constrained problems with a relaxation of order two may contain up to a hundred variables. The implementation is available in Python. The tool helps solve such as finding the ground state energy or testing quantum correlations.
This letter considers joint cooperative beamforming and jamming schemes in a cooperative relay network where distributed relay nodes perform cooperative beamforming. The problem of interest is to keep the eavesdropper's signal to interference and noise ratio (SINR) as low as possible while maintaining the legitimate receiver's SINR requirement. Applying semidefinite relaxation (SDR) technique, it is shown that a rank-one optimal solution always exists if perfect channel information is available. An optimal relay beamforming scheme has also been proposed for the scenario where only the second-order statistics of the eavesdropper's channel is available.