New semidefinite relaxations for a class of complex quadratic programming problems

DOI10.1007/S10898-023-01290-ZMaRDI QIDQ6166105zbMATH OpenFDO

Authors Yingzhe Xu, Cheng Lu, Zhibin Deng, Ya-Feng Liu

Publication date 2 August 2023

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.09934

zbMATH Keywords

approximation algorithmdiscrete transmit beamformingphase quantized waveform designquadratic optimizationsemidefinite relaxation

Mathematics Subject Classification ID

Quadratic programming (90C20) Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: In this paper, we propose some new semidefinite relaxations for a class of nonconvex complex quadratic programming problems, which widely appear in the areas of signal processing and power system. By deriving new valid constraints to the matrix variables in the lifted space, we derive some enhanced semidefinite relaxations of the complex quadratic programming problems. Then, we compare the proposed semidefinite relaxations with existing ones and show that the newly proposed semidefinite relaxations could be strictly tighter than the previous ones. Moreover, the proposed semidefinite relaxations can be applied to more general cases of complex quadratic programming problems, whereas the previous ones are only designed for special cases. Numerical results indicate that the proposed semidefinite relaxations not only provide tighter relaxation bounds but also improve some existing approximation algorithms by finding better sub-optimal solutions.

Recommendations

• A new global algorithm for homogeneous complex quadratic programming problems and applications
• A new semidefinite programming relaxation scheme for a class of quadratic matrix problems
• New positive semidefinite relaxations for nonconvex quadratic programs
• Semidefinite programming relaxation for nonconvex quadratic programs
• A new convex relaxation for quadratically constrained quadratic programming

Cites work

• A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables
• An efficient quadratic programming relaxation based algorithm for large-scale MIMO detection
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming
• Complex Quadratic Optimization and Semidefinite Programming
• Convex Relaxation of Optimal Power Flow—Part I: Formulations and Equivalence
• Convex Relaxation of Optimal Power Flow—Part II: Exactness
• Design of Optimized Radar Codes With a Peak to Average Power Ratio Constraint
• Design of Phase Codes for Radar Performance Optimization With a Similarity Constraint
• Designing Unimodular Codes Via Quadratic Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On approximating complex quadratic optimization problems via semidefinite programming relaxations
• Phase recovery, MaxCut and complex semidefinite programming
• Tightness of a New and Enhanced Semidefinite Relaxation for MIMO Detection
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

Cited in

(1)

• A new global algorithm for homogeneous complex quadratic programming problems and applications

This page was built for publication: New semidefinite relaxations for a class of complex quadratic programming problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166105)